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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Чего бинарный поиск требует от входных данных?

  1. AМассив должен содержать только положительные числа
  2. BМассив должен быть отсортирован
  3. CВ массиве должно быть не более 1000 элементов
  4. DДлина массива должна быть степенью двойки
2.Лёгкая

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

  1. AO (O большое)
  2. BΘ (тета большое)
  3. CΩ (омега большое)
  4. Do (o малое)
3.Лёгкая

Что из этого растёт медленнее всего при больших n?

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

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

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

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

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

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

  1. AO(n²)
  2. BO(n log n)
  3. CO(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 √n)
  4. DO(n²)
8.Сложная

Алгоритм Штрассена умножает матрицы, используя 7 вместо 8 рекурсивных умножений блоков половинного размера. Каково время его работы?

  1. AΘ(nlog₂ 7), примерно n2,81
  2. BΘ(n2)
  3. CΘ(n² log n)
  4. DΘ(n³)

Ответы

  1. 1. B · Массив должен быть отсортирован
  2. 2. C · Ω (омега большое)
  3. 3. A · O(log n)
  4. 4. B · На уже отсортированном массиве
  5. 5. D · Ω(n log n)
  6. 6. C · O(n)
  7. 7. B · O(n log n)
  8. 8. A · Θ(nlog₂ 7), примерно n2,81

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