Информатика · Пробное ЕНТ

Алгоритмы: тест ЕНТ

Проверьте знания по теме «Алгоритмы» для подготовки к ЕНТ. Формулы, логические выражения и математические обозначения отображаются через MathML.

20 вопросов4 варианта ответаПроверка сразуОбъясненияБез регистрации

Вопрос 1 из 20Правильных ответов: 0

✓

Тест завершён

Ваш результат по теме «Алгоритмы»

0 / 20

Другие тесты по информатике

Подготовка к ЕНТ: Алгоритмы

Тематический тест помогает проверить не весь курс, а конкретный раздел «Алгоритмы». Такой формат удобен для повторения после урока, самостоятельной подготовки и поиска слабых мест.

Как работать с результатом

Не ограничивайтесь итоговым числом правильных ответов. Обратите внимание, какие понятия были перепутаны и почему выбранный вариант показался верным. После объяснения попробуйте своими словами сформулировать правило или алгоритм, логическое правило или вычислительную закономерность.

Повторное прохождение имеет смысл после короткого повторения темы. Цель — понимать связь между данными, алгоритмом, кодом и результатом выполнения, а не запоминать расположение ответов.

Алгоритмы · Функции · Рекурсия · Строки · Файлы · Сортировка · Графы

Не запоминайте только определения — прослеживайте, как алгоритм изменяет данные шаг за шагом

В актуальной спецификации ЕНТ по информатике в раздел «Алгоритмы и программы» входят функции, рекурсия, работа со строками и файлами, сортировка и графы. Поэтому при подготовке важно уметь не только узнавать термин, но и выполнять трассировку небольших алгоритмов и анализировать результат их работы.

01 Прочитайте алгоритм сверху вниз Сначала определите начальные значения переменных и порядок выполнения команд

02 Отслеживайте условия и циклы Фиксируйте, когда ветвь выполняется и как изменяются переменные после каждой итерации

03 Для рекурсии найдите базовый случай После этого раскройте вызовы до базового случая и вычисляйте результат в обратном порядке

04 Для графа выпишите вершины и рёбра Отдельно контролируйте порядок обхода, степени вершин и веса рёбер

Базовые алгоритмические конструкции

Дискретность Алгоритм состоит из отдельных последовательных шагов, каждый из которых выполняет определённое действие.

Определённость Каждая команда должна трактоваться однозначно и не оставлять исполнителю неопределённого выбора.

Конечность и результативность Выполнение алгоритма должно завершаться за конечное число шагов и приводить к предусмотренному результату.

Следование Команды выполняются последовательно в том порядке, который задан алгоритмом.

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

Цикл Определённая последовательность действий повторяется заданное число раз или пока выполняется условие.

Функция Именованный фрагмент программы, который можно вызывать многократно и которому можно передавать аргументы.

Рекурсия Функция вызывает саму себя для более простой версии задачи. Обязательным элементом корректной рекурсии является достижимый базовый случай.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

При трассировке никогда не вычисляйте несколько строк «в уме» сразу. Записывайте значения переменных после каждого изменения — это особенно важно в циклах и рекурсивных функциях.

Строки, файлы, сортировка и графы

Строка Это последовательность символов. При работе со строками важно учитывать индексацию, срезы, длину строки и порядок символов.

Файлы Режим чтения используется для получения данных, режим записи — для создания или перезаписи содержимого, а режим добавления — для записи в конец файла.

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

Сортировка выбором На каждом шаге в неотсортированной части находят минимальный или максимальный элемент и помещают его на требуемую позицию.

Сортировка вставками Очередной элемент вставляется в нужное место уже отсортированной части последовательности.

Граф Состоит из вершин и рёбер. Ребро описывает связь между двумя вершинами.

Степень вершины В неориентированном графе равна количеству рёбер, инцидентных данной вершине.

Матрица смежности Показывает наличие связей между парами вершин. Для простого неориентированного графа она симметрична относительно главной диагонали.

Типичная схема обработки данных

1. Ввод Получите исходные данные из переменных, строки, списка или файла.

2. Обработка Примените условие, цикл, функцию, сортировку или другой алгоритм.

3. Контроль промежуточного состояния Следите за индексами, накопителями, очередью обхода или текущим максимумом.

4. Вывод Только после полного выполнения алгоритма определите конечный результат.

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

Алгоритм решения

Как выполнять задания на трассировку

Зафиксируйте начальное состояние

Выпишите исходные значения переменных, содержимое строки, массива или исходную вершину графа.

Проверяйте условие буквально

Не заменяйте строгие сравнения нестрогими и учитывайте логические операции в том виде, в котором они записаны.

В цикле ведите таблицу состояний

Для каждой итерации фиксируйте значение счётчика, изменяемых переменных и результата.

В рекурсии сначала идите к базовому случаю

После достижения базового случая последовательно возвращайтесь по цепочке вызовов и вычисляйте значения.

Для сортировки воспроизводите именно указанный метод

Не сортируйте массив сразу целиком: вопрос может спрашивать состояние после конкретного прохода или итерации.

Для графа контролируйте уже посещённые вершины

При обходе не добавляйте одну и ту же вершину повторно, если алгоритм уже отметил её как обнаруженную.

Частые ошибки

Что особенно важно не перепутать

Путают индекс и значение элемента

Индекс определяет позицию элемента, а сам элемент — хранящееся на этой позиции значение.

Не учитывают изменение переменной внутри цикла

Условие следующей итерации проверяется уже с новым значением, полученным на предыдущем шаге.

Считают рекурсивный вызов мгновенным

Каждый вызов создаёт новое вычисление функции, пока не будет достигнут базовый случай.

Игнорируют границы среза строки

Начальный индекс включается, конечный — не включается, а третий параметр определяет шаг.

Сразу записывают полностью отсортированный массив

Если спрашивается состояние после одного прохода, необходимо выполнить только этот проход.

В графе выбирают путь с меньшим числом вершин вместо меньшего веса

Для взвешенного графа длина маршрута определяется суммой весов его рёбер, если условием не задано иное.