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

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

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

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

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

1.Легка

Що таке базовий випадок рекурсивної функції?

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

Яка оцінка «велике O» для 3n² + 5n + 2?

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

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

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

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

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

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

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

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

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

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

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

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

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

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

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