Создать тест

Вот готовый тест по информатике для 11 класса. Цель теста — понять материал, поэтому в ответах и объяснениях я добавляю подробные шаги и пояснения. Если тебе нужно, могу адаптировать тест под другой формат (более короткие задания, больше задач на код или наоборот). Название теста: Итоговый тест по информатике, 11 класс (Цель: Понять) Время на выполнение: 90 минут Раздел 1. Теоретические вопросы (выбор одного варианта из четырех) Инструкция: выберите один верный ответ и запишите его букву. 1) Какова асимптотическая сложность сортировки пузырьком в худшем случае? - A) O(n) - B) O(n log n) - C) O(n^2) - D) O(2^n) 2) Что означает свойство устойчивости сортировки? - A) Сохраняется порядок равных элементов после сортировки - B) Сортировка всегда работает за линейное время - C) Можно сортировать только целые числа - D) Сортировка требует дополнительной памяти пропорционально размеру массива 3) Бинарный поиск можно использовать на каком массиве? - A) Любой массив - B) Массиве, отсортированном по неубыванию - C) Массиве, отсортированном по возрастанию - D) Массиве, где есть повторяющиеся элементы 4) Что такое абстракция в информатике? - A) Способ реализации алгоритма на языке программирования - B) Процесс скрытия деталей реализации и отображение лишь существенных свойств - C) Способ ускорения выполнения программы - D) Вид памяти компьютера 5) Что из ниже перечисленного является базовым понятием алгоритмов? - A) Монотонность - B) Константность - C) Рекурсия - D) Непоследовательность Раздел 2. Задачи на алгоритмы и структуры данных Инструкция: запишите решение и ответ. B1. Инверсии в массиве Дан массив a = [3, 1, 4, 1, 5]. Число инверсий — количество пар i < j, таких что a[i] > a[j]. Найдите число инверсий в данном массиве. B2. Калькулятор числа способов подъема по ступенькам Сколько существует способов добраться до верхней ступени, если за один шаг можно сделать 1 или 2 шага? Нумерация ступеней от 1 до n, где n = 5. Опишите рекуррентное соотношение и вычислите ответ. B3. Поиск в графе (BFS/DFS — концептуально) Приведён ориентированный граф: A -> B, B -> C, C -> D, A -> D. Вопрос: существует ли путь из A в D? Опишите путь, если он есть. B4. Пример одной итерации пузырьковой сортировки Дан массив [5, 2, 7, 3]. Выполните одну полную итерацию пузырьковой сортировки (один проход слева направо) и запишите получившийся массив. Раздел 3. Программирование (письменно) Инструкция: запишите решения на Python (или псевдокод). Приведите пояснения к коду. C1. Палиндром с игнорированием символов Напишите функцию, которая проверяет, является ли строка палиндромом, игнорируя пробелы и регистр символов (с учётом только алфавитно-цифровых символов). C2. Бинарный поиск Напишите функцию бинарного поиска, которая возвращает индекс искомого элемента в отсортированном по возрастанию списке или -1, если элемента нет. Функцию объясните в параграфе. Пример: тестовые данные можно взять: arr = [2, 4, 7, 9, 12], target = 9 → ответ 3. Инструкция по оформлению: для заданий C можно прислать код в виде блока кода или в виде обычного текста с отступами. В ответах — краткие пояснения к каждому фрагменту. Ответы и подробные объяснения Раздел 1. Теория 1) C. О(n^2) Пояснение: сортировка пузырьком выполняет n-1 проходов, в каждом проходе сравниваются пары соседних элементов; при этом количество сравнений пропорционально n(n-1)/2, то есть O(n^2). 2) A. устойчивость сортировки значит, что порядок равных элементов сохраняется. Пояснение: если в исходном массиве элементы равны и одного типа и другого типа, после сортировки они останутся в том же относительном порядке. 3) C или B: на отсортированном по возрастанию массиве, чаще говорят, что требуется отсортированная последовательность; формально бинарный поиск работает на массиве, отсортированном по возрастанию. Правильный ответ: C. Пояснение: бинарный поиск делит диапазон пополам по каждому шагу, что требует упорядоченности по возрастанию. 4) B. Абстракция — скрытие деталей реализации и отображение только существенных свойств. Пояснение: это позволяет работать с концепциями без привязки к конкретной реализации. 5) C. Рекурсия — базовое понятие алгоритмов, часто встречается в задачах разложения по аналогии. Пояснение: рекурсия — это вызов функции самой себя с меньшими входами; требует базового случая для завершения. Раздел 2. Задачи на алгоритмы и структуры данных B1. Инверсии в массиве Число инверсий = 3. Пошагово: - Пара (0,1): 3 > 1 — инверсия 1 - Пара (0,3): 3 > 1 — инверсия 2 - Пара (2,3): 4 > 1 — инверсия 3 Другие пары не удовлетворяют условию. B2. Способы подъёма по ступенькам (1 или 2 шага) Расчёт циклом Фибоначчи: dp[n] = dp[n-1] + dp[n-2], base dp[1] = 1, dp[2] = 2. Для n = 5: dp[3] = 3, dp[4] = 5, dp[5] = 8. Ответ: 8 способов. B3. Поиск пути в графе Граф: A -> B, B -> C, C -> D, A -> D. Существование пути A → D очевидно: прямой путь A -> D, также можно идти A -> B -> C -> D. Ответ: существует, пример пути: A → D. B4. Одно прохождение пузырьковой сортировки Исходный массив: [5, 2, 7, 3] Проход слева направо: - Сравнить 5 и 2: обмен → [2, 5, 7, 3] - Сравнить 5 и 7: без обмена → [2, 5, 7, 3] - Сравнить 7 и 3: обмен → [2, 5, 3, 7] Итог после одного прохода: [2, 5, 3, 7]. Раздел 3. Программирование C1. Палиндром с игнорированием символов Код (Python): def is_palindrome(s): i, j = 0, len(s) - 1 while i < j: while i < j and not s[i].isalnum(): i += 1 while i < j and not s[j].isalnum(): j -= 1 if i < j and s[i].lower() != s[j].lower(): return False i += 1 j -= 1 return True Пояснение: двухуказательный проход сравнивает символы, пропуская неалфавитно-цифровые, приводит к нижнему регистру для сравнения. C2. Бинарный поиск Код (Python): def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 Пояснение: стандартный алгоритм делит диапазон пополам на каждом шаге; если элемент найден, возвращается индекс, иначе — -1. Пояснения к структуре теста: - Раздел 1 проверяет теорию и базовые понятия алгоритмов. - Раздел 2 формирует навыки анализа и вычисления на практике. - Раздел 3 оценивает умение писать простые фрагменты кода и понимать их работу. Если хочешь, могу адаптировать тест под конкретную тему из программы 11 класса (например, концентрация задач на конкретных алгоритмах: сортировка, графы, графовая теория, или углубление в Python/Java). Также могу привести отдельный вариант теста с другим набором вопросов или увеличить/уменьшить сложность.