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

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

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

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

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

1.Легка

Який із цих часів виконання є поліноміальним?

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

Що таке алгоритм повного перебору?

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

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

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

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

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

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

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

Що вимірює амортизований аналіз?

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

Для якого варіанта задачі про рюкзак жадібне правило «брати предмети в порядку цінності на одиницю ваги» завжди дає оптимальну відповідь?

  1. AДля рюкзака 0/1, де предмети завжди потрібно брати цілими
  2. BДля обох варіантів
  3. CДля жодного варіанта
  4. DДля неперервного (дробового) рюкзака, де предмети можна ділити
8.Складна

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

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

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

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

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