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

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

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

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

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

1.Легка

Які три кроки алгоритму «розділяй і володарюй»?

  1. AПрочитати, обчислити, записати
  2. BРозділити, підкорити, об'єднати
  3. CВідсортувати, знайти, повернути
  4. DВгадати, перевірити, повторити
2.Легка

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

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

Просторова складність вимірює:

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

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

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

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

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

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

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

Які часові та просторові витрати обчислення n-го числа Фібоначчі циклом, що зберігає лише два останні значення?

  1. AO(log n) часу та O(n) пам'яті
  2. BO(n) часу та O(1) пам'яті
  3. CO(2ⁿ) часу та O(1) пам'яті
  4. DO(n) часу та O(n) пам'яті
8.Складна

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

  1. AO(n)
  2. BO(n √n)
  3. CO(n²)
  4. DO(n log n)

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

  1. 1. B · Розділити, підкорити, об'єднати
  2. 2. C · O(log n)
  3. 3. B · Обсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
  4. 4. C · O(log n)
  5. 5. A · O(mn)
  6. 6. C · O(n log n + k log n)
  7. 7. B · O(n) часу та O(1) пам'яті
  8. 8. D · O(n log n)

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