Тест по информатике по теме: алгоритмы и структуры данных

Тема 3. Связные и кольцевые списки

1

Какое преимущество связного списка перед массивом?

динамическое изменение размера

быстрый доступ по индексу

меньший расход памяти

Связные списки позволяют динамически изменять размер, вставлять и удалять элементы без сдвига всех остальных, в отличие от массивов фиксированного размера

При удалении элемента из кольцевого списка

список разрывается

в списке образуется дыра

список становится короче на один элемент

Удаление узла просто сокращает список на один элемент, при этом сохраняется кольцевая структура

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

данные, указатель на следующий, указатель на предыдущий

только данные

только один указатель

Двусвязный узел содержит данные и два указателя: на следующий и предыдущий элементы, что позволяет двустороннюю навигацию

Зачем в кольцевых списках используется sentinel-узел?

для упрощения обработки граничных случаев

для хранения дополнительной информации

для ускорения поиска по индексу

Sentinel-узел упрощает обработку граничных случаев, таких как вставка или удаление первого и последнего узла, без дополнительных проверок

Что происходит при вставке нового элемента в начало односвязного списка?

новый элемент указывает на старый первый

новый элемент указывает на NULL

все элементы сдвигаются

Новый элемент указывает на старый первый узел, сохраняя последовательность и корректную работу списка

Как создать новый элемент списка с информационным полем D?

p = getnode

p = getnode;
info(p) = D

p = getnode;
ptr = lst

Сначала выделяется память для узла через getnode, затем в поле info(p) помещается значение D, что обеспечивает корректное хранение данных

В чём недостаток односвязного списка по сравнению с двусвязным?

невозможно эффективно перемещаться назад

занимает больше памяти

сложнее реализовать вставку в начало

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

Для чего используется указатель в кольцевых списках?

для ссылки на следующий элемент

для запоминания номера сегмента расположения элемента

для ссылки на предыдущий элемент

для расположения элемента в списке памяти

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

Какова сложность поиска элемента в односвязном списке?

O(n)

O(1)

O(log n)

Поиск в односвязном списке требует пройти элементы по порядку, что даёт сложность O(n)

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

1

2

сколько угодно

Для односвязного кольцевого списка достаточно одного указателя на следующий элемент, чтобы организовать циклическую структуру

Где находится конец у кольцевого списка?

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

последний элемент указывает на NULL

зависит от реализации

У кольцевого списка нет конца: последний узел ссылается на первый, создавая замкнутую структуру

В каких направлениях можно перемещаться в кольцевом двунаправленном списке?

в обоих

влево

вправо

Двусвязный кольцевой список позволяет перемещаться как вперёд, так и назад, используя два указателя: на следующий и на предыдущий узел

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

двусвязный

массив

стек

Двусвязный список позволяет вставлять элементы в середину за O(1), используя указатели на соседние узлы

Где удобнее всего использовать кольцевой список?

в циклических очередях и повторяющихся процессах

в стековых вычислениях

в индексных таблицах

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

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

p = getnode

ptr(p) = nil

freenode(p)

p = lst

Операция freenode(p) освобождает память, занятую узлом, предотвращая утечки памяти при работе со связными структурами

Как создать пустой элемент с указателем p?

p = getnode

info(p)

freenode(p)

ptr(p) = lst

Операция p=getnode выделяет память для нового узла и инициализирует указатель, готовя элемент к дальнейшему использованию

Чем отличается кольцевой список от линейного?

в кольцевом списке последний элемент является одновременно и первым

в кольцевом списке указатель последнего элемента пустой

в кольцевых списках последнего элемента нет

в кольцевом списке указатель последнего элемента не пустой

В кольцевом списке последний элемент ссылается на первый, создавая замкнутую структуру без начала и конца

Сколько указателей используется в конструкции узла односвязного списка?

1

2

сколько угодно

Односвязный список содержит один указатель next, который указывает на следующий узел, обеспечивая линейную последовательность элементов

Что произойдёт, если в кольцевом списке потерять указатель на голову?

доступ ко всему списку становится невозможным

список сам восстановится

создастся новый список

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

loading...