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

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

1. ANull (узла нет)
2. BЧисло узлов в списке
3. CАдрес первого узла
4. DАдрес предыдущего узла

Хеш-таблица (hash table) хранит данные в виде:

1. AПар ключ–значение, расположение которых определяет хеш-функция
2. BСтроки фиксированной длины
3. CТолько отсортированного списка
4. DДерева с упорядоченными ключами

Что такое коллизия в хеш-таблице?

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

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

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

Что верно для матрицы смежности неориентированного графа?

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

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

1. AСамый правый узел его левого поддерева
2. BСамый левый узел его правого поддерева
3. CВсегда его правый потомок
4. DВсегда его родитель

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

1. AЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
2. BМеняют его местами с корнем
3. CПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
4. DУдаляют всё поддерево

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

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