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

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

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

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

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

1.Легка

Чому дорівнює log₂ 1024?

  1. A32
  2. B12
  3. C10
  4. D512
2.Легка

Що таке рекурсія?

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

Яка часова складність бінарного пошуку у відсортованому масиві?

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

Який розв'язок рекурентного співвідношення T(n) = T(n − 1) + O(1)?

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

Як алгоритм Прима будує мінімальне кістякове дерево?

  1. AВін вирощує одне дерево від початкової вершини, додаючи найдешевше ребро, що виходить із дерева
  2. BВін запускає пошук у ширину й зберігає дерево BFS
  3. CВін сортує всі ребра за вагою й додає кожне, окрім тих, що утворили б цикл у лісі
  4. DВін видаляє найдорожче ребро, доки не залишиться циклів
6.Середня

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

  1. AСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних
  2. BСортування вставками має складність O(n log n) у найгіршому випадку
  3. CСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  4. DРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів
7.Складна

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

  1. AO((V + E) log V)
  2. BO(V × E)
  3. CO(V³)
  4. DO(V + E)
8.Складна

Узявши обидва кінці кожного ребра максимального (за включенням) паросполучення, отримують вершинне покриття. Наскільки воно добре?

  1. AЩонайбільше вдвічі більше за мінімальне вершинне покриття
  2. BЩонайбільше в log n разів більше за мінімум
  3. CНевідомої якості порівняно з оптимумом
  4. DЗавжди мінімальне вершинне покриття

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

  1. 1. C · 10
  2. 2. A · Функція, яка викликає саму себе для менших вхідних даних
  3. 3. D · O(log n)
  4. 4. C · O(n)
  5. 5. A · Він вирощує одне дерево від початкової вершини, додаючи найдешевше ребро, що виходить із дерева
  6. 6. C · Сортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  7. 7. A · O((V + E) log V)
  8. 8. A · Щонайбільше вдвічі більше за мінімальне вершинне покриття

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