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

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

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

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

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

1.Легка

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

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

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

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

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

  1. AБлизько log₂ n
  2. BБлизько n
  3. CБлизько n / 2
  4. DБлизько n²
4.Середня

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

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

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

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

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

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

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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

Як класифікують задачу комівояжера?

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

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

  1. 1. B · O(n)
  2. 2. C · O(n³)
  3. 3. A · Близько log₂ n
  4. 4. D · O(n²)
  5. 5. C · Близько 20
  6. 6. C · O(log n)
  7. 7. D · O(n)
  8. 8. B · Версія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною

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