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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая нотация описывает верхнюю границу роста?

  1. AO-большое
  2. BТета-большое
  3. CОмега-малое
  4. DОмега-большое
2.Лёгкая

Что такое базовый случай рекурсивной функции?

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

Какова временная сложность сортировки слиянием в худшем случае?

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

Какова временна́я сложность: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Быстрая сортировка всегда берёт в качестве опорного первый элемент. На каком входе проявляется её поведение в худшем случае?

  1. AНа уже отсортированном массиве
  2. BНа массиве длины 2
  3. CНа массиве, все элементы которого различны
  4. DНа массиве в случайном порядке
6.Средняя

Что измеряет амортизационный анализ?

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

Как классифицируется задача коммивояжёра?

  1. AОна неразрешима
  2. BВерсия распознавания NP-полна, а оптимизационная версия NP-трудна
  3. CОна лежит в P, потому что её решает алгоритм Дейкстры, посещая каждый город один раз
  4. DВерсия распознавания лежит в P, а оптимизационная NP-полна
8.Сложная

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

  1. AПоказать, что у X нет полиномиального алгоритма для малых входов
  2. BСвести известную NP-трудную задачу к X за полиномиальное время
  3. CПоказать, что X можно проверить за полиномиальное время
  4. DСвести X к известной NP-трудной задаче за полиномиальное время

Ответы

  1. 1. A · O-большое
  2. 2. A · Случай, ответ на который даётся напрямую, без нового рекурсивного вызова
  3. 3. A · O(n log n)
  4. 4. B · O(n log n)
  5. 5. A · На уже отсортированном массиве
  6. 6. A · Среднюю стоимость одной операции в худшей последовательности операций
  7. 7. B · Версия распознавания NP-полна, а оптимизационная версия NP-трудна
  8. 8. B · Свести известную NP-трудную задачу к X за полиномиальное время

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