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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Доступ к элементу массива по индексу занимает:

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

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

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

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

  1. AΩ (омега большое)
  2. Bo (o малое)
  3. CO (O большое)
  4. DΘ (тета большое)
4.Средняя

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

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

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

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

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

  1. AОколо n
  2. BОколо n / 2
  3. CОколо √n
  4. DОколо log₂ n
7.Сложная

Умножение Карацубы удовлетворяет T(n) = 3T(n/2) + O(n). Каково решение?

  1. AΘ(n log n)
  2. BΘ(n²)
  3. CΘ(nlog₂ 3), примерно n1,585
  4. DΘ(n3)
8.Сложная

Какое определение класса NP верно?

  1. AЗадачи распознавания, положительные ответы которых можно проверить за полиномиальное время при наличии сертификата
  2. BЗадачи, которые не может решить ни один алгоритм
  3. CЗадачи, которые нельзя решить за полиномиальное время
  4. DЗадачи, которые не являются полиномиальными

Ответы

  1. 1. A · O(1)
  2. 2. D · O(n)
  3. 3. A · Ω (омега большое)
  4. 4. A · Ω(n log n)
  5. 5. A · O(n²)
  6. 6. D · Около log₂ n
  7. 7. C · Θ(nlog₂ 3), примерно n1,585
  8. 8. A · Задачи распознавания, положительные ответы которых можно проверить за полиномиальное время при наличии сертификата

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