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

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

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

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

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

1.Легка

Що означає f(n) = Θ(g(n))?

  1. Af зростає строго швидше, ніж g
  2. Bf завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу
  3. Cf зростає строго повільніше, ніж g
  4. Df зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
2.Легка

Скільки додаткової пам'яті використовує стандартне сортування злиттям на основі масиву?

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

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

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

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

  1. AΩ(n)
  2. BΩ(n log n)
  3. CΩ(log n)
  4. DΩ(n²)
5.Середня

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

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

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

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

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

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

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

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

  1. 1. D · f зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
  2. 2. A · O(n)
  3. 3. A · O(n²)
  4. 4. B · Ω(n log n)
  5. 5. C · O(n log n + k log n)
  6. 6. D · O(n²)
  7. 7. B · Орієнтованих ациклічних графів
  8. 8. D · Задачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката

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