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

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

- **Canonical URL:** https://flashcards.world/flashcards/sets/bda6db80-8023-4ec2-a814-2f077069d179/
- **Markdown URL:** https://flashcards.world/flashcards/sets/bda6db80-8023-4ec2-a814-2f077069d179.md
- **Level:** basic
- **Languages:** ru → ru
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 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). |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/bda6db80-8023-4ec2-a814-2f077069d179/).