Новая школа

Вот тест по информатике для 11 класса на тему "Дномерное динамическое программирование на подсчет количества вариантов". В конце теста приведены правильные ответы.

Тест по информатике: Дномерное динамическое программирование

Вопрос 1: Какое из следующих утверждений наиболее точно описывает дименсиональное динамическое программирование?
a) Оно используется только для поиска максимальных значений.
b) Оно основывается на разбиении задачи на подзадачи.
c) Оно всегда оптимально решает задачи о кратчайших путях.
d) Оно всегда требует использования графов.

Вопрос 2: Какое значение получает элемент dp[i][j] в типичном алгоритме динамического программирования?
a) Общее количество возможных вариантов для подзадачи.
b) Максимальное значение для подзадачи.
c) Минимальное значение для подзадачи.
d) Результат для целевой задачи.

Вопрос 3: В каком из случаев динамическое программирование особенно эффективно?
a) Если задачи независимы друг от друга.
b) Если задача может быть решена за полиномиальное время без использования динамического программирования.
c) Если есть накладные расходы на переходы между состояниями.
d) Если есть перекрывающиеся подзадачи.

Вопрос 4: В какой задаче наилучшим образом применяется дименсиональное динамическое программирование?
a) Задача о кратчайшем пути в графе.
b) Задача о рюкзаке.
c) Задача о максимальной подпоследовательности.
d) Задача о разбиении строки на подстроки.

Вопрос 5: Какой из следующих алгоритмов можно отнести к классическим методам динамического программирования?
a) Алгоритм Дейкстры.
b) Алгоритм Кнута-Морриса-Пратта.
c) Алгоритм Флойда-Уоршелла.
d) Алгоритм Ханллера.

Вопрос 6: Во время решения задачи о подсчете количества способов разбить число n на суммы, какая основная формула используется для перехода между состояниями?
a) dp[i] = dp[i-1] + 1
b) dp[i] = min(dp[j]) для всех j < i
c) dp[i] = sum(dp[i-j]) для всех j
d) dp[i] = dp[i-1] * dp[i-2]

Ответы:

b) Оно основывается на разбиении задачи на подзадачи.
a) Общее количество возможных вариантов для подзадачи.
d) Если есть перекрывающиеся подзадачи.
b) Задача о рюкзаке.
c) Алгоритм Флойда-Уоршелла.
c) dp[i] = sum(dp[i-j]) для всех j.

Удачи в подготовке к экзаменам!

Бесплатный сервис «Учительская»

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

Тест по информатике: Дномерное динамическое программирование

Ответы:

Популярные тесты

Тест по биологической теме: "Опорно-двигательная система"

Тест по немецкому языку: Тема - Перфект

Тест по Всеобщей истории для 11 класса

Тема: Страны Азии: социалистический выбор развития

Вопросы:

Соответствие:

Ответы: