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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

Задачу обычно называют практически разрешимой (tractable), если:

  1. AЕё можно решить за постоянное время
  2. BУ неё нет решения
  3. CЕё можно решить только перебором всех возможностей
  4. DЕё можно решить за полиномиальное время
4.Средняя

Почему динамическое программирование не даёт реального ускорения для сортировки слиянием?

  1. AУ сортировки слиянием нет рекурсивной структуры
  2. BДинамическое программирование работает только на задачах о графах, но не на массивах
  3. CЕё подзадачи не перекрываются, поэтому нечего использовать повторно
  4. DСортировка слиянием уже работает за O(n)
5.Средняя

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

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

Какой алгоритм сортировки является устойчивым?

  1. AПирамидальная сортировка
  2. BСортировка выбором (типичная версия)
  3. CСортировка слиянием
  4. DБыстрая сортировка (типичная версия на месте)
7.Сложная

Проблема остановки показывает, что:

  1. AЦиклов следует избегать
  2. BНекоторые программы работают быстрее на более быстрых компьютерах, поэтому остановка зависит от оборудования
  3. CНикакой алгоритм не может для каждой программы и входных данных определить, остановится ли она
  4. DКаждая программа в конце концов останавливается
8.Сложная

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

  1. AΘ(n²)
  2. BΘ(n log² n)
  3. CΘ(n)
  4. DΘ(n log n)

Ответы

  1. 1. A · O(n)
  2. 2. A · O(n)
  3. 3. D · Её можно решить за полиномиальное время
  4. 4. C · Её подзадачи не перекрываются, поэтому нечего использовать повторно
  5. 5. C · O(log n)
  6. 6. C · Сортировка слиянием
  7. 7. C · Никакой алгоритм не может для каждой программы и входных данных определить, остановится ли она
  8. 8. B · Θ(n log² n)

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