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

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

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

В односвязном списке каждый узел содержит:

1. AДанные и ссылки на все остальные узлы
2. BДанные и индекс
3. CТолько данные
4. DДанные и ссылку на следующий узел

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

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

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

1. Ai/2 и i/2 + 1
2. B2i + 1 и 2i + 2
3. Ci + 1 и i + 2
4. D2i и 2i + 1

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. Ai + 1
2. B(i − 1) mod n
3. C2i + 1
4. D(i + 1) mod n

Префиксное дерево (trie) особенно эффективно для:

1. AПоиска по префиксу, например автодополнения
2. BХранения матриц
3. CСортировки чисел
4. DПоиска кратчайших путей

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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