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

В чём главное отличие статического массива от динамического?

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

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

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

Что определяет двоичное дерево?

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

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

1. A5 4 3 2 1
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 4 5 3

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

1. A2i + 1 и 2i + 2
2. Bi + 1 и i + 2
3. C2i и 2i + 1
4. Di/2 и i/2 + 1

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

Как определить, есть ли цикл в односвязном списке, используя O(1) дополнительной памяти?

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

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

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