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

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

1. An
2. Bn + 1
3. C2n
4. Dn − 1

Высота дерева обычно определяется как:

1. AЧисло рёбер на самом длинном пути от корня до листа
2. BЧисло листьев в дереве
3. CЧисло потомков корня
4. DОбщее число узлов в дереве, считая корень и каждый лист

Что такое дек (deque, двусторонняя очередь)?

1. AОчередь, допускающая удаление только с конца
2. BСтруктура, допускающая вставку и удаление с обоих концов
3. CДве отдельные очереди в одном массиве
4. DОчередь, отсортированная по приоритету

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

1. AO(V + E)
2. BO(V²)
3. CO(V × E)
4. DO(E²)

Кольцевой буфер (ring buffer) обычно используют для реализации:

1. AОбхода графа
2. BОчереди фиксированного размера
3. CХеш-функции
4. DДвоичного дерева поиска

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

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

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

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

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

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