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

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

Где находится наименьший элемент двоичной min-кучи?

1. AВ последней позиции массива
2. BВ каком-то листе, который придётся искать
3. CВ самом левом листе
4. DВ корне

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

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

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

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

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

1. AO(n)
2. BO(n log n)
3. CO(1)
4. DO(log n)

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

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

Дерево отрезков (segment tree) обычно используют для:

1. AСортировки строк по алфавиту путём хранения каждого префикса в отдельном узле дерева
2. BРеализации стека
3. CХранения рёбер графа
4. DОтветов на запросы на диапазонах (например, суммы диапазонов) и обновлений за O(log n)

Какое утверждение о пирамидальной сортировке (heapsort) верно?

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