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

Что такое степень вершины в неориентированном графе?

1. AЕё позиция в списке смежности
2. BДлина самого длинного пути из неё
3. CЧисло вершин графа
4. DЧисло инцидентных ей рёбер

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

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

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

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

1. A2
2. B0,5
3. C1
4. DМаксимума нет

Чему равно значение постфиксного выражения 3 4 + 2 * ?

1. A14
2. B10
3. C11
4. D24

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

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

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

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

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

1. AОтсортированный массив всех n значений
2. BMax-куча размера k, корень которой заменяется, когда приходит меньшее значение
3. CОчередь FIFO последних k значений
4. DMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших