C C · 25 вопросов · ~70 мин · ⏱ Таймер 10:00 · Средний ·

Структуры данных на C

Тест проверяет не названия списков и очередей, а их инварианты: удаление через указатель на указатель, переход индексов кольцевого буфера, передачу владения, уничтожение без обращения к освобождённой памяти и сравнение случайных последовательностей с эталонной моделью.

Отвечено: 0 из 25

⏱ --:--

💡 Инструкция: Выберите один ответ из пяти. На 25 вопросов отведено 70 минут. Код читайте построчно: часть заданий проверяет вывод, часть — поиск дефекта, переносимость и безопасное исправление. После завершения откроются объяснения и профиль по 5 темам.

Вопрос 1 из 25

Какова сложность вставки нового узла в начало односвязного списка, если известен указатель head?

node->next=*head; *head=node;

O(log n) Зависит от значений в узлах O(n) O(1) O(n²)

Вопрос 2 из 25

Почему при удалении узла удобно хранить указатель на указатель, ведущий к текущему узлу?

for(node **link=&head;*link;link=&(*link)->next){...}

Одна переменная может обозначать и `head`, и поле `next` предыдущего узла, поэтому замена выполняется одинаково Такой обход исключает `NULL` из промежуточных ссылок и позволяет не проверять окончание списка Указатель на указатель одновременно поддерживает сортировку: поле `next` обновляется в порядке значений Разыменование `node **` переносит следующий узел на место текущего без явного присваивания Адрес ссылки хранит предыдущий узел внутри отдельной служебной структуры, поэтому удаление требует меньше разыменований

Вопрос 3 из 25

Какой дефект есть в этом фрагменте удаления узлов?

free(cur);
cur=cur->next;

Список обязан быть массивом Не вызывается malloc Ошибка возникает только при prev==NULL После free(cur) программа читает cur->next free возвращает адрес следующего узла

Вопрос 4 из 25

Как обнаружить цикл в списке, используя O(1) дополнительной памяти?

slow=slow->next; fast=fast->next->next;

Выполнить двоичный поиск по адресам узлов, предполагая их порядок выделения распределителем Запоминать последний адрес и считать циклом любое уменьшение числового значения указателя Считать длину через `strlen((char *)head)` и сравнить её с числом посещённых узлов Сравнить байты всех узлов через `memcmp`; совпадение двух узлов означает возврат к прежней позиции Использовать медленный и быстрый указатели Флойда

Вопрос 5 из 25

Почему добавление в конец односвязного списка без сохранённого указателя на последний узел требует O(n) шагов?

Потому что каждое выделение одного узла имеет линейную сложность по длине списка Потому что поле `next` можно изменять только после полного обхода списка Без `tail` приходится пройти от головы до последнего узла Потому что односвязный список хранит элементы в непрерывном массиве Потому что перед вставкой адреса узлов необходимо отсортировать

Вопрос 6 из 25

Какое значение вернёт второй вызов pop после выполнения этого кода?

stack s={0};
push(&s,10); push(&s,20); push(&s,30);
(void)pop(&s);
printf("%d\n",pop(&s));

20 10 30 Второй вызов вернёт 10, если первый `pop` не обнуляет освобождённую ячейку массива Второй вызов завершится ошибкой, поскольку после первого извлечения стек считается пустым

Вопрос 7 из 25

В каком порядке очередь возвращает элементы, если после enqueue(4), enqueue(7), enqueue(9) выполнить три dequeue?

4, 7, 9 9, 7, 4 7, 9, 4 В порядке возрастания адресов Порядок не определён

Вопрос 8 из 25

Почему кольцевой буфер часто выгоднее связной очереди фиксированной ёмкости?

tail=(tail+1)%capacity;

Он поддерживает элементы отсортированными по значению при каждой вставке Он повторно использует массив и меняет индексы без выделения узла на каждую операцию Он выигрывает за счёт хвостовой рекурсии при извлечении очередного элемента Его ёмкость автоматически растёт без копирования или перераспределения памяти Он не требует проверять переполнение ёмкости и потому всегда принимает элемент

Вопрос 9 из 25

Как корректно различать пустой и полный кольцевой буфер, если в обоих случаях head может совпасть с tail?

Хранить индексы в знаковом типе и использовать отрицательный `head` как единственный признак заполнения Сравнивать значения ячеек `buf[head]` и `buf[tail]`; одинаковые данные означают пустой буфер Считать равенство индексов пустым состоянием после чтения и полным состоянием после записи без отдельного признака При совпадении индексов выделять новый массив, не сохраняя явное состояние полноты Хранить count, флаг полноты или оставлять один слот пустым

Вопрос 10 из 25

Какое предусловие нужно проверить до вычисления остатка в `next_index`?

size_t next_index(size_t tail, size_t capacity) {
    return (tail + 1) % capacity;
}

`errno == 0`, поскольку оператор `%` сообщает деление на ноль через `errno` `capacity` является степенью двойки, иначе оператор `%` неприменим `tail + 1 < SIZE_MAX`, но значение `capacity` проверять не требуется `capacity != 0`, чтобы делитель в операции остатка был ненулевым `tail < capacity`, поскольку допустимый хвост сам по себе исключает нулевую ёмкость

Вопрос 11 из 25

Что означает договорённость «контейнер владеет данными элементов»?

В узле не может быть указателя Данные обязаны находиться в стеке Вызывающий код обязан немедленно освободить данные Контейнер уничтожает данные при удалении элемента или себя Копирование элементов запрещено

Вопрос 12 из 25

Список хранит `void *` и может содержать данные разных типов. Как задать их освобождение?

typedef void (*destroy_fn)(void*);

Всегда вызывать `free`: любой `void *` в контейнере должен указывать на начало динамического блока Принять функцию уничтожения либо объявить данные заимствованными Определять способ уничтожения по результату `strlen`, считая ненулевую длину признаком строки Хранить рядом целочисленный код типа и освобождать данные после приведения указателя к этому целому типу Освобождать только узлы списка; данные разных типов нельзя включить в контракт владения контейнера

Вопрос 13 из 25

Что должен означать интерфейс `remove_take`, возвращающий указатель на данные удалённого узла?

Владельцем становится глобальная переменная Удалённый узел остаётся связанным со списком Контейнер сначала уничтожает данные и возвращает висячий указатель Функция всегда возвращает глубокую копию Владение данными переходит вызывающему коду, и контейнер их больше не уничтожает

Вопрос 14 из 25

Почему опасно надолго передавать наружу указатель на внутренний узел контейнера?

Указатель на узел всегда медленнее числового индекса независимо от структуры контейнера Проблема существует только у динамических массивов; адрес узла списка всегда остаётся действительным Само чтение узла меняет его адрес из-за работы распределителя памяти Удаление или реорганизация контейнера может освободить узел и превратить сохранённый адрес в висячий Внутренний узел по определению неизменяем, поэтому внешний код не сможет прочитать его поля

Вопрос 15 из 25

Что требуется для действительно глубокой копии обобщённого списка?

list *clone(const list *src, clone_fn c, destroy_fn d);

Сохранить исходные узлы и увеличить счётчик ссылок только у объекта списка, не у данных Клонировать все узлы, но разделить последний узел и функцию уничтожения между двумя списками Создать новые узлы, но оставить в них прежние указатели на данные; этого достаточно для глубокой копии списка Скопировать объект списка через `memcpy`, а затем заменить только поле `head` Клонировать узлы и данные, откатывая частичную копию при ошибке

Вопрос 16 из 25

Какой вариант корректно уничтожает список, если контейнер владеет данными каждого узла?

struct node {
    void *data;
    struct node *next;
};

void list_destroy(struct node *head, void (*destroy)(void *)) {
    /* выбрать тело */
}

`while(head){ struct node *next=head->next; destroy(head->data); free(head); head=next; }`while(n){ node *next=n->next; destroy(n->data); free(n); n=next; } `while(head){ destroy(head->data); free(head); free(head); }`while(n->next) n=n->next; `while(head){ free(head); destroy(head->data); head=head->next; }`while(n){ free(n); n=n->next; } `while(head){ struct node *next=head->next; free(head); head=next; }`free(head); `for(;head;head=head->next) destroy(head); free(head);`memset(n,0,sizeof n);

Вопрос 17 из 25

Стоит ли разрешить функции destroy принимать NULL как пустой контейнер?

Нет: передача `NULL` любой функции уничтожения является ошибкой языка независимо от контракта Разрешать `NULL` можно только после того, как ранее был выполнен успешный `malloc` Допустимо лишь при первом вызове; повторный `destroy(NULL)` должен считаться двойным освобождением Да, если интерфейс явно определяет `destroy(NULL)` как пустую и безопасную операцию Нет: само сравнение аргумента с `NULL` внутри функции уже вызывает неопределённое поведение

Вопрос 18 из 25

Почему простой цикл уничтожения непригоден для списка, в котором случайно образовался цикл?

while(n){ node *next=n->next; free(n); n=next; }

Обход завершится утечкой, но не сможет повторно прочитать или освободить уже уничтоженный узел После первого освобождения цикл в связях исчезнет, потому что распределитель обнулит поле `next` Квалификатор `const` автоматически появится у `head`, когда обход вернётся к исходному адресу Обход зациклится или повторно обратится к освобождённому узлу `free` обнаружит повторный адрес и завершит обход до второго освобождения узла

Вопрос 19 из 25

Конструктор списка не смог создать четвёртый узел. Что делать с уже созданными тремя?

Вернуть частично построенный список как успешный результат и сообщить о нехватке памяти только через `errno` Освободить лишь третий узел: предыдущие два образуют корректный самостоятельный список Установить код ошибки и оставить уже выделенные узлы вызывающей стороне без явного контракта Повторять выделение четвёртого узла без ограничения, пока распределитель не вернёт память Освободить все три уже созданных узла, оставить выходной указатель в оговорённом состоянии и вернуть ошибку

Вопрос 20 из 25

В каком порядке безопаснее удалять узел двусвязного списка?

if(n->prev)n->prev->next=n->next; else head=n->next;
if(n->next)n->next->prev=n->prev; else tail=n->prev;

Скопировать узел в соседний через `memcpy`, а исходный оставить в списке Сначала связать соседей и обновить границы, затем уничтожить данные и освободить узел Сначала всегда заменить `tail`, даже если удаляется внутренний узел Сначала освободить узел, затем прочитать из него `prev` и `next` для исправления связей Изменить только ссылку `prev->next`: обратная связь восстановится при следующем обходе

Вопрос 21 из 25

Какой инвариант полезно проверять у односвязного списка с сохранённым tail?

Пустой: оба `NULL`; непустой: `tail` достижим и его `next` равен `NULL` Все узлы обязаны идти в порядке возрастания адресов памяти `tail` всегда равен `NULL`, пока в списке меньше двух элементов Счётчик элементов должен быть отрицательным до первой вставки `head` и `tail` должны всегда указывать на один и тот же узел

Вопрос 22 из 25

Какой санитайзер компилятора непосредственно обнаруживает обращение к уже освобождённому узлу списка?

struct node *next = node->next;
free(node);
return node->value; /* обращение после free */

AddressSanitizer, сохраняющий метаданные освобождённой области и стек доступа Статический анализатор, видящий возможный путь к повторному использованию узла Valgrind Memcheck в режиме, где отслеживаются выделения и освобождения Пользовательский распределитель с карантином освобождённых блоков UBSan с проверками арифметики, но без инструментирования адресов кучи

Вопрос 23 из 25

Какое свойство удобно проверять при случайном тестировании очереди?

Результат должен быть случайным Функции не должны возвращать коды ошибок Сверять извлечения с эталонной FIFO-моделью Адреса элементов должны возрастать Достаточно проверять size >= 0

Вопрос 24 из 25

Чем полезна выгрузка повреждённой структуры в виде графа?

digraph { n1 -> n2; n2 -> n3; }

Она полностью заменяет отладчик: по структуре графа всегда можно восстановить строку кода, вызвавшую повреждение Она доказывает корректность структуры и полностью заменяет проверку инвариантов Она ускоряет компиляцию, исключая неиспользуемые вершины графа Она меняет раскладку структуры так, чтобы ошибка исчезла в следующем запуске Она наглядно показывает неверные ссылки, циклы и недостижимые узлы

Вопрос 25 из 25

Как сократить длинную случайную последовательность операций, воспроизводящую ошибку?

Удалять части последовательности, пока минимальный вариант всё ещё воспроизводит сбой Удалить зерно генератора, чтобы получить новую независимую последовательность Отключить проверки инвариантов, поскольку они мешают сокращению входа Повторить исходную последовательность один раз и считать её минимальной Сохранить всю последовательность: удаление любой операции делает тест недостоверным

Ответьте на все 25 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу