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

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

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

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

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

1.Легка

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

  1. A512
  2. B32
  3. C10
  4. D12
2.Легка

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

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

Які три кроки алгоритму «розділяй і володарюй»?

  1. AРозділити, підкорити, об'єднати
  2. BВгадати, перевірити, повторити
  3. CПрочитати, обчислити, записати
  4. DВідсортувати, знайти, повернути
4.Середня

Жадібний алгоритм:

  1. AНа кожному кроці робить локально найкращий вибір
  2. BПеребирає всі можливі розв'язки
  3. CВикористовує лише рекурсію
  4. DЗавжди дає оптимальний розв'язок
5.Середня

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

Яка часова складність швидкого сортування (quicksort) у найгіршому випадку?

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

Задача є NP-повною, якщо вона:

  1. AНалежить до NP і будь-яка задача з NP зводиться до неї за поліноміальний час
  2. BЛежить поза NP, але складніша за всі задачі NP, як-от проблема зупинки
  3. CНерозв'язна
  4. DРозв'язна за поліноміальний час
8.Складна

Проблема зупинки показує, що:

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

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

  1. 1. C · 10
  2. 2. C · Функція, яка викликає саму себе для менших вхідних даних
  3. 3. A · Розділити, підкорити, об'єднати
  4. 4. A · На кожному кроці робить локально найкращий вибір
  5. 5. D · O(n)
  6. 6. D · O(n²)
  7. 7. A · Належить до NP і будь-яка задача з NP зводиться до неї за поліноміальний час
  8. 8. B · Жоден алгоритм не може для кожної програми та вхідних даних визначити, чи зупиниться вона

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