Массивы и сортировки в C++: обработка массивов, матрицы, пузырёк, вставки, слияние, быстрая сортировка, двоичный поиск — тест для 8 класса

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

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

Объявление и инициализация массива, допустимые индексы и выход за границы. Сумма и обработка элементов в цикле. Двумерные массивы (матрицы): число элементов, заполнение по формуле, главная диагональ и положение элемента относительно неё. Сортировки пузырьком, вставками, слиянием и быстрая: идея каждой, проходы пузырька, число обменов, поведение в худшем случае. Стандартная сортировка sort. Двоичный поиск: условие применимости, середина отрезка, число шагов.

Задания

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

Разбор

Пояснения показывают, почему у массива из десяти элементов нет элемента a[10], почему для 1000 элементов двоичному поиску хватает десяти шагов, чем худший случай быстрой сортировки отличается от сортировки слиянием и почему sort вызывается с аргументами a и a + n.

Назначение

Работа завершает 8 класс. Двоичный поиск и сортировки — основа первой темы 9 класса (двоичный поиск по ответу), а работа с индексами матриц понадобится в динамическом программировании. В восьмом классе курс «Программирование» ведётся на двух языках: первое полугодие продолжает Python, второе вводит C++, на котором пишут олимпиадные решения и программы для микроконтроллеров. Темы повторяются на обоих языках намеренно — так ученик видит, что алгоритм не зависит от синтаксиса. Эта работа — шестая из 6 по курсу.

Условия прохождения

Задания открываются в браузере на компьютере, планшете или мобильном телефоне, поэтому подойдёт любое устройство под рукой. Учитель может задать период, в течение которого доступен тест, поэтому его допустимо выполнять и дома. Система контроля добросовестности регистрирует переходы в посторонние вкладки и приложения во время выполнения.