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

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

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

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

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

1.Легка

Доступ до елемента масиву за індексом займає:

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

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

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

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

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

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

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

Що вимірює амортизований аналіз?

  1. AВартість алгоритму на найкращих вхідних даних
  2. BСередню вартість операції на послідовності операцій у найгіршому випадку
  3. CОчікувану вартість на випадкових вхідних даних
  4. DВартість однієї найдорожчої операції будь-де в послідовності
6.Середня

Який час виконання порозрядного сортування LSD для n цілих чисел із d цифрами в системі числення з основою k?

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

Який прийом забезпечує очікуваний час роботи O(n log n) для швидкого сортування на будь-яких вхідних даних?

  1. AСортування вхідних даних перед запуском швидкого сортування
  2. BЗастосування рекурсії лише до лівої частини
  3. CВибір опорного елемента випадково з рівномірним розподілом
  4. DВибір завжди першого елемента
8.Складна

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

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

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

  1. 1. B · O(1)
  2. 2. B · Скінченна послідовність чітко визначених кроків, що розв'язує задачу
  3. 3. B · Близько log₂ n
  4. 4. B · O(log n)
  5. 5. B · Середню вартість операції на послідовності операцій у найгіршому випадку
  6. 6. B · O(d(n + k))
  7. 7. C · Вибір опорного елемента випадково з рівномірним розподілом
  8. 8. B · Версія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною

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