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

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

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

Сколько рёбер в дереве с n узлами?

1. An + 1
2. B2n
3. Cn − 1
4. Dn

Что такое степень вершины в неориентированном графе?

1. AЧисло вершин графа
2. BДлина самого длинного пути из неё
3. CЕё позиция в списке смежности
4. DЧисло инцидентных ей рёбер

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AВсегда его правый потомок
2. BВсегда его родитель
3. CСамый левый узел его правого поддерева
4. DСамый правый узел его левого поддерева

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

1. AВ кучах никогда не бывает больше 100 элементов
2. BМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны
3. CВсе ключи в куче равны
4. DЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

1. AКучу
2. BСтек
3. CТолько хеш-таблицу
4. DОчередь

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

1. AОтображение выбрасывает ошибку в момент изменения поля
2. BНичего не меняется, потому что хеш ключа вычисляется только один раз при запуске программы
3. CПоиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
4. DОтображение автоматически переносит ключ в новую корзину

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

1. AОно сортирует потомков каждого узла по частоте
2. BОно хранит только первую букву каждого слова
3. CОно сливает цепочки узлов с одним потомком в одно ребро, помеченное строкой
4. DОно хранит каждое слово в хеш-таблице в корне вместо отдельных узлов