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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое рекурсия?

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

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

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

Какой класс сложности растёт быстрее всех при больших n?

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

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

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

Какова временна́я сложность умножения двух матриц n × n стандартным тройным циклом?

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

В отсортированном массиве вы ищете два элемента с заданной суммой, двигая по одному указателю с каждого конца внутрь. Какова временна́я сложность?

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

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

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

Какая оценка для log(n!) верна?

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

Ответы

  1. 1. D · Функция, которая вызывает саму себя для меньших входных данных
  2. 2. D · «Разделяй и властвуй»
  3. 3. B · O(2ⁿ)
  4. 4. D · O(n log n)
  5. 5. C · O(n³)
  6. 6. B · O(n)
  7. 7. B · O(n log n)
  8. 8. A · Θ(n log n)

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