Тест на тему Разработка алгоритмов и программ

Ниже представлен тест по информатике для 9 класса. Тип вопросов — открытые. В конце каждого вопроса дан пример возможного ответа/ключевые моменты для учителя.

1. Вопрос 1 Опишите пошаговый алгоритм нахождения максимального элемента в массиве A длины n. Укажите входы, выход, а также крайние случаи. Ответ (пример конструкции):

• Вход: массив A размера n > 0.
• Шаги: выбрать первый элемент как max = A[1]; для i от 2 до n: если A[i] > max, то max = A[i].
• Выход: max.
• Время выполнения: O(n); потребляемая память: O(1).
• Примечания: если n = 1 — ответ A[1]; если массив пустой — задача не определена, требует обработки входных данных.

2. Вопрос 2 Напишите псевдокод алгоритма проверки числа n на простоту. Укажите вход, выход, шаги. Ответ (пример псевдокода):

• Вход: целое число n.
• Выход: true, если n простое, иначе false.
• Шаги: если n <= 1 вернуть false; для i от 2 до floor(sqrt(n)) сделать: если n mod i == 0 вернуть false; вернуть true.
• Примечание: время работы пропорционально sqrt(n).

3. Вопрос 3 Опишите алгоритм подсчета частоты каждого элемента в массиве целых чисел. Ответ:

• Вход: массив A.
• Выход: отображение freq, где freq[x] — сколько раз встречается значение x.
• Шаги: создать пустой словарь freq; для каждого элемента x в A увеличить freq[x] на 1 (если x впервые — задать 1); вернуть freq.
• Примечание: задача решается без сортировки; временная сложность O(n), память O(k), где k — число уникальных элементов.

4. Вопрос 4 Опишите алгоритм сортировки пузырьком; запишите псевдокод, и приведите пошаговый пример на массиве [5, 2, 4]. Ответ:

• Псевдокод: для i от 0 до n-2: для j от 0 до n-2-i: если A[j] > A[j+1], обменять их.
• Пример на [5, 2, 4]: Шаг 1: сравнить 5 и 2 — [2,5,4]; сравнить 5 и 4 — [2,4,5]. Шаг 2: последние элементы уже на месте; результат [2,4,5].
• Время: O(n^2); память: O(1).

5. Вопрос 5 Опишите алгоритм Евклида для нахождения НОД двух чисел a и b. Напишите псевдокод. Ответ:

• Вход: целые a, b.
• Выход: НОД(a, b).
• Шаги: пока b != 0: заменить a и b на (b, a mod b); вернуть a.
• Сложность: O(log min(a, b)) операций деления.

6. Вопрос 6 Объясните значения понятий: алгоритм, программа, переменная, ветвление, цикл; чем отличается простая последовательность действий от алгоритма. Ответ:

• Алгоритм — набор конкретных шагов для решения задачи, с явным входом и выходом.
• Программа — реализация алгоритма на языке программирования.
• Переменная — именованная область памяти для хранения данных.
• Ветвление — выбор ветки выполнения по условию (если… то… иначе).
• Цикл — повторение блока действий до достижения условия выхода.
• Отличие: алгоритм — идеи решения; программа — конкретная реализация на языке; переменная/ветвление/цикл — конструкции, применяемые внутри алгоритма.

7. Вопрос 7 Напишите псевдокод (или поясните текстом) цикл while, который вычисляет факториал числа n. Ответ:

• Идея: факториал n (= 1, если n = 0; иначе n! = n * (n-1)!).
• Псевдокод: result = 1; i = 2; while i <= n: result = result * i; i = i + 1; вернуть result.
• Пример: n = 4 → 4! = 24.
• Примечание: можно реализовать и через for; важно корректное начальное значение и граница.

8. Вопрос 8 Опишите алгоритм разбиения массива на две части по порогу t: элементы <= t и элементы > t. Ответ:

• Вход: массив A и порог t.
• Выход: два массива: LE ( elements <= t ) и GT (elements > t).
• Шаги: создать пустые LE и GT; для каждого x в A: если x <= t добавить в LE, иначе в GT.
• Время: O(n); память: O(n) в сумме для двух массивов.
• Примечание: можно реализовать без копирования элементов, поместив их в два списка по индексу, если язык позволяет.

9. Вопрос 9 Опишите, как строится блок-схема простого алгоритма. Какие элементы обязательны? Что означают ромб и прямоугольник на схеме? Ответ:

• Блок-схема представляет последовательность действий графически.
• Обязательные элементы: начало/конец (стрелка), операции (прямоугольники), решения (ромбы/условия), направление стрелок.
• Ромб обозначает условие/ветвление; прямоугольник — операция/действие; стрелки показывают последовательность.
• Пример: ввод данных, выполнение действий, проверка условий, выход.

10. Вопрос 10 Напишите псевдокод бинарного поиска в упорядоченном массиве. Ответ:

• Вход: отсортированный массив A, целое x.
• Выход: индекс x в A или -1, если x отсутствует.
• Шаги: l = 0, r = n-1; пока l <= r: m = floor((l + r)/2); если A[m] == x вернуть m; если A[m] < x l = m + 1; иначе r = m - 1; вернуть -1.
• Примечание: предполагается, что массив отсортирован по неубыванию.

11. Вопрос 11 Как найти повторяющийся элемент в массиве? Опишите два подхода: с использованием множества и без него. Ответ:

• Подход 1 (с множеством): пройти по элементам, если элемент уже встречался в множестве, вернуть его; иначе добавить в множество. Время O(n), память O(n).
• Подход 2 (без множества): сортировать массив и найти соседние равные элементы; или использовать алгоритм Floyd–Tloyd для нашли дубликатов без дополнительной памяти. Время O(n log n) с сортировкой; память O(1) при in-place сортировке.

12. Вопрос 12 Перечислите типы тестирования программ и дайте примеры кейсов. Как подбирать тесты? Ответ:

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

13. Вопрос 13 Спроектируйте простой текстовый калькулятор: какие модули должны быть, какие задачи выполнять. Ответ:

• Модули: ввод выражения пользователя, разбор выражения (парсинг), вычисление, вывод результата, обработка ошибок.
• План работы: считать строку; разложить на токены (числа и операции +, -, *, /); проверить синтаксис; выполнить вычисление слева направо или с учётом приоритетов; вывести результат; обработать деление на ноль и т.д.
• Псевдокод/логика: минимально реализовать поддержу бинарных операций с приоритетами или использовать простой последовательный вычислитель.

14. Вопрос 14 Опишите рекурсивную реализацию вычисления чисел Фибоначчи. Приведите пример вызова и обсудите проблемы и способы оптимизации. Ответ:

• Рекурсия: fib(n) = fib(n-1) + fib(n-2) с базами fib(0) = 0, fib(1) = 1.
• Пример вызова: fib(5) = 5.
• Проблемы: экспоненциальная временная сложность из-за повторных вычислений; большой расход памяти на глубине стека.
• Оптимизация: динамическое программирование/мемоизация (запоминание уже вычисленных значений) или итеративная реализация с сохранением двух последних значений.

15. Вопрос 15 Объясните различия локальных и глобальных переменных. Приведите пример. Ответ:

• Локальные переменные определяются внутри функции/модуля и существуют только во время выполнения этой части кода.
• Глобальные переменные объявляются вне функций и доступны во всей программе.
• Пример: глобальная переменная global_count; функция увеличивает её; локальная переменная temp внутри функции не влияет на глобальные значения после возврата.
• Важность: чрезмерное использование глобальных переменных может приводить к трудноуловимым ошибкам и сложному тестированию; локальные переменные улучшают модульность и предсказуемость.

16. Вопрос 16 Опишите алгоритм нахождения минимального элемента в двумерной матрице размером m x n. Укажите сложность. Ответ:

• Вход: матрица M размером m x n.
• Выход: минимум элемента матрицы.
• Шаги: пройти двойной цикл: минимальное = M[1][1]; для i от 1 до m: для j от 1 до n: если M[i][j] < минимальное, обновить минимальное.
• Время: O(mn); память: O(1) (без учёта входных данных).
• Примечание: можно использовать оптимизированные подходы (например, если матрица отсортирована по строкам/столбцам, но в общем случае требуется полный проход).