Как устроен экзамен по блоку 2 «Файлы, функции, рекурсия, динамическая память» и как к нему подготовиться
| Что | Условие |
|---|---|
| Допуск | практические работы №12–17 сданы не ниже «удовлетворительно» (50 баллов из 100) |
| Тест | 20 вопросов из банка по разделам 14–18, 30 минут, 40 % оценки |
| Практическая задача | одна задача по билету на материале практических работ №12–17, 45 минут, 60 % оценки; после сдачи — короткое устное объяснение |
| Оценка за блок | тест (0–100) · 0,4 + задача (0–100) · 0,6 |
| Итог | Оценка |
|---|---|
| 85–100 | «отлично» |
| 70–84 | «хорошо» |
| 50–69 | «удовлетворительно» |
| менее 50 | «неудовлетворительно» |
Шкала та же, что у экзамена по блоку 1 и у каждой практической работы.
Вопросы — того же вида, что в тестах разделов, но не повторяют их: «что выведет фрагмент», «чему равно», выбор структуры данных под задачу, причина ошибки. Подготовка — пройти ещё раз тесты разделов 14–18, разобрать свои ошибки и проследить на бумаге примеры со страниц.
| Раздел | Главное для теста |
|---|---|
| 14 | режимы rb, wb, r+b, ab; результат fread/fwrite; смещение записи и fseek/ftell, в том числе от конца; размер структуры и порядок байтов числа в файле |
| 15 | static-локальные, передача по значению и через указатель, массив в параметре, адрес локальной переменной, указатели на функции, функция сравнения для qsort |
| 16 | трассировка рекурсии (порядок вывода, число вызовов), глубина и стек, мемоизация, слияние и быстрая сортировка — сложность, устойчивость, опорный, перебор с возвратом |
| 17 | malloc/realloc/free и четыре ошибки памяти, рост вдвое, список (вставка, удаление, разворот), стек и очередь, кольцевой буфер, ОПН и скобки, выбор структуры под задачу |
| 18 | заголовок и реализация, include guard, static и extern вне функций, ошибки компоновки, Makefile и что он пересоберёт, статическая библиотека |
По пять билетов на каждую практическую работу №12–17 — задачи разного типа на одном материале. Студенты одной подгруппы получают билеты по разным работам.
| Материал | Билеты и темы |
|---|---|
| ПЗ №12, двоичный файл записей | 1 — запись чисел и чтение по индексу; 7 — обмен двух записей на месте; 13 — счётчик запусков в файле; 19 — двоичный поиск в файле; 25 — обращение файла на месте |
| ПЗ №13, побайтовая обработка | 2 — статистика байтов; 8 — XOR, единичные биты, самая длинная серия; 14 — склейка файлов; 20 — поиск последовательности байтов; 26 — хвост файла в шестнадцатеричном виде |
| ПЗ №14, сортировки | 3 — устойчивая сортировка слов слиянием; 9 — быстрая с медианой трёх и счётом сравнений; 15 — сортировка по двум ключам qsort; 21 — быстрый выбор k-го; 27 — сочетания перебором с возвратом |
| ПЗ №15, динамический массив | 4 — числа выше среднего; 10 — слияние двух строк чисел; 16 — текстовый буфер без лишних пробелов; 22 — гистограмма; 28 — удаление строки матрицы в одном блоке |
| ПЗ №16, связный список | 5 — удаление каждого второго узла; 11 — разделение на чётные и нечётные; 17 — удаление повторов; 23 — пересечение упорядоченных списков; 29 — сжатие серий |
| ПЗ №17, стек и очередь | 6 — системы счисления стеком; 12 — скользящее среднее на кольцевом буфере; 18 — упрощение пути Unix; 24 — числа Хэмминга тремя очередями; 30 — вычеркнуть цифры, чтобы число стало наименьшим |
Полные условия, примеры и критерии — на портале. Задача — одна программа на 45 минут; разрешено пользоваться страницами курса и своими практическими работами. Держите под рукой готовые части: read_record/write_record и разбор команд (ПЗ №12), цикл fgetc с int c (ПЗ №13), сортировки и функцию сравнения (ПЗ №14), push с ростом вдвое (ПЗ №15), вставку в конец через указатель на последнюю ссылку и free_list (ПЗ №16), стек и очередь с кодами ошибок (ПЗ №17).
-fsanitize=address, если есть malloc. 5 минут — перечитать: проверки fopen и malloc, free и fclose на всех путях, границы циклов.Билет: целые до конца ввода — в список в порядке ввода; удалить 2-й, 4-й, … узлы за один проход, освобождая их; вывести список до и после и число удалённых. Пример: 1 2 3 4 5 → 1 3 5, удалено 2.
Node **tail (раздел 17, ПЗ №16), print_list, free_list с сохранением next до free.p, удаляем p->next: сначала перецепляем ссылку, затем освобождаем; следующим рассматривается узел, ставший p->next, — он нечётный и остаётся./* Вернуть число удалённых */
int remove_every_second(Node *head)
{
int removed = 0;
for (Node *p = head; p != NULL && p->next != NULL; p = p->next) {
Node *victim = p->next;
p->next = victim->next; /* перецепить, затем освободить */
free(victim);
removed++;
}
return removed;
}| Тест | Ожидается | Что проверяет |
|---|---|---|
| 1 2 3 4 5 | result: 1 3 5, removed 2 | пример билета, нечётная длина |
| 1 2 | result: 1, removed 1 | удаляется последний узел |
| 7; пустой ввод | 7, removed 0; пустой список | условие цикла не обращается к NULL->next |
| 1 2 x | сообщение об ошибке, код 1, список освобождён | проверка ввода, память на пути ошибки |
Устный вопрос может быть таким: «Что случится, если в цикле сначала вызвать free(victim), а потом p->next = victim->next?» — чтение поля освобождённого узла, неопределённое поведение; ASan сообщит heap-use-after-free (раздел 17, пункт 03).