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

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

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

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

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

1.Легка

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

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

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

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

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

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

Динамічне програмування корисне, коли задача має:

  1. AОдин цикл
  2. BЖодних підзадач, тож її можна розв'язати за один крок
  3. CЛише випадкові вхідні дані
  4. DПерекривні підзадачі та оптимальну підструктуру
5.Середня

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

  1. AСталою
  2. BЕкспоненційною
  3. CЛогарифмічною
  4. DЛінійною
6.Середня

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

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

Яке визначення класу NP правильне?

  1. AЗадачі, що не є поліноміальними
  2. BЗадачі, які не може розв'язати жоден алгоритм
  3. CЗадачі, які неможливо розв'язати за поліноміальний час
  4. DЗадачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката
8.Складна

Чи належить 22n до O(2ⁿ)?

  1. AТак, бо обидві функції експоненційні
  2. BНі, бо 22n зростає повільніше, ніж 2ⁿ
  3. CТак, бо сталі множники в показнику степеня в нотації «велике O» завжди ігноруються
  4. DНі, бо 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено

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

  1. 1. C · O(n²)
  2. 2. C · O(log n)
  3. 3. B · O(n)
  4. 4. D · Перекривні підзадачі та оптимальну підструктуру
  5. 5. B · Експоненційною
  6. 6. A · На кожному кроці робить локально найкращий вибір
  7. 7. D · Задачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката
  8. 8. D · Ні, бо 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено

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