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

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

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

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

Вопрос 2: Какой из следующих алгоритмов чаще всего используется в динамическом программировании?
a) Алгоритм Дейкстры
b) Алгоритм Краскала
c) Метод ветвей и границ
d) Рекурсивный метод с мемоизацией

Вопрос 3: Каково основное свойство задач, на которые применимо динамическое программирование?
a) Отсутствие подзадач
b) Декомпозиция на независимые подзадачи
c) Перекрывающиеся подзадачи
d) Невозможность деления на подзадачи

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

Вопрос 5: Какой из следующих примеров можно решить с помощью динамического программирования?
a) Задача о рюкзаке
b) Задача о нахождении минимального элемента в массиве
c) Задача о сортировке
d) Задача о линейной регрессии

Вопрос 6: Какой метод динамического программирования будет использоваться для решения задачи о рюкзаке с ограничениями?
a) Рекурсивный подход
b) Брутфорс
c) Итеративное программирование с построением таблицы значений
d) Греческий метод

Вопрос 7: Что такое "таблица" в контексте динамического программирования?
a) График выполнения алгоритма
b) Структура данных для хранения промежуточных результатов
c) Компьютерный файл данных
d) Система управления базами данных

Вопрос 8: Что такое «проблема об увеличении длины наибольшей возрастающей подпоследовательности»?
a) Задача, решаемая методом жадного алгоритма
b) Проблема, для которой динамическое программирование часто применяется
c) Задача, не имеющая решения
d) Задача, требующая линейного времени

Вопрос 9: Как можно описать рекурсивную формулу для задачи о покрытии шахматной доски?
a) R(n) = R(n-1) + R(n-2)
b) R(n) = n + R(n-1)
c) R(n) = R(n-1) + R(n-2) + ... + R(0)
d) R(n) = 2 * R(n-1)

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

Ответы:

1. a
2. d
3. c
4. b
5. a
6. c
7. b
8. b
9. a
10. a, d