Базовые алгоритмы для школьников

Упражнение 1:

Номер 1

В чем заключается суть динамического программирования?

Ответ:

(1) в том, что используются динамические переменные, место под которые в оперативной памяти выделяется во время выполнения программы

(2) в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая задача

(3) в том, что поставленная задача решается без разбиения ее на подзадачи

Номер 2

Какие утверждения являются неверными?

Ответ:

(1) суть динамического программирования заключается в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая задача

(2) суть динамического программирования заключается в том, что поставленная задача решается без разбиения ее на подзадачи

(3) суть динамического программирования заключается в том, что используются динамические переменные, место под которые в оперативной памяти выделяется во время выполнения программы

Номер 3

Какое утверждение является верным?

Ответ:

(1) суть динамического программирования заключается в том, что поставленная задача решается без разбиения ее на подзадачи

(2) суть динамического программирования заключается в том, что для отыскания решения поставленной задачи решается похожая (или похожие), но более простая задача

(3) суть динамического программирования заключается в том, что используются динамические переменные, место под которые в оперативной памяти выделяется во время выполнения программы

Упражнение 2:

Номер 1

В каких случаях применяется динамическое программирование?

Ответ:

(1) при решении задач, в которых на разных путях многократно встречаются одни и те же подзадачи

(2) при решении задач оптимизации

(3) при решении задач, в которых искомый ответ состоит из частей, каждая из которых в свою очередь дает оптимальное решение некоторой подзадачи

Номер 2

Какие из перечисленных действий выполняются при решении задачи с помощью динамического программирования?

Ответ:

(1) определение вычисляемого значения

(2) определение рекурентного соотношения

(3) определение начальных значений

Номер 3

Какие из перечисленных действий выполняются при решении задачи с помощью динамического программирования?

Ответ:

(1) определение начальных значений

(2) определение порядка вычисления значений

(3) определение диапазона поиска ответа

Упражнение 3:

Номер 1

Что такое граф?

Ответ:

(1) динамическая структура данных, состоящая из узлов, каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья

(2) линейная структура данных, добавление элементов в которую выполняется в один конец, а выборка - из другого конца

(3) совокупность объектов со связями между ними

(4) линейная структура данных, добавление элементов в которую и выборка из которой выполняются с одного конца

Номер 2

Что является ребрами графа?

Ответ:

(1) объекты

(2) свободные объекты графа (объекты без связей)

(3) пара вершин

Номер 3

Что является вершиной графа?

Ответ:

(1) объекты

(2) связи

(3) два связанных объекта

Упражнение 4:

Номер 1

Какие утверждения являются верными?

Ответ:

(1) на графе вершины обозначены буквами

(2) граф имеет 6 рёбер

(3) граф имеет 9 вершин

Номер 2

Сколько рёбер имеет граф?

Ответ:

(1) 6

(2) 7

(3) 8

(4) 9

Номер 3

Сколько вершин имеет граф?

Ответ:

(1) 6

(2) 7

(3) 8

(4) 9

Упражнение 5:

Номер 1

Какой граф имеет 4 вершины и 5 рёбер?

Ответ:

(1)

(2)

(3)

Номер 2

Отметьте графы, которые имеют одинаковое количество рёбер?

Ответ:

(1)

(2)

(3)

Номер 3

В каком случае количество вершин и количество рёбер графа совпадают?

Ответ:

(1)

(2)

(3)

Упражнение 6:

Номер 1

Какие вершины являются соседями вершины с?

Ответ:

(1) a

(2) b

(3) d

(4) e

(5) f

Номер 2

Какая вершина имеет наибольшее количество соседей?

Ответ:

(1) a

(2) b

(3) с

(4) d

(5) e

(6) f

Номер 3

Какие вершины имеют одинаковое количество соседей?

Ответ:

(1) a

(2) b

(3) с

(4) d

(5) e

(6) f

Упражнение 7:

Номер 1

Степень какой вершины наибольшая?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

Номер 2

Чему равна сумма степеней вершин графа?

Ответ:

(1) 5

(2) 7

(3) 14

Номер 3

Для какого графа сумма степеней вершин графа равна 14?

Ответ:

(1)

(2)

(3)

Упражнение 8:

Номер 1

Какой путь не является простым?

Ответ:

(1) (1)-(4)-(5)-(1)-(3)

(2) (1)-(4)-(3)

(3) (1)-(4)-(5)-(1)

Номер 2

Какой путь называется простым?

Ответ:

(1) путь, содержащий не более одного ребра

(2) путь, в котором вершины не повторяются

(3) путь, который имеет минимальное количество вершин

Номер 3

Какой путь является простым?

Ответ:

(1) (1)-(4)-(5)-(1)-(3)

(2) (1)-(4)-(3)

(3) (1)-(4)-(5)-(1)

Упражнение 9:

Номер 1

Что такое длина пути?

Ответ:

(1) количество рёбер в пути

(2) количество вершин в пути

(3) сумма степеней всех вершин

Номер 2

Какой путь является циклическим?

Ответ:

(1) (1)-(4)-(5)-(1)-(3)

(2) (1)-(4)-(3)

(3) (1)-(4)-(5)-(1)

Номер 3

Какой путь не является циклическим?

Ответ:

(1) (1)-(4)-(5)-(1)-(3)

(2) (1)-(4)-(3)

(3) (1)-(4)-(5)-(1)

Упражнение 10:

Номер 1

Какие утверждения являются верными?

Ответ:

(1) в цикле нельзя два раза подряд ходить по одному и тому же ребру

(2) начало и конец циклического пути находятся в одной вершине

(3) в цикле рёбра не могут повторяться

Номер 2

Какой из перечисленных циклов является повторением цикла (3)-(4)-(2)?

Ответ:

(1) (1)-(2)-(4)

(2) (2)-(3)-(4)

(3) (3)-(4)-(1)

Номер 3

Какой из перечисленных циклов является повторением цикла (1)-(2)-(3)-(4)?

Ответ:

(1) (1)-(3)-(2)-(4)

(2) (1)-(2)-(4)-(3)

(3) (2)-(3)-(4)-(1)

Упражнение 11:

Номер 1

Какие утверждения являются верными?

Ответ:

(1) в ориентированном графе не может быть петель

(2) петля является исходящей

(3) петля является входящей

Номер 2

Как звучит лемма о рукопожатиях для неориентированного графа?

Ответ:

(1) сумма входящих степеней равна сумме исходящих

(2) сумма степеней равна удвоенному количеству рёбер

(3) сумма степеней равна количеству рёбер

Номер 3

Как звучит лемма о рукопожатиях для ориентированного графа?

Ответ:

(1) сумма входящих степеней равна сумме исходящих

(2) сумма степеней равна удвоенному количеству рёбер

(3) сумма степеней равна количеству рёбер

Упражнение 12:

Номер 2

Какой путь является допустимым в ориентированном графе?

Ответ:

(1) (1)-(2)-(3)-(3)-(4)

(2) (1)-(2)-(3)-(4)-(4)

(3) (1)-(2)-(3)-(1)

Базовые алгоритмы для школьников - тест 4