Расположите скорости роста от меньшей к большей при n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.

Асимптотически: 1 < log n < n < n log n < n² < 2ⁿ < n!.

Какие ответы может давать фильтр Блума, допускающий только вставки?

Отрицательный ответ означает, что элемент не вставляли; положительный — что могли вставить. Хеши устанавливают биты в массиве: ложноположительные ответы возможны, ложноотрицательные при неповреждённом состоянии — нет.

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

Все уровни заполнены, кроме, возможно, последнего, который заполняется слева. Ключ родителя не больше ключей детей. Поэтому корень содержит минимум.

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

При ограниченном заполнении, хорошем распределении хешей и постоянной стоимости операций с ключами поиск/удаление имеют ожидаемую стоимость O(1). Вставка при геометрическом росте имеет ожидаемую амортизированную стоимость O(1). Цепочка из n коллидирующих ключей может дать O(n).

Чем отличаются линейное и квадратичное пробирование при открытой адресации?

Записи остаются в массиве. При размере m и начальном индексе h проверяют соответственно (h+i) mod m и (h+c₁i+c₂i²) mod m. Квадратичное пробирование требует подходящих параметров.

Какова амортизированная стоимость union/find со сжатием путей и объединением по рангу?

O(α(n)) на операцию, где α — обратная функция Аккермана, n — число элементов. Инициализация стоит O(n); оценка относится к последовательности, а не к постоянному худшему времени каждого вызова.

Как метод цепочек разрешает коллизии хеширования?

Каждая корзина содержит коллекцию записей с её индексом, часто связный список. Разные ключи в одной корзине остаются отдельными записями.

Сколько стоит построить кучу снизу вверх из n элементов?

O(n). Большинство узлов близко к листьям и требуют мало просеивания вниз; сумма работы по высотам узлов линейна.

Каково условие балансировки AVL?

В каждом узле высота(слева) − высота(справа) ∈ {−1, 0, 1}. Также соблюдается инвариант порядка BST.

Что означает f(n) ∈ O(g(n)) для неотрицательных функций f и g?

Существуют константы c > 0 и n₀ ≥ 0, такие что f(n) ≤ c·g(n) для всех n ≥ n₀.

Как исправить левый-правый дисбаланс после вставки в AVL?

Сначала повернуть левого ребёнка влево, затем несбалансированный узел вправо.

Почему двусвязный список позволяет удалить заданный узел за O(1)?

Ссылки на предыдущий и следующий узлы позволяют напрямую соединить соседей. При необходимости обновляют голову и хвост; искать предшественника не нужно.

Что делают find и union в структуре непересекающихся множеств?

find(x) возвращает представителя множества x. union(x,y) объединяет их множества, если они различны; если уже совпадают, разбиение не меняется.

Чем различаются O, Ω и Θ?

Это соответственно асимптотическая верхняя, нижняя и точная по порядку оценка. Они описывают заданную функцию затрат; O само по себе не означает худший случай.

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

O(1) на добавление. Изменение размера может стоить O(n), но n добавлений в изначально пустой массив суммарно стоят O(n).

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

Прямой: узел → слева → справа. Симметричный: слева → узел → справа. Обратный: слева → справа → узел.

Как работает стек и когда его операции занимают O(1)?

LIFO: последним добавлен — первым извлечён. В голове связного списка добавление, извлечение и просмотр вершины занимают O(1); изменение размера массива может сделать одно добавление O(n).

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

Родитель: ⌊(i−1)/2⌋ при i>0. Дети: 2i+1 и 2i+2, только если эти индексы меньше n. У индекса 0 нет родителя.

Что такое trie и когда поиск ключа из L символов занимает O(L)?

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

Сколько стоят вставка, удаление корня и просмотр корня в двоичной куче?

Соответственно O(log n), O(log n) и O(1), если не нужно менять размер массива. Изменение размера может стоить O(n).

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

Она должна быть детерминированной и хорошо распределять ожидаемые ключи. Хеширование ключа фиксированного размера может занимать O(1); новой строки из L символов — обычно O(L).

Чем различаются сжатие путей, объединение по рангу и по размеру?

Сжатие направляет посещённые узлы к корню. По рангу корень меньшего ранга подвешивают к большему; по размеру меньшее множество — к большему. Ранг не обязан совпадать с текущей высотой.

Что даёт симметричный обход BST с различными ключами?

Все ключи в строго возрастающем порядке; n узлов посещаются за O(n).

Как обход по уровням посещает двоичное дерево?

Очередь FIFO позволяет обрабатывать по одному уровню глубины. Добавление левого ребёнка перед правым обеспечивает порядок слева направо.

Какие цветовые правила поддерживают баланс красно-чёрного BST?

Узлы красные или чёрные; корень и листья NIL чёрные. У красных узлов нет красных детей. Все пути от узла до нижележащего листа NIL содержат одинаковое число чёрных узлов. Это ограничивает высоту величиной O(log n).

Что такое коэффициент заполнения хеш-таблицы и зачем менять её размер?

α = n/m: n записей и m корзин или ячеек. Превышение порога реализации может вызвать увеличение и перехеширование; 0,75 не является универсальным порогом.

Сравните вставку в начало и доступ по индексу в односвязном списке и динамическом массиве.

Список: вставка в начало O(1), доступ по индексу O(n). Массив: вставка в начало O(n), доступ по индексу O(1); вставка в начало сдвигает элементы.

Почему доступ по индексу в массиве фиксированного размера занимает O(1)?

Ячейки одинакового размера расположены подряд: адрес(i) = база + i·размер_ячейки. Предполагается, что вычисление адреса занимает постоянное время.

Какой инвариант порядка определяет двоичное дерево поиска (BST) с различными ключами?

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

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

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

Как поиск, вставка и удаление в BST зависят от высоты h?

Они занимают O(h). У сбалансированного дерева h = O(log n), у цепочки h = O(n). Ожидаемое O(log n) требует предположений, например случайного порядка вставки.

Каков порядок доступа в очереди и типичные затраты на её операции?

FIFO: добавление в конец, извлечение из начала. Обе операции занимают O(1) со ссылками на голову/хвост или в кольцевом буфере фиксированной вместимости; сдвиг массива делает извлечение O(n).

Структуры данных, оценка сложности (Big-O) и фундаментальные алгоритмы

Повторение на уровне бакалавриата, требующее базовых знаний программирования: 32 карточки о массивах, списках, хешировании, деревьях, кучах, trie, Union–Find, фильтрах Блума и сложности.

Level: basic
Languages: ru → ru
Cards: 32
Markdown: Структуры данных, оценка сложности (Big-O) и фундаментальные алгоритмы (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	Расположите скорости роста от меньшей к большей при n → ∞: n!, n, 1, n², log n, 2ⁿ, n log n.	Асимптотически: 1 < log n < n < n log n < n² < 2ⁿ < n!.
2	Какие ответы может давать фильтр Блума, допускающий только вставки?	Отрицательный ответ означает, что элемент не вставляли; положительный — что могли вставить. Хеши устанавливают биты в массиве: ложноположительные ответы возможны, ложноотрицательные при неповреждённом состоянии — нет.
3	Какие два свойства определяют двоичную минимальную кучу?	Все уровни заполнены, кроме, возможно, последнего, который заполняется слева. Ключ родителя не больше ключей детей. Поэтому корень содержит минимум.
4	Каковы ожидаемые и худшие затраты на операции в хеш-таблице с цепочками?	При ограниченном заполнении, хорошем распределении хешей и постоянной стоимости операций с ключами поиск/удаление имеют ожидаемую стоимость O(1). Вставка при геометрическом росте имеет ожидаемую амортизированную стоимость O(1). Цепочка из n коллидирующих ключей может дать O(n).
5	Чем отличаются линейное и квадратичное пробирование при открытой адресации?	Записи остаются в массиве. При размере m и начальном индексе h проверяют соответственно (h+i) mod m и (h+c₁i+c₂i²) mod m. Квадратичное пробирование требует подходящих параметров.
6	Какова амортизированная стоимость union/find со сжатием путей и объединением по рангу?	O(α(n)) на операцию, где α — обратная функция Аккермана, n — число элементов. Инициализация стоит O(n); оценка относится к последовательности, а не к постоянному худшему времени каждого вызова.
7	Как метод цепочек разрешает коллизии хеширования?	Каждая корзина содержит коллекцию записей с её индексом, часто связный список. Разные ключи в одной корзине остаются отдельными записями.
8	Сколько стоит построить кучу снизу вверх из n элементов?	O(n). Большинство узлов близко к листьям и требуют мало просеивания вниз; сумма работы по высотам узлов линейна.
9	Каково условие балансировки AVL?	В каждом узле высота(слева) − высота(справа) ∈ {−1, 0, 1}. Также соблюдается инвариант порядка BST.
10	Что означает f(n) ∈ O(g(n)) для неотрицательных функций f и g?	Существуют константы c > 0 и n₀ ≥ 0, такие что f(n) ≤ c·g(n) для всех n ≥ n₀.
11	Как исправить левый-правый дисбаланс после вставки в AVL?	Сначала повернуть левого ребёнка влево, затем несбалансированный узел вправо.
12	Почему двусвязный список позволяет удалить заданный узел за O(1)?	Ссылки на предыдущий и следующий узлы позволяют напрямую соединить соседей. При необходимости обновляют голову и хвост; искать предшественника не нужно.
13	Что делают find и union в структуре непересекающихся множеств?	find(x) возвращает представителя множества x. union(x,y) объединяет их множества, если они различны; если уже совпадают, разбиение не меняется.
14	Чем различаются O, Ω и Θ?	Это соответственно асимптотическая верхняя, нижняя и точная по порядку оценка. Они описывают заданную функцию затрат; O само по себе не означает худший случай.
15	Какова амортизированная стоимость добавления в конец динамического массива при удвоении вместимости?	O(1) на добавление. Изменение размера может стоить O(n), но n добавлений в изначально пустой массив суммарно стоят O(n).
16	Каковы порядки прямого, симметричного и обратного обхода двоичного дерева?	Прямой: узел → слева → справа. Симметричный: слева → узел → справа. Обратный: слева → справа → узел.
17	Как работает стек и когда его операции занимают O(1)?	LIFO: последним добавлен — первым извлечён. В голове связного списка добавление, извлечение и просмотр вершины занимают O(1); изменение размера массива может сделать одно добавление O(n).
18	Где находятся родитель и дети узла i в массиве кучи длины n с индексацией от нуля?	Родитель: ⌊(i−1)/2⌋ при i>0. Дети: 2i+1 и 2i+2, только если эти индексы меньше n. У индекса 0 нет родителя.
19	Что такое trie и когда поиск ключа из L символов занимает O(L)?	Префиксное дерево хранит ключи вдоль путей из символов, отмечая полные ключи. Поиск занимает O(L), если каждый переход по следующему символу стоит O(1).
20	Сколько стоят вставка, удаление корня и просмотр корня в двоичной куче?	Соответственно O(log n), O(log n) и O(1), если не нужно менять размер массива. Изменение размера может стоить O(n).
21	Какими свойствами должна обладать хеш-функция для поиска в таблице?	Она должна быть детерминированной и хорошо распределять ожидаемые ключи. Хеширование ключа фиксированного размера может занимать O(1); новой строки из L символов — обычно O(L).
22	Чем различаются сжатие путей, объединение по рангу и по размеру?	Сжатие направляет посещённые узлы к корню. По рангу корень меньшего ранга подвешивают к большему; по размеру меньшее множество — к большему. Ранг не обязан совпадать с текущей высотой.
23	Что даёт симметричный обход BST с различными ключами?	Все ключи в строго возрастающем порядке; n узлов посещаются за O(n).
24	Как обход по уровням посещает двоичное дерево?	Очередь FIFO позволяет обрабатывать по одному уровню глубины. Добавление левого ребёнка перед правым обеспечивает порядок слева направо.
25	Какие цветовые правила поддерживают баланс красно-чёрного BST?	Узлы красные или чёрные; корень и листья NIL чёрные. У красных узлов нет красных детей. Все пути от узла до нижележащего листа NIL содержат одинаковое число чёрных узлов. Это ограничивает высоту величиной O(log n).
26	Что такое коэффициент заполнения хеш-таблицы и зачем менять её размер?	α = n/m: n записей и m корзин или ячеек. Превышение порога реализации может вызвать увеличение и перехеширование; 0,75 не является универсальным порогом.
27	Сравните вставку в начало и доступ по индексу в односвязном списке и динамическом массиве.	Список: вставка в начало O(1), доступ по индексу O(n). Массив: вставка в начало O(n), доступ по индексу O(1); вставка в начало сдвигает элементы.
28	Почему доступ по индексу в массиве фиксированного размера занимает O(1)?	Ячейки одинакового размера расположены подряд: адрес(i) = база + i·размер_ячейки. Предполагается, что вычисление адреса занимает постоянное время.
29	Какой инвариант порядка определяет двоичное дерево поиска (BST) с различными ключами?	У каждого узла все ключи левого поддерева меньше его ключа, а правого — больше. Правило действует рекурсивно.
30	Как очередь в кольцевом массиве избегает сдвига после извлечения?	Индексы начала и конца циклически изменяются по модулю вместимости. Извлечение продвигает индекс начала, позволяя повторно использовать свободные ячейки без перемещения остальных элементов.
31	Как поиск, вставка и удаление в BST зависят от высоты h?	Они занимают O(h). У сбалансированного дерева h = O(log n), у цепочки h = O(n). Ожидаемое O(log n) требует предположений, например случайного порядка вставки.
32	Каков порядок доступа в очереди и типичные затраты на её операции?	FIFO: добавление в конец, извлечение из начала. Обе операции занимают O(1) со ссылками на голову/хвост или в кольцевом буфере фиксированной вместимости; сдвиг массива делает извлечение O(n).