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

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

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

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

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

1.Легка

Яку стратегію проєктування використовує сортування злиттям?

  1. AДинамічне програмування
  2. B«Розділяй і володарюй»
  3. CЖадібний вибір
  4. DПовний перебір
2.Легка

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

  1. A8 секунд
  2. B4 секунди
  3. C2 секунди
  4. D1 секунду
3.Легка

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

  1. AO(nⁿ)
  2. BO(2ⁿ)
  3. CO(n!)
  4. DO(n³)
4.Середня

Швидке сортування завжди бере опорним перший елемент. На яких вхідних даних воно демонструє поведінку найгіршого випадку?

  1. AНа масиві у випадковому порядку
  2. BНа вже відсортованому масиві
  3. CНа масиві довжини 2
  4. DНа масиві, всі елементи якого різні
5.Середня

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

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

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

  1. AЖадібний використовує 4 монети; оптимум — 3
  2. BЖадібний використовує 3 монети; оптимум — 3
  3. CЖадібний використовує 2 монети; оптимум — 2
  4. DЖадібний використовує 3 монети; оптимум — 2
7.Складна

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

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

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

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

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

  1. 1. B · «Розділяй і володарюй»
  2. 2. B · 4 секунди
  3. 3. D · O(n³)
  4. 4. B · На вже відсортованому масиві
  5. 5. A · Обрати заявку, що закінчується найраніше, а потім повторити із сумісними
  6. 6. D · Жадібний використовує 3 монети; оптимум — 2
  7. 7. A · O(1) на інкремент
  8. 8. A · Вибір опорного елемента випадково з рівномірним розподілом

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