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

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

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

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

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

1.Легка

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

  1. A32
  2. B512
  3. C12
  4. D10
2.Легка

Яке позначення описує нижню межу зростання?

  1. AΩ (велике Омега)
  2. BΘ (велике Тета)
  3. CO (велике O)
  4. Do (мале o)
3.Легка

Задачу зазвичай називають практично розв'язною (tractable), якщо:

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

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

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

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

  1. AТак, але лише якщо n менше за 100
  2. BНі, бо «велике O» завжди має вказувати точну швидкість зростання функції
  3. CТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
  4. DНі, бо для великих n n³ менше за n²
6.Середня

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

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

Яка різниця між нерозв'язною задачею та практично нерозв'язною?

  1. AПрактично нерозв'язні задачі не може розв'язати жоден алгоритм, а нерозв'язні лише потребують експоненційного часу
  2. BОбидва терміни означають, що задача взагалі не має алгоритму
  3. CНерозв'язні задачі належать до NP, а практично нерозв'язні — до P
  4. DДля нерозв'язної задачі немає алгоритму для всіх вхідних даних; для практично нерозв'язної він є, але надто повільний
8.Складна

Яке твердження про вибір k-го найменшого елемента невідсортованого масиву правильне?

  1. AВибір можливий лише за O(n²)
  2. BВибір завжди потребує Ω(n log n), бо вимагає сортування
  3. CQuickselect працює за O(log n) у найгіршому випадку, бо рекурсивно переходить лише в один бік від опорного елемента
  4. DQuickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку

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

  1. 1. D · 10
  2. 2. A · Ω (велике Омега)
  3. 3. B · Її можна розв'язати за поліноміальний час
  4. 4. D · Обрати заявку, що закінчується найраніше, а потім повторити із сумісними
  5. 5. C · Так, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
  6. 6. C · Вона викликає себе, доки не переповниться стек викликів
  7. 7. D · Для нерозв'язної задачі немає алгоритму для всіх вхідних даних; для практично нерозв'язної він є, але надто повільний
  8. 8. D · Quickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку

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