Стек, очередь и дек в Python, скобочные выражения, постфиксная запись, деревья поиска и их обход — тест для 9 класса

Стек, очередь и дерево — структуры данных, на которых держится половина привычных программ: кнопка «Назад» браузера, отмена действия, очередь печати, поиск в ширину, файловая система. В этой теме девятиклассники учатся выбирать структуру под задачу и проверять скобки и вычислять выражения с помощью стека.

Что проверяется

Стек и принцип «последним пришёл — первым ушёл», операции добавления и извлечения, реализация списком. Очередь и принцип «первым пришёл — первым ушёл», дек и методы collections.deque. Проверка правильности скобочного выражения, вычисление выражения в постфиксной записи, системный стек вызовов. Двоичное дерево поиска: правило расположения ключей, вставка, прямой и симметричный обход, высота и вырождение дерева, число узлов, дерево арифметического выражения.

Задания

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

Разбор

Пояснения показывают, почему для скобок нужен именно стек, почему pop(0) у списка медленный и для очереди берут deque, как вставка отсортированных ключей превращает дерево в цепочку и почему симметричный обход дерева поиска выдаёт ключи по возрастанию.

Назначение

Работа рассчитана на темы о связанных структурах данных и готовит к графам: обход графа в ширину использует очередь, а в глубину — стек. Девятый класс завершает трёхлетний курс «Программирование» ИТ-вертикали: тридцать четыре часа на Python, посвящённые структурам данных и классическим алгоритмам. Это материал, с которого начинаются олимпиадная информатика и профильные ИТ-классы, куда поступает большинство выпускников вертикали. Эта работа — третья из 5 по курсу.

Технические возможности

Пройти комплект можно с любого устройства — настольного компьютера, ноутбука, планшета или смартфона. Так как время доступа к тесту настраивается, его спокойно можно выполнять вне школы, дома. Встроенная защита от списывания отмечает, когда учащийся уходит со страницы теста в другие окна или программы.