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

Как называется операция стека, добавляющая элемент на вершину?

1. AEnqueue
2. BPop
3. CPush
4. DPeek

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

1. An + 1
2. B2n
3. Cn − 1
4. Dn

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

1. An (дерево превращается в связный список)
2. Blog₂ n
3. C√n
4. D1

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

1. AСписки смежности
2. BДвоичная куча рёбер
3. CОдин отсортированный массив вершин
4. DМатрица смежности

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

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

Каково время работы поиска в ширину на графе с V вершинами, хранящемся в виде матрицы смежности?

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

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

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