Структуры данных: тренировочные вопросы с объяснениями

1Что такое структура данных

Структура данных — это способ организации данных в памяти, при котором определённые операции выполняются быстро: найти элемент, добавить его, удалить.

Нет структуры, которая быстра во всём. Выбрать структуру — значит выбрать, какие операции должны быть дешёвыми. Их стоимость записывают в Big O, где n — число элементов.

Два базовых строительных блока — массив и связный список.

Массив хранит элементы в одном блоке памяти, один за другим. Компьютер может вычислить, где находится элемент i, поэтому чтение a[i] занимает O(1). Вставка в начало означает сдвиг каждого элемента: O(n).

Связный список хранит каждый элемент в узле с указателем на следующий узел. Последний указатель равен null. Вставка в голову (h) меняет только один указатель: O(1). Но чтобы добраться до элемента i, нужно пройти i указателей: O(n).

Двусвязный список имеет также указатель на предыдущий узел, поэтому по нему можно идти в обе стороны.

2Стеки и очереди

Стек похож на стопку тарелок: добавлять и убирать можно только сверху. Последним вошёл — первым вышел: LIFO.

• push кладёт элемент наверх, pop убирает верхний элемент, peek читает верхний, не убирая его. Все операции выполняются за O(1).
• Применение: функция отмены в редакторе, стек вызовов программы, проверка баланса скобок, поиск в глубину.

Очередь похожа на очередь у кассы: встают в конец, а уходят из начала. Первым вошёл — первым вышел: FIFO.

• enqueue добавляет в конец, dequeue убирает из начала. Обе операции выполняются за O(1).
• Применение: задания печати, сообщения, ожидающие обработки, поиск в ширину.

Дек (двусторонняя очередь) допускает добавление и удаление с обоих концов. Очередь с приоритетом всегда первым убирает элемент с наивысшим приоритетом; обычно её строят на основе кучи.

3Деревья, кучи, хеш-таблицы и графы

У дерева есть один верхний узел — корень. У каждого другого узла ровно один родитель. Узлы без потомков — листья. В дереве с n узлами n − 1 рёбер.

В двоичном дереве у каждого узла не более двух потомков. Двоичное дерево поиска (BST) добавляет правило: ключи в левом поддереве меньше ключа узла, ключи в правом поддереве больше.

Поиск в BST идёт по одному пути вниз, поэтому стоит O(высота). Сбалансированное дерево (AVL, красно-чёрное) держит высоту около log₂ n. Ключи, вставленные в отсортированном порядке, образуют цепочку высотой n.

Куча — это двоичное дерево, в котором каждый родитель меньше своих потомков (min-куча) или больше (max-куча). Минимум или максимум находится в корне, а вставка и удаление стоят O(log n).

Хеш-таблица хранит пары «ключ — значение». Хеш-функция превращает ключ в индекс, поэтому вставка и поиск в среднем занимают O(1). Два ключа с одним индексом образуют коллизию, которую решают цепочками (список в каждой ячейке) или открытой адресацией (пробуют другую ячейку).

У графа есть вершины, соединённые рёбрами, которые могут иметь направление или вес. Его хранят в виде матрицы смежности, O(V²) памяти, или списков смежности, O(V + E).

4Метод по шагам

Вопросы часто описывают задачу и спрашивают, какая структура подходит, или спрашивают, как выглядит структура после некоторых операций.

1. Найдите операцию, которая должна быть быстрой: доступ по позиции, по ключу, к новейшему элементу, к самому старому, к наименьшему или к диапазону.
2. Сопоставьте её со структурой: индекс → массив, ключ → хеш-таблица, новейший → стек, самый старый → очередь, наименьший или наибольший → куча, отсортированный порядок или диапазоны → сбалансированное дерево поиска.
3. Проверьте в Big O стоимость остальных операций, нужных для задачи.
4. Для вопроса на трассировку выполняйте операции по одной и записывайте состояние после каждой.
5. Сверьте итоговое состояние с правилом структуры: LIFO, FIFO, порядок BST или порядок кучи.

5Разобранный пример

Пройдите каждый шаг. Попробуйте предсказать следующий, прежде чем открыть его.

6Типичные ошибки

• Путать LIFO и FIFO. Стек возвращает новейший элемент, очередь — самый старый.
• Думать, что связный список даёт быстрый доступ по индексу. Ему приходится идти от головы.
• Считать, что BST всегда работает за O(log n). Это верно только для сбалансированного дерева; вставка отсортированных ключей даёт O(n).
• Забывать о коллизиях в хеш-таблице. O(1) — это в среднем, а не в худшем случае.
• Путать обходы. Прямой: сначала узел. Симметричный: узел посередине. Обратный: узел последним.
• Использовать матрицу смежности для большого разреженного графа. Она впустую тратит O(V²) памяти.

7Как выглядят экзаменационные задачи

• Лёгкая: ключевые термины и факты. LIFO и FIFO, что такое узел, корень или лист, правило BST, что делает хеш-функция.
• Средняя: применение понятий. Какая структура подходит для задачи, результат push и pop или вставок в BST, обходы деревьев, хеш-таблица с линейным пробированием, стоимость в Big O.
• Сложная: случаи и анализ. Сбалансированные деревья, кучи в массивах, B-деревья, префиксные деревья (tries), система непересекающихся множеств (union-find), фильтры Блума и конструкции вроде LRU-кеша.

Для кучи, хранящейся в массиве с индекса 0, потомки элемента с индексом i находятся на позициях 2i + 1 и 2i + 2, а его родитель — на ⌊(i − 1) / 2⌋.