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

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

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

Что такое взвешенный граф?

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

Глубина узла в дереве — это:

1. AЧисло рёбер от корня до этого узла
2. BЧисло рёбер от этого узла до самого глубокого листа
3. CЧисло узлов в его поддереве
4. DЧисло потомков этого узла

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

1. A2^h+1 − 1
2. Bh²
3. C2^h
4. D2h + 1

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

1. AВ динамическом массиве
2. BВ двусвязном списке
3. CВ односвязном списке
4. DВ отсортированном массиве

Как вставляется новый элемент в двоичную кучу?

1. AВсю кучу перестраивают с нуля
2. BЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
3. CЕго помещают в корень и опускают вниз
4. DЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

1. AO(n log n)
2. BO(log n)
3. CO(1)
4. DO(n)

Что делает косое дерево (splay tree) после каждого обращения?

1. AПеремещает узел, к которому обращались, в лист
2. BПерекрашивает узлы на пути поиска
3. CПерестраивает всё дерево в сбалансированном виде
4. DПоворотами поднимает узел, к которому обращались, в корень