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

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

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

Вопрос 1

Что такое динамическое программирование?

• A) Метод решения задач, основанный на разбиении их на подзадачи
• B) Процесс создания программного обеспечения
• C) Алгоритм для сортировки данных
• D) Способ шифрования информации
  Правильный ответ: A

Вопрос 2

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

• A) Поиск максимального элемента в массиве
• B) Поиск кратчайшего пути в графе
• C) Сортировка массива
• D) Умножение матриц
  Правильный ответ: B

Вопрос 3

Какое из следующих утверждений является верным?

• A) Динамическое программирование требует меньше памяти, чем обычные алгоритмы
• B) Динамическое программирование всегда быстрее, чем жадные алгоритмы
• C) Динамическое программирование подходит для задач с "перекрывающимися подзадачами"
• D) Динамическое программирование не используется в реальных приложениях
  Правильный ответ: C

Вопрос 4

Какое из следующих утверждений неверно?

• A) Всё, что можно решить с помощью динамического программирования, можно решить и с помощью жадных алгоритмов
• B) Подход динамического программирования может быть использован для задачи о рюкзаке
• C) Динамическое программирование может быть реализовано с помощью таблиц
• D) Это метод, основанный на принципе оптимальности
  Правильный ответ: A

Вопрос 5

Что такое "принцип оптимальности" в контексте динамического программирования?

• A) Оптимальное решение задачи может быть найдено за O(n) времени
• B) Оптимальное решение задачи состоит из оптимальных решений ее подзадач
• C) Все подзадачи независимы друг от друга
• D) Решение всегда может быть представлено в виде формулы
  Правильный ответ: B

Вопрос 6

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

• A) Алгоритм Дейкстры
• B) Алгоритм Флойда-Уоршелла
• C) Алгоритм Кнута-Морриса-Pratt
• D) Алгоритм 0/1 рюкзака
  Правильный ответ: D

Вопрос 7

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

• A) 0
• B) -1
• C) ∞ (бесконечность)
• D) null
  Правильный ответ: C

Вопрос 8

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

• A) Рекурсия
• B) Декомпозиция
• C) Жадный алгоритм
• D) Мемоизация
  Правильный ответ: B

Вопрос 9

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

• A) Вычисление n-го числа Фибоначчи
• B) Алгоритм Лонгеста Увеличивающей Подпоследовательности
• C) Подсчет всех возможных комбинаций
• D) Оптимизация маршрута с помощью алгоритма Флойда
  Правильный ответ: C

Вопрос 10

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

• A) Когда известно, что все промежуточные результаты не пересекаются
• B) Когда данные имеют большие размеры
• C) Когда есть много повторяющихся подзадач
• D) Когда решение проявляется только в конце
  Правильный ответ: C

Вопрос 11

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

• A) Жадный метод
• B) Метод полной переборной оптимизации
• C) Метод ветвей и границ
• D) Мемоизация
  Правильный ответ: D

Вопрос 12

Какая из задач не является классической задачей динамического программирования?

• A) Нахождение наибольшей общей подпоследовательности
• B) Задача о рюкзаке
• C) Кратчайший путь в графе
• D) Сортировка массивов
  Правильный ответ: D

Вопрос 13

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

• A) Сортировка массива
• B) Сумма элементов массива
• C) Поиск максимальной подпоследовательности
• D) Поиск минимального значения в массиве
  Правильный ответ: A

Вопрос 14

Каково время работы алгоритма для нахождения n-го числа Фибоначчи с использованием динамического программирования?

• A) O(n^2)
• B) O(n log n)
• C) O(n)
• D) O(2^n)
  Правильный ответ: C

Вопрос 15

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

• A) Кэширование
• B) Браузерная кэш-память
• C) Жадное кэширование
• D) Оперативная память
  Правильный ответ: A

Итоги

Этот тест состоит из 15 вопросов, касающихся динамического программирования. Понимание этих вопросов поможет усвоить основные концепции и применения динамического программирования в информатике.