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

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

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

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

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

1.Легка

Що з наведеного зростає найповільніше зі збільшенням n?

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

Як називається зростання O(2ⁿ)?

  1. AПоліноміальне
  2. BЕкспоненційне
  3. CЛінійне
  4. DЛогарифмічне
3.Легка

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

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

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

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

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

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

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

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

Який алгоритм знаходить мінімальне кістякове дерево, багаторазово додаючи найдешевше ребро, яке не утворює циклу?

  1. AАлгоритм Краскала
  2. BАлгоритм Флойда–Воршелла
  3. CАлгоритм Прима, що починає з однієї вершини
  4. DАлгоритм Дейкстри
8.Складна

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

  1. AO((V + E) log V)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V³)

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

  1. 1. A · O(log n)
  2. 2. B · Експоненційне
  3. 3. C · O(V + E)
  4. 4. C · Вона викликає себе, доки не переповниться стек викликів
  5. 5. B · Обрати заявку, що закінчується найраніше, а потім повторити із сумісними
  6. 6. D · O(V × E)
  7. 7. A · Алгоритм Краскала
  8. 8. A · O((V + E) log V)

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