Сложность алгоритмов и сортировки — тест для ИТ-класса, 10–11 классы
Бесплатно для подключённых школДве программы могут решать одну задачу и давать одинаковый ответ, но одна справится с миллионом записей за секунду, а другая будет работать час. Первый раздел курса «Программирование» учит заранее, ещё до запуска, оценивать, как растёт время работы алгоритма вместе с размером входных данных. Работа проверяет этот навык на алгоритмах сортировки.
Что проверяет работа
Понятие порядка роста и запись через O-большое; константная, логарифмическая, линейная, линейно-логарифмическая и квадратичная сложность; наилучший, средний и наихудший случай; оценка числа операций у вложенных циклов и у цикла, который на каждом шаге делит диапазон пополам; затраты памяти. Вторая половина работы — сортировки, основанные на сравнении: пузырёк и вставки как квадратичные, слияние и быстрая сортировка как линейно-логарифмические, устойчивость и выбор опорного элемента.
Формат заданий
Пятнадцать заданий разных типов: выбор оценки для фрагмента кода, подсчёт числа сравнений, сопоставление алгоритма и его сложности, восстановление шагов сортировки слиянием в правильном порядке, текст с пропусками о быстрой сортировке. Короткие листинги даны на C++, как в практикуме курса, но читаются без знания конкретного языка. На работу отводится тридцать минут.
Пояснения
После закрытия проведения ученик видит разбор каждого задания: откуда берётся логарифм у двоичного деления, почему быстрая сортировка в худшем случае квадратична и почему константы в O-нотации отбрасывают. Разбор помогает перейти от заучивания таблицы сложностей к самостоятельной оценке незнакомого кода.
Когда проводить
После первого раздела программы десятого класса или как входной срез в начале года, если раздел частично изучался раньше. Результаты удобно сопоставить с лабораторными работами: ошибки в оценке вложенных циклов обычно совпадают с ошибками в самостоятельно написанных сортировках.
Как и на чём выполнять тест
Пройти комплект можно с любого устройства — настольного компьютера, ноутбука, планшета или смартфона. Так как время доступа к тесту настраивается, его спокойно можно выполнять вне школы, дома. Встроенная защита от списывания отмечает, когда учащийся уходит со страницы теста в другие окна или программы.
Примеры заданий
Что описывает запись O(n²) для алгоритма?
Какова сложность фрагмента по числу выполнений строки s += a[i] * a[j];?
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
s += a[i] * a[j];Купить для ребёнка — 190 ₽
Эта работа открывается в кабинете родителя: ребёнок проходит её с телефона или компьютера, вы видите баллы, разбор каждой ошибки и то, какие темы просели. Разовая оплата, доступ навсегда. Первый тест — бесплатно.
Купить для ребёнка — 190 ₽ Что такое кабинет родителяКабинет учителя — 390 ₽
Для учителей и репетиторов, работающих с учениками вне школы. Разовая оплата, доступ навсегда — без подписки. Проведение с любого устройства: участники заходят по ссылке или QR-коду, регистрация не нужна. Результат и разбор ошибок — сразу после работы.
Купить тест — 390 ₽ Оферта и реквизитыДля всей школы — подключить организацию по лицензии →
Заберите этот тест в свою школу
Чтобы добавить тест в базу и провести диагностику — подключите школу к ЗнаниоМетр. Тест станет вашей редактируемой копией: правьте вопросы, баллы и запускайте сессии.
Подключить школу Посмотреть в демоКак выглядит тест «Программирование (ИТ-класс) · 10–11 классы · Сложность алгоритмов и сортировки» в системе
Реальные экраны прохождения в ЗнаниоМетр: на компьютере, на смартфоне и версия для печати (PDF).
