Стек, очередь и дек — тест по программированию для ИТ-класса

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

Темы работы

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

Устройство работы

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

Разбор после проведения

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

Для кого

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

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

Тестирование одинаково удобно и на компьютере, и на смартфоне. Период выполнения задаётся гибко, поэтому работу проводят и в классе, и дома. Чтобы снизить риск списывания, фиксируются попытки переключиться на другие вкладки браузера или другие приложения.