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

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

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

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

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

1.Легка

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

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

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

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

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

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

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

  1. AЛогарифми з різними основами відрізняються лише сталим множником
  2. BУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
  3. CОснова має значення лише для малих n
  4. DЛогарифми завжди округлюють до цілих
5.Середня

Приблизно скільки порівнянь потребує бінарний пошук у найгіршому випадку на відсортованому масиві з 1,000,000 елементів?

  1. AБлизько 500,000
  2. BБлизько 100
  3. CБлизько 1,000
  4. DБлизько 20
6.Середня

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

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

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

Алгоритм динамічного програмування Гелда–Карпа точно розв'язує задачу комівояжера. Який його час виконання для n міст?

  1. AO(n³)
  2. BO(n² 2ⁿ)
  3. CO(2n²)
  4. DO(n!)

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

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

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