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

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

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

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

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

1.Легка

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

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

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

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

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

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

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

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

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

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

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

  1. AБлизько √n
  2. BБлизько n
  3. CБлизько log₂ n
  4. DБлизько n / 2
7.Складна

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

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

Чи належить 22n до O(2ⁿ)?

  1. AНі, бо 22n зростає повільніше, ніж 2ⁿ
  2. BТак, бо обидві функції експоненційні
  3. CТак, бо сталі множники в показнику степеня в нотації «велике O» завжди ігноруються
  4. DНі, бо 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено

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

  1. 1. B · O(1)
  2. 2. A · O(n)
  3. 3. A · f зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
  4. 4. A · O(2ⁿ)
  5. 5. C · O(n)
  6. 6. C · Близько log₂ n
  7. 7. C · O(1) на інкремент
  8. 8. D · Ні, бо 22n = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено

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