Робочий аркуш «Алгоритми та складність» з відповідями

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

Новий робочий аркушТренуватися онлайн з підказками

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

Ім’я: ____________________   Дата: ____________

1.Легка

Що описує час виконання в середньому випадку?

  1. AЧас на найпоширенішому комп'ютері
  2. BСереднє значення між часами виконання в найкращому й найгіршому випадках
  3. CОчікуваний час за заданого розподілу вхідних даних розміру n
  4. DЧас для вхідних даних середньої довжини
2.Легка

Яка нотація описує верхню межу зростання?

  1. AВелике O
  2. BМале омега
  3. CВелике Омега
  4. DВелике Тета
3.Легка

Яка часова складність пошуку в глибину на графі, збереженому у вигляді списків суміжності?

  1. AO(V × E)
  2. BO(V + E)
  3. CO(V²)
  4. DO(E log V)
4.Середня

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

  1. AВона автоматично повертає 0
  2. BВона викликає себе, доки не переповниться стек викликів
  3. CКомпілятор завжди перетворює її на цикл, що безпечно завершується
  4. DВона виконується за час O(1)
5.Середня

Який час виконання порозрядного сортування LSD для n цілих чисел із d цифрами в системі числення з основою k?

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

Яка часова складність: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

  1. AO(n log n)
  2. BO(log n)
  3. CO(n²)
  4. DO(n)
7.Складна

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

  1. AΘ(nlog₂ 7), близько n2,81
  2. BΘ(n² log n)
  3. CΘ(n2)
  4. DΘ(n³)
8.Складна

Яка оцінка для log(n!) правильна?

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

Ключ відповідей

  1. 1. C · Очікуваний час за заданого розподілу вхідних даних розміру n
  2. 2. A · Велике O
  3. 3. B · O(V + E)
  4. 4. B · Вона викликає себе, доки не переповниться стек викликів
  5. 5. A · O(d(n + k))
  6. 6. A · O(n log n)
  7. 7. A · Θ(nlog₂ 7), близько n2,81
  8. 8. A · Θ(n log n)

Повні покрокові розв’язки: тренуйте цю тему на examproblems.com.