Структуры данных: лист заданий с ответами

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

1. ANull (узла нет)
2. BЧисло узлов в списке
3. CАдрес предыдущего узла
4. DАдрес первого узла

Какая операция медленная в массиве, но быстрая в начале связного списка?

1. AДоступ к 5-му элементу
2. BОпределение длины массива фиксированного размера
3. CВставка в начало
4. DЧтение последнего элемента по индексу

Какая структура данных работает по принципу «первым пришёл — первым ушёл» (FIFO)?

1. AБинарное дерево
2. BКуча
3. CСтек
4. DОчередь

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

1. A2h + 1
2. B2^h+1 − 1
3. Ch²
4. D2^h

Какую структуру данных использует выполняющаяся программа для отслеживания активных вызовов функций и их локальных переменных?

1. AДвоичное дерево поиска кадров
2. BСтек вызовов
3. CОчередь памяти кучи
4. DХеш-таблицу функций

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

1. AЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
2. BМассивы требуют меньше инструкций для сравнения значений
3. CСвязные списки всегда хранят элементы на диске
4. DОбход массива занимает в сумме O(1), а связного списка — O(n)

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

1. AПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
2. BЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
3. CУдаляют всё поддерево
4. DМеняют его местами с корнем

Структура union-find (система непересекающихся множеств) с объединением по рангу и сжатием путей имеет амортизированную стоимость операции:

1. AO(n²)
2. BO(α(n)), обратная функция Аккермана, практически константа
3. CO(n)
4. DРовно O(log n)