Тест: Структуры данных и алгоритмы

Стек лучше всего подходит для доступа LIFO. Очереди лучше всего подходят для доступа FIFO (First In, First Out).

O(1) представляет собой постоянную временную сложность. Это означает, что алгоритм всегда занимает одинаковое время выполнения, независимо от размера входных данных.

Если счётчик длины не хранится, чтобы вычислить длину односвязного списка, необходимо пройти каждый узел от головы до хвоста, что приводит к временной сложности O(n).

В сбалансированном BST средняя временная сложность поиска составляет O(log n), потому что на каждом уровне пространство поиска уменьшается вдвое.

Merge Sort всегда работает с худшей сложностью O(n log n), так как он неоднократно делит массив пополам и объединяет отсортированные подмассивы.

BFS использует очередь для обхода узлов уровень за уровнем, обрабатывая их в порядке ширины (по “строке”).

Поиск в глубину (DFS) обычно используется для обнаружения циклов в графе, поддерживая стек рекурсии для отслеживания посещённых узлов.

Сортировка кучей сохраняет худшую временную сложность O(n log n), так как она строит кучу и многократно извлекает максимальный элемент.

Хеш‑таблицы имеют среднюю временную сложность O(1) при доступе к элементам, при условии хорошей хеш‑функции, минимизирующей коллизии.

Основные операции стека — Push (добавление элемента), Pop (удаление элемента) и Peek (просмотр верхнего элемента без его удаления).

Алгоритм Дейкстры часто применяется для нахождения кратчайшего пути в графах с неотрицательными весами ребер. Он использует приоритетную очередь для эффективного определения минимального расстояния.

AVL‑деревья и красно‑черные деревья являются типами самобалансирующихся деревьев, которые гарантируют, что дерево остаётся сбалансированным после каждой вставки или удаления.

Базовый случай необходим в рекурсивной функции, чтобы остановить рекурсивные вызовы, когда выполнено определённое условие, предотвращая бесконечную рекурсию.

Две основные операции в очереди — Enqueue (добавление элемента в конец) и Dequeue (удаление элемента из начала).

Топологическую сортировку можно выполнить над графом, если он ориентирован и ацикличен (DAG). Такой порядок полезен в задачах планирования выполнения.

Наивная рекурсивная реализация последовательности Фибоначчи имеет временную сложность O(2^n) из‑за обширных повторных вычислений для каждого числа Фибоначчи.

Приоритетная очередь обычно реализуется с помощью кучи, потому что она обеспечивает эффективное извлечение элемента с наивысшим или наименьшим приоритетом.

In-order, Pre-order и Post-order — это три распространённых порядка обхода в глубину для бинарных деревьев, каждый из которых отличается порядком посещения узлов. Обход в ширину также распространён, но относится к другой категории обходов.

В min-heap корень всегда является наименьшим элементом, а высота дерева O(log n), что делает вставку и извлечение эффективными.

Такая пузырьковая сортировка устойчива: элементы с равными ключами не меняются местами и сохраняют относительный порядок. Вариант, меняющий местами равные элементы, может нарушить устойчивость.