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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Пространственная сложность измеряет:

  1. AОбъём памяти, необходимый алгоритму по мере роста входных данных
  2. BКоличество строк кода
  3. CМесто на диске, занимаемое файлом программы после компиляции
  4. DФизический размер компьютера
2.Лёгкая

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

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

Что такое алгоритм?

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

Нижняя граница для сортировки сравнениями в худшем случае равна:

  1. AΩ(n²)
  2. BΩ(n)
  3. CΩ(log n)
  4. DΩ(n log n)
5.Средняя

Решением рекуррентного соотношения T(n) = 2T(n/2) + O(n) является:

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

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

  1. AO(n)
  2. BO(2ⁿ)
  3. CO(n log n)
  4. DO(n²)
7.Сложная

Что установила теорема Кука–Левина?

  1. AПроблема остановки неразрешима
  2. BЛюбую задачу из NP можно решить за экспоненциальное время
  3. CЗадача выполнимости булевых формул (SAT) NP-полна
  4. DP не равно NP
8.Сложная

Какова временна́я сложность: for i = 1 to n: for (j = i; j ≤ n; j = j + i) выполнить работу O(1)?

  1. AO(n √n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)

Ответы

  1. 1. A · Объём памяти, необходимый алгоритму по мере роста входных данных
  2. 2. C · «Разделяй и властвуй»
  3. 3. D · Конечная последовательность чётко определённых шагов, решающая задачу
  4. 4. D · Ω(n log n)
  5. 5. A · O(n log n)
  6. 6. B · O(2ⁿ)
  7. 7. C · Задача выполнимости булевых формул (SAT) NP-полна
  8. 8. B · O(n log n)

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