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

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

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

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

1. APeek
2. BPush
3. CPop
4. DEnqueue

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

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

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

1. AМножество без упорядочения
2. BОчередь FIFO
3. CОчередь с приоритетом по минимуму
4. DСтек

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

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

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

1. A√n
2. B1
3. Clog₂ n
4. Dn (дерево превращается в связный список)

Почему B-деревья используются в базах данных и файловых системах?

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

Структура union-find (система непересекающихся множеств) с объединением по рангу и сжатием путей имеет амортизированную стоимость операции:

1. AO(α(n)), обратная функция Аккермана, практически константа
2. BO(n)
3. CРовно O(log n)
4. DO(n²)