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

Что такое лист дерева?

1. AУзел ровно с одним потомком
2. BУзел без родителя
3. CУзел с наибольшим значением
4. DУзел без потомков

Что делает хеш-функция в хеш-таблице?

1. AШифрует значения в таблице
2. BОтображает ключ в индекс таблицы
3. CПодсчитывает, сколько ключей хранится
4. DСортирует ключи в таблице

Где находится наименьший элемент двоичной min-кучи?

1. AВ каком-то листе, который придётся искать
2. BВ самом левом листе
3. CВ корне
4. DВ последней позиции массива

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

1. AСтек
2. BОчередь FIFO
3. CОчередь с приоритетом по минимуму
4. DМножество без упорядочения

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

1. A50
2. B40
3. C20
4. D70

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

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

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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