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

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (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Двоичная куча рёбер

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

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

1. AВ индексе 2i + 1
2. BВ индексе ⌊i / 2⌋ + 1
3. CВ индексе ⌊(i − 1) / 2⌋
4. DВ индексе i − 1

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

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

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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