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

В двоичном дереве поиска значения в левом поддереве узла:

1. AМеньше значения узла
2. BБольше значения узла
3. CРавны значению узла
4. DРасположены в случайном порядке

Что такое цикл в графе?

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

Что такое свойство max-кучи?

1. AКлюч каждого родителя больше или равен ключам его потомков
2. BВсе листья содержат максимальный ключ
3. CКлюч каждого левого потомка больше или равен ключу его правого соседа
4. DКлючи отсортированы слева направо

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

1. A2i + 1 и 2i + 2
2. Bi + 1 и i + 2
3. Ci/2 и i/2 + 1
4. D2i и 2i + 1

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

1. AВ индексе 4
2. BВ индексе 0
3. CВ индексе 6
4. DВ индексе 3

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

1. AO(L × n)
2. BO(L), независимо от числа хранимых слов
3. CO(log n), где n — число слов
4. DO(n), где n — число слов

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

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

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

1. AНеобходимость в хеш-функции
2. BНеобходимость хранить ключи в таблице
3. CСтоимость O(n) чтения значения по ключу
4. DПервичную кластеризацию, при которой образуются длинные серии занятых ячеек