https://pastein.ru/t/R-y
Загрузка данных
Ниже приведены готовые ответы на все 30 вопросов по системному программированию (C, Windows API, структуры данных, алгоритмы). Ответы сформулированы так, чтобы их можно было проговорить устно преподавателю.
---
Аргументы командной строки и строки
Вопрос 1. argc и argv в функции main. Их связь с запуском программы из командной строки Windows. Пример использования.
argc (argument count) — количество аргументов командной строки, включая имя самой программы. argv (argument vector) — массив указателей на строки с этими аргументами. При запуске программы из командной строки Windows, например myprog.exe -f input.txt, система разбивает строку на токены и передаёт в main. argc будет равно 3, argv[0] — "myprog.exe", argv[1] — "-f", argv[2] — "input.txt". Пример использования: проверить argc > 1, затем открыть файл argv[1].
Вопрос 2. Ключи (опции) командной строки. Отличия ключей с аргументами от ключей без аргументов. Примеры.
Ключи — это специальные аргументы, обычно начинающиеся с / или -, управляющие поведением программы. Ключи без аргументов — просто флаги: -h (справка), -v (версия). Ключи с аргументами требуют дополнительного значения: -o output.txt или --input file.txt. В Windows принято /O output.txt. Отличие: при разборе, если ключ требует аргумент, следующий токен читается как значение.
Вопрос 3. Функция getopt. Её назначение при разборе аргументов командной строки. Основные ограничения.
getopt — стандартная функция в POSIX-системах (Linux, MinGW) для разбора коротких опций вида -a -b value. Она автоматически обрабатывает группировку (-ab), проверяет наличие аргументов для опций, возвращает код опции. Основные ограничения: не поддерживает длинные опции (--help) без дополнительных библиотек (getopt_long), не работает нативно в Windows (нужен эмулятор), и требует глобальные переменные optarg, optind.
Вопрос 4. Строки в языке C. Отличия массива символов char str[] от указателя char* ptr. Причина, по которой нельзя изменять строковые литералы.
char str[] = "hello" — массив, выделенный в стеке или статической памяти, который содержит копию строки, его можно изменять. char *ptr = "hello" — указатель на строковой литерал, который размещается в сегменте только для чтения (обычно в .rodata). Попытка изменить ptr[0] приводит к неопределённому поведению (часто к crash), потому что литералы помещаются в защищённую память. Изменять можно только массив, который является копией.
Вопрос 5. Функции библиотеки string.h для поиска подстроки в строке. Отличия между strchr, strrchr и strstr.
strchr(str, c) — ищет первое вхождение символа c в строке str, возвращает указатель на него или NULL. strrchr(str, c) — ищет последнее вхождение символа (движется с конца). strstr(str, substr) — ищет первое вхождение целой подстроки substr в str, возвращает указатель на начало или NULL. Отличия: первые две работают с одним символом, strstr — с подстрокой.
---
Структуры и динамическая память
Вопрос 6. Структура (struct) в языке C. Её назначение. Пример объявления и использования структуры.
Структура — это пользовательский тип данных, объединяющий переменные разных типов под одним именем. Назначение — группировка связанных данных (например, студент: имя, возраст, оценка). Пример:
```c
struct Student {
char name[50];
int age;
float grade;
};
struct Student s = {"Ivan", 20, 4.8};
s.age = 21;
```
Вопрос 7. Отличия стековой памяти от динамической (кучевой). Преимущества и недостатки каждого типа памяти.
Стек: автоматическое выделение/освобождение при входе/выходе из функции, очень быстрый, ограниченный размер (обычно 1-8 МБ). Недостаток — время жизни переменной ограничено блоком. Куча (динамическая): выделение вручную через malloc/free, размер ограничен только доступной памятью, время жизни — до явного освобождения. Недостатки: медленнее, риск утечек и фрагментации.
Вопрос 8. Функции malloc, calloc, realloc и free. Отличия между malloc и calloc. Правила безопасного использования realloc.
malloc(size) выделяет блок размером size байт, не инициализирует. calloc(count, size) выделяет память под count элементов по size байт и обнуляет все байты. realloc(ptr, new_size) изменяет размер ранее выделенного блока, при необходимости копирует данные. free(ptr) освобождает память. Правила realloc: если ptr == NULL, работает как malloc. Если realloc вернул NULL, старый указатель остаётся валидным, поэтому нужно сохранять его во временную переменную: void *tmp = realloc(ptr, new_size); if (!tmp) { /* ошибка, ptr не потерян */ } else { ptr = tmp; }
Вопрос 9. Утечка памяти (memory leak). Пример кода с утечкой памяти и способ её исправления.
Утечка — когда программа теряет указатель на выделенную динамическую память, и память не может быть освобождена. Пример:
```c
void leak() {
int *p = malloc(100 * sizeof(int));
// забыли free(p);
}
```
Исправление: добавить free(p); перед выходом из функции.
Вопрос 10. Двойное освобождение (double free) и использование памяти после освобождения (use-after-free). Чем опасны эти ошибки.
Double free — вызов free дважды на один и тот же указатель. Опасность: может повредить менеджер кучи, привести к крашу или уязвимости. Use-after-free — обращение к памяти после free. Опасность: память могла быть перераспределена под другие данные, чтение даёт мусор, запись портит чужие структуры. Обе ошибки ведут к неопределённому поведению и трудно отлаживаются.
Вопрос 11. Валидация данных. Проверки, необходимые при добавлении новой записи в динамический массив структур.
При добавлении записи в динамический массив структур нужно: 1) проверить, что переданные данные корректны (не NULL, диапазоны значений). 2) Проверить, достаточно ли выделенной памяти, если нет — использовать realloc (проверяя успешность). 3) После добавления обновить счётчик размера. 4) При ошибке выделения памяти корректно обработать (вернуть код ошибки, не потерять старые данные). 5) Избегать дублирования записей, если требуется уникальность.
---
Битовые операции и маски
Вопрос 12. Шесть битовых операторов в языке C. Примеры работы операторов &, |, ^, ~, <<, >>.
· & — побитовое И: 5 & 3 (0101 & 0011 = 0001 = 1)
· | — побитовое ИЛИ: 5 | 3 = 0111 = 7
· ^ — исключающее ИЛИ (XOR): 5 ^ 3 = 0110 = 6
· ~ — побитовое НЕ (инверсия): ~5 = ...11111010 (зависит от размера)
· << — сдвиг влево: 5 << 1 = 1010 = 10
· >> — сдвиг вправо: 5 >> 1 = 0010 = 2
Вопрос 13. Битовая маска. Способы установки, сброса, проверки и переключения определённого бита в числе с помощью масок. Примеры.
Маска — число с единицей в нужной позиции. Пусть mask = 1 << n.
· Установка бита: x |= mask
· Сброс (очистка): x &= ~mask
· Проверка: if (x & mask)
· Переключение (toggle): x ^= mask
Вопрос 14. Отличия сдвига вправо для знаковых и беззнаковых типов в Windows. Причина использования беззнаковых типов при битовых операциях.
В Windows (как и везде) для беззнаковых типов сдвиг вправо заполняет освободившиеся биты нулями (логический сдвиг). Для знаковых типов сдвиг вправо может быть арифметическим: заполнение знаком (единицами для отрицательных чисел) — это зависит от компилятора, но в стандарте C для отрицательных знаковых результат сдвига вправо определяется реализацией. Поэтому при битовых операциях всегда используют беззнаковые типы (unsigned), чтобы избежать неопределённого поведения и получить предсказуемый логический сдвиг.
Вопрос 15. Битовые поля (bit fields) в структурах. Их назначение. Пример структуры с битовыми полями и объяснение экономии памяти.
Битовые поля позволяют задать членам структуры размер в битах. Назначение — экономия памяти и удобная работа с аппаратными регистрами или протоколами. Пример:
```c
struct Flags {
unsigned int ready : 1;
unsigned int error : 2;
unsigned int data : 5;
};
```
Здесь ready занимает 1 бит, error — 2 бита, data — 5 битов. Вместо 3 * 4 = 12 байт (int) структура займёт, скорее всего, 4 байта (одно int). Экономия существенна при большом количестве флагов.
---
Собственный аллокатор памяти
Вопрос 16. Аллокатор памяти. Его основные задачи. Ситуации, в которых может потребоваться написание собственного аллокатора вместо использования стандартного malloc.
Аллокатор управляет кучей: выделяет, освобождает блоки, отслеживает свободные области. Задачи: уменьшение фрагментации, повышение производительности, учёт использования памяти. Собственный аллокатор пишут, когда: 1) стандартный malloc слишком медленный для real-time систем; 2) нужна специальная стратегия (например, пул объектов фиксированного размера); 3) требуется отладочная информация (стек вызовов выделения); 4) работа в среде без ОС (встраиваемые системы).
Вопрос 17. Фрагментация памяти. Отличия внутренней фрагментации от внешней. Роль слияния (coalescing) блоков в борьбе с фрагментацией.
Внутренняя фрагментация — неиспользуемая память внутри выделенного блока (например, malloc выделил 24 байта под 17 байт из-за выравнивания). Внешняя — мелкие свободные участки между занятыми блоками, которые не могут удовлетворить крупный запрос, хотя суммарно памяти достаточно. Слияние (coalescing) — объединение соседних свободных блоков в один большой при освобождении, что уменьшает внешнюю фрагментацию.
Вопрос 18. Стратегии поиска свободного блока (First-Fit, Best-Fit, Worst-Fit, Next-Fit). Преимущества и недостатки каждой стратегии.
· First-Fit — первый подходящий блок. Быстрый, но может создать много мелких фрагментов в начале.
· Best-Fit — блок, наилучшим образом подходящий по размеру (минимальный из достаточных). Минимизирует остаток, но медленнее поиск.
· Worst-Fit — самый большой блок. Оставляет большие остатки, редко используется.
· Next-Fit — продолжает поиск с места последнего выделения. Равномернее распределяет, но может быть медленнее First-Fit.
---
Файловая система
Вопрос 19. Дескриптор (HANDLE) в Windows. Причина, по которой все операции с файлами в Windows API выполняются через дескрипторы, а не напрямую через имена файлов.
Дескриптор (HANDLE) — это абстрактный указатель на объект ядра (файл, процесс, семафор). Причина использования дескрипторов: они обеспечивают уровень косвенности. Ядро хранит для каждого процесса таблицу дескрипторов, где хранятся права доступа, режим открытия, позиция в файле и т.д. Это позволяет безопасно передавать доступ к объекту между процессами (дублирование дескриптора), контролировать закрытие (CloseHandle) и не зависеть от имени файла после открытия.
Вопрос 20. Функция CreateFile для открытия файла. Основные параметры (dwDesiredAccess, dwShareMode, dwCreationDisposition, dwFlagsAndAttributes) и их значение.
CreateFile возвращает HANDLE. Параметры:
· dwDesiredAccess — режим доступа: GENERIC_READ, GENERIC_WRITE, GENERIC_ALL.
· dwShareMode — совместный доступ: FILE_SHARE_READ, FILE_SHARE_WRITE, FILE_SHARE_DELETE (0 — эксклюзивный).
· dwCreationDisposition — действие: CREATE_NEW (создать новый, ошибка если есть), CREATE_ALWAYS (перезаписать), OPEN_EXISTING (открыть существующий), OPEN_ALWAYS (открыть или создать), TRUNCATE_EXISTING (обрезать до нуля).
· dwFlagsAndAttributes — флаги и атрибуты: FILE_ATTRIBUTE_NORMAL, FILE_FLAG_OVERLAPPED (асинхронный ввод-вывод), FILE_FLAG_DELETE_ON_CLOSE и др.
Вопрос 21. Рекурсивный обход папок в Windows. Функции для поиска файлов. Специальные записи "." и ".." и их значение.
Для поиска файлов используются FindFirstFile, FindNextFile, FindClose. Структура WIN32_FIND_DATA содержит имя файла и атрибуты. Рекурсивный обход: при нахождении каталога (атрибут FILE_ATTRIBUTE_DIRECTORY) нужно проверить, что имя не равно "." и "..", и затем войти в него рекурсивно. "." означает текущий каталог, ".." — родительский. Они используются для навигации, но обход дерева должен их пропускать, чтобы не зациклиться.
Вопрос 22. Атрибуты файлов в Windows (FILE_ATTRIBUTE_READONLY, HIDDEN, SYSTEM, DIRECTORY и другие). Способ получения атрибутов файла программно.
Основные атрибуты: READONLY (только чтение), HIDDEN (скрытый), SYSTEM (системный), DIRECTORY (каталог), ARCHIVE (архивный), COMPRESSED (сжатый). Получить атрибуты можно с помощью функции GetFileAttributes (возвращает DWORD битовую маску) или через GetFileAttributesEx. Установить атрибуты — SetFileAttributes.
---
Форматы данных JSON и CSV
Вопрос 23. Основные отличия форматов CSV и JSON. Случаи, когда лучше использовать CSV, а когда — JSON. Примеры.
CSV — табличный формат, строки и столбцы, нет вложенности. JSON — иерархический, поддерживает объекты, массивы, различные типы (числа, строки, булевы, null). CSV лучше для простых табличных данных, больших объёмов (экономнее), для импорта/экспорта в Excel. JSON лучше для сложных структур, API, конфигураций, когда нужна вложенность и типы данных. Пример CSV: список пользователей (id,name). Пример JSON: { "user": { "name": "Ivan", "addresses": [...] } }.
Вопрос 24. Парсинг. Этапы процесса парсинга структурированных данных (лексический анализ, синтаксический анализ, семантический анализ, валидация).
1. Лексический анализ (токенизация) — разбивает входной поток на токены (числа, строки, скобки, ключевые слова). 2. Синтаксический анализ — строит дерево разбора (AST) по правилам грамматики, проверяет порядок токенов. 3. Семантический анализ — проверяет смысловые правила (например, тип данных, что переменная определена). 4. Валидация — проверка соответствия данным правилам предметной области (например, возраст не отрицательный). В парсинге JSON/CSV часто валидация объединяется с синтаксическим анализом.
---
Хеш-таблицы
Вопрос 25. Хеш-таблица. Основные операции и их средняя и худшая временная сложность. Причина возможного худшего случая O(n).
Хеш-таблица поддерживает вставку, удаление, поиск по ключу. Средняя сложность — O(1) (при хорошей хеш-функции и низкой заполненности). Худшая — O(n), когда все ключи попадают в одну корзину (коллизии), например, из-за плохой хеш-функции или злонамеренных данных. В худшем случае поиск превращается в линейный по списку коллизий.
Вопрос 26. Коллизия в хеш-таблице. Метод цепочек (chaining) для разрешения коллизий. Способ реализации.
Коллизия — когда разные ключи дают одинаковый хеш-индекс. Метод цепочек: каждая ячейка массива является указателем на связный список (или другую структуру) элементов, попавших в эту ячейку. При вставке элемент добавляется в список, при поиске — проходим по списку, сравнивая ключи. Реализация: массив Node** table, каждый узел содержит ключ, значение и указатель на следующий. При удалении — удаляем из списка.
---
Деревья
Вопрос 27. Дерево как структура данных. Определения основных терминов: корень, лист, родитель, потомок, поддерево, высота дерева.
Дерево — иерархическая структура из узлов и рёбер. Корень — узел без родителя. Лист — узел без потомков. Родитель — узел, имеющий потомков. Потомок — узел, связанный с родителем. Поддерево — часть дерева, состоящая из узла и всех его потомков. Высота дерева — максимальное количество рёбер от корня до листа (или количество уровней; бывают определения с 0 или 1). Обычно высота пустого дерева -1 или 0.
Вопрос 28. Рекурсивный обход дерева. Отличия обхода в глубину (DFS) от обхода в ширину (BFS). Задачи для каждого типа обхода.
DFS (обход в глубину) — идём вниз до листа, потом возвращаемся. Реализуется рекурсивно или через стек. Виды: прямой (pre-order), симметричный (in-order), обратный (post-order). BFS (обход в ширину) — обход по уровням, использует очередь. DFS хорош для поиска пути, копирования дерева, вычисления высоты. BFS — для поиска кратчайшего пути (в графах, где рёбра равны), печати по уровням, поиска ближайшего узла.
---
Внешняя сортировка
Вопрос 29. Проблема сортировки данных, не помещающихся в оперативную память. Алгоритм внешней сортировки слиянием (External Merge Sort): фаза формирования отрезков (runs) и фаза многопутевого слияния (K-way merge).
Проблема: данные больше доступной RAM. Решение — внешняя сортировка. Фаза 1: чтение блока данных, сортировка его в памяти (например, qsort), запись во временный файл — получаем отсортированные отрезки (runs). Фаза 2: многопутевое слияние — одновременно открываем K файлов с runs, выбираем наименьший элемент среди первых элементов каждого run (с помощью min-кучи), записываем в выходной файл. Повторяем, пока не сольём все runs в один отсортированный файл.
---
Процессы
Вопрос 30. Процесс и поток. Их отличия. Создание дочернего процесса в Windows с помощью функции CreateProcess. Ожидание завершения дочернего процесса и получение его кода возврата.
Процесс — это экземпляр выполняемой программы, имеет своё виртуальное адресное пространство, дескрипторы, контекст безопасности. Поток — единица выполнения внутри процесса, разделяет память и ресурсы процесса, имеет свой стек и регистры. Отличия: процессы изолированы, переключение между процессами дороже, чем между потоками. В Windows для создания дочернего процесса используется CreateProcess (передаётся имя исполняемого файла, командная строка, параметры безопасности, флаги). Чтобы ожидать завершения, вызывают WaitForSingleObject(hProcess, INFINITE). Код возврата получают через GetExitCodeProcess(hProcess, &exitCode). Затем закрывают дескриптор CloseHandle(hProcess).