ЕГЭ/Информатика/Структуры данных и библиотеки

ЕГЭ по информатике: структуры данных и стандартные библиотеки

Что важно знать

• Базовые структуры: массивы, списки, очереди, стеки, хеш-таблицы, деревья.
• Когда выбирать ту или иную структуру в задачах ЕГЭ (поиск, сортировка, подсчёт частот).
• Использование стандартных библиотек (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`.
• Разбираюсь в сложности операций и умею объяснить выбор.
• Веду таблицу «задача → решение → используемая структура → выигрыш».

Работа в вики

• Создайте страницу «Структуры данных/ноябрь»: примеры кода, сравнения, тренировки.
• Свяжите материалы с ЕГЭ/Информатика/Оптимизация алгоритмов и профилирование и Ресурсы:Интерактивные шаблоны.
• Для обсуждения откройте тему на форуме: `[url=https://forum.egebal.ru/viewtopic.php?t=489]Структуры данных — делимся решениями[/url]`, добавьте ссылку в разделе «Обсуждение».

Советы наставника

1. Попросите ученика оформить таблицу с описанием структур и примерами задач.
2. Используйте тесты на скорость: одно и то же решение со списком и с `deque`.
3. Проводите код-ревью: как можно улучшить структуру данных в решении.