Целочисленные алгоритмы и структуры данных — тест

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

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

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

Алгоритм Евклида

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

Стек и очередь

Из стека берут то, что положили последним, из очереди — то, что положили первым. Отсюда стек естественен для обратного порядка и вложенности, очередь — для обслуживания по порядку прихода.

Как устроена работа

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

Где и как проходить тест

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