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

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

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

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

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

1.Легка

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

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

Що таке алгоритм?

  1. AМова програмування, призначена для запису математичних формул
  2. BСтруктура даних, що зберігає числа
  3. CСкінченна послідовність чітко визначених кроків, що розв'язує задачу
  4. DБудь-яка комп'ютерна програма з графічним інтерфейсом
3.Легка

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

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

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

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

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

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

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

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

Яка амортизована вартість інкременту двійкового лічильника, якщо один інкремент може змінити багато бітів?

  1. AO(n log n) на інкремент
  2. BO(n) на інкремент
  3. CO(log n) на інкремент
  4. DO(1) на інкремент
8.Складна

Топологічне сортування можливе лише для:

  1. AГрафів із від'ємними вагами
  2. BОрієнтованих ациклічних графів
  3. CНеорієнтованих графів
  4. DПовних графів

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

  1. 1. D · Її можна розв'язати за поліноміальний час
  2. 2. C · Скінченна послідовність чітко визначених кроків, що розв'язує задачу
  3. 3. A · O(log n)
  4. 4. A · O(1)
  5. 5. A · O(mn)
  6. 6. C · O(log n)
  7. 7. D · O(1) на інкремент
  8. 8. B · Орієнтованих ациклічних графів

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