Материал из База знаний подготовки ЕГЭ и ОГЭ
ЕГЭ по информатике: структуры данных и стандартные библиотеки[править | править код]
- Базовые структуры: массивы, списки, очереди, стеки, хеш-таблицы, деревья.
- Когда выбирать ту или иную структуру в задачах ЕГЭ (поиск, сортировка, подсчёт частот).
- Использование стандартных библиотек (Python: `collections`, `heapq`, `itertools`).
- Оценка сложности операций и влияние выбора структуры на время работы программы.
Таблица «Структура → операции → пример»[править | править код]
| Структура |
Быстрые операции |
Где применяем |
Пример (Python)
|
| Список |
Доступ по индексу $O(1)$, добавление в конец $O(1)$ |
Перебор, хранение последовательностей |
`arr.append(x)`
|
| Стек |
`push`/`pop` с конца $O(1)$ |
Обратный обход, проверка скобок |
`stack.append(x); stack.pop()`
|
| Очередь |
Добавление в конец, удаление из начала $O(1)$ |
BFS, обработка задач по мере поступления |
`collections.deque`
|
| Хеш-таблица (словарь) |
Доступ по ключу $O(1)$ |
Подсчёт частот, сопоставление значений |
`counter = collections.Counter(data)`
|
| Куча |
Получение минимума/максимума $O(1)$, добавление $O(\log n)$ |
Поиск $k$-минимальных значений, планирование |
`heapq.heappush(pq, value)`
|
| Деревья/графы |
Поиск путей, структурирование связей |
Задачи на графы, иерархии |
представление списками смежности
|
- **День 1:** повтор массивов, списков, базовых операций, оценка сложности.
- **День 2:** стек и очередь, практика на задачах «скобки», «очередь клиентов».
- **День 3:** словари, `Counter`, подсчёт частот, задачи на анализ текста/данных.
- **День 4:** `heapq`, приоритетные очереди, жадные алгоритмы.
- **День 5:** мини-пробник: три задачи с обязательным выбором структуры + отчёт «почему выбран инструмент».
- Умею оценивать, какая структура нужна для задачи.
- Знаю основные функции модулей `collections`, `heapq`, `itertools`.
- Разбираюсь в сложности операций и умею объяснить выбор.
- Веду таблицу «задача → решение → используемая структура → выигрыш».
- Попросите ученика оформить таблицу с описанием структур и примерами задач.
- Используйте тесты на скорость: одно и то же решение со списком и с `deque`.
- Проводите код-ревью: как можно улучшить структуру данных в решении.
