Алгоритмы и сложность: лист заданий с ответами

Бесплатный лист заданий для печати по теме «Алгоритмы и сложность»: 8 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

Для преподавателей: можно бесплатно печатать, копировать и использовать на занятиях. Каждый новый лист содержит новые значения и собственные ответы. Будем благодарны за ссылку на ExamProblems на странице вашего курса.

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. A«Разделяй и властвуй»
  2. BПолный перебор
  3. CЖадный выбор
  4. DДинамическое программирование
2.Лёгкая

Что такое алгоритм полного перебора (brute force)?

  1. AАлгоритм, угадывающий ответ случайным образом
  2. BАлгоритм, перебирающий все возможные кандидаты в решения
  3. CАлгоритм, работающий на многих процессорах
  4. DАлгоритм, который всегда использует рекурсию
3.Лёгкая

Какое из этих времён работы полиномиально?

  1. AO(2ⁿ)
  2. BO(nⁿ)
  3. CO(n³)
  4. DO(n!)
4.Средняя

Сколько уровней у рекурсии сортировки слиянием для массива из n элементов?

  1. AОколо n / 2
  2. BОколо √n
  3. CОколо log₂ n
  4. DОколо n
5.Средняя

Какова временна́я сложность стандартного алгоритма динамического программирования для наибольшей общей подпоследовательности строк длиной m и n?

  1. AO(mn)
  2. BO(2m+n)
  3. CO(m + n)
  4. DO(mn log n)
6.Средняя

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

  1. AСначала выбрать заявку с наименьшим числом пересечений, затем повторить с совместимыми
  2. BСначала выбрать самую короткую заявку
  3. CВыбрать заявку, которая заканчивается раньше всех, затем повторить с совместимыми
  4. DВыбрать заявку, которая начинается раньше всех
7.Сложная

Какова амортизированная стоимость инкремента двоичного счётчика, если один инкремент может изменить много битов?

  1. AO(n log n) на инкремент
  2. BO(1) на инкремент
  3. CO(log n) на инкремент
  4. DO(n) на инкремент
8.Сложная

Какое утверждение о P и NP верно?

  1. AРешения задач NP невозможно быстро проверить
  2. BДоказано, что P ≠ NP
  3. CNP означает «неполиномиальный» (not polynomial)
  4. DКаждая задача из P также принадлежит NP

Ответы

  1. 1. A · «Разделяй и властвуй»
  2. 2. B · Алгоритм, перебирающий все возможные кандидаты в решения
  3. 3. C · O(n³)
  4. 4. C · Около log₂ n
  5. 5. A · O(mn)
  6. 6. C · Выбрать заявку, которая заканчивается раньше всех, затем повторить с совместимыми
  7. 7. B · O(1) на инкремент
  8. 8. D · Каждая задача из P также принадлежит NP

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.