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

Какая операция медленная в массиве, но быстрая в начале связного списка?

1. AВставка в начало
2. BОпределение длины массива фиксированного размера
3. CДоступ к 5-му элементу
4. DЧтение последнего элемента по индексу

Что делает операция peek (или top) стека?

1. AУдаляет все элементы из стека
2. BВозвращает верхний элемент, не удаляя его
3. CУдаляет верхний элемент и возвращает его
4. DВозвращает нижний элемент стека

Что такое дек (deque, двусторонняя очередь)?

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

Как вставляется новый элемент в двоичную кучу?

1. AЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
2. BЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
3. CЕго помещают в корень и опускают вниз
4. DВсю кучу перестраивают с нуля

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

1. A2i + 1
2. B(i − 1) mod n
3. C(i + 1) mod n
4. Di + 1

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

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

Для чего используется структура union-find в алгоритме Краскала построения минимального остовного дерева?

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

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

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