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

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

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

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

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

Что содержит каждый узел двусвязного списка?

1. AДве копии данных и один указатель
2. BДанные, указатель на следующий узел и указатель на предыдущий узел
3. CДанные и два указателя: один на следующий узел и один на узел после него
4. DДанные и только указатель на следующий узел

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

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

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

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

1. A2^h+1 − 1
2. B2h + 1
3. C2^h
4. Dh²

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

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

1. AОчередь (или любая коллекция) вершин с полустепенью захода 0
2. BМатрица смежности, фиксирующая, какие вершины уже удалены
3. CСтек всех посещённых рёбер
4. DMax-куча, упорядоченная по полустепени исхода