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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Каковы три шага алгоритма «разделяй и властвуй»?

  1. AРазделить, решить (властвовать), объединить
  2. BУгадать, проверить, повторить
  3. CОтсортировать, найти, вернуть
  4. DПрочитать, вычислить, записать
2.Лёгкая

Каково O большое для 3n² + 5n + 2?

  1. AO(n³)
  2. BO(3n²)
  3. CO(5n)
  4. DO(n²)
3.Лёгкая

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

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

Каково решение рекуррентного соотношения T(n) = 2T(n − 1) + O(1)?

  1. AO(n)
  2. BO(n²)
  3. CO(2ⁿ)
  4. DO(n log n)
5.Средняя

Каково решение рекуррентного соотношения T(n) = T(n/2) + O(1)?

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

Почему основание логарифма в O большом обычно не указывают, как в O(log n)?

  1. AЛогарифмы по разным основаниям отличаются лишь постоянным множителем
  2. BЛогарифмы всегда округляются до целых
  3. CОснование имеет значение только при малых n
  4. DВсе логарифмы в информатике имеют основание 10, так что оно подразумевается
7.Сложная

Какие две вещи нужно показать, чтобы доказать NP-полноту задачи распознавания X?

  1. AX сводится к задаче из P, и X лежит в NP
  2. BX лежит в P, и X сводится к SAT
  3. CX лежит в NP, и известная NP-полная задача сводится к X за полиномиальное время
  4. DУ X нет полиномиального алгоритма, и X разрешима
8.Сложная

Почему бинарный поиск не даёт времени O(log n) на односвязном списке?

  1. AСвязные списки нельзя сортировать
  2. BБинарному поиску нужно как минимум вдвое больше памяти
  3. CСравнения узлов связного списка медленнее
  4. DЧтобы добраться до среднего элемента, нужно O(n) шагов, поскольку нет прямого доступа по индексу

Ответы

  1. 1. A · Разделить, решить (властвовать), объединить
  2. 2. D · O(n²)
  3. 3. B · «Разделяй и властвуй»
  4. 4. C · O(2ⁿ)
  5. 5. A · O(log n)
  6. 6. A · Логарифмы по разным основаниям отличаются лишь постоянным множителем
  7. 7. C · X лежит в NP, и известная NP-полная задача сводится к X за полиномиальное время
  8. 8. D · Чтобы добраться до среднего элемента, нужно O(n) шагов, поскольку нет прямого доступа по индексу

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