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

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

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

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

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

1.Легка

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

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

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

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

Задачу зазвичай називають практично розв'язною (tractable), якщо:

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

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

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

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

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

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

Чому пошук у геш-таблиці в середньому має складність O(1), а в найгіршому випадку — O(n)?

  1. AДоступ до масивів має складність O(n)
  2. BГеш-функції повільні
  3. CБагато ключів через колізії можуть потрапити в один і той самий кошик
  4. DКлючі спершу потрібно відсортувати
8.Складна

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

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

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

  1. 1. B · O(n³)
  2. 2. B · O(1)
  3. 3. C · Її можна розв'язати за поліноміальний час
  4. 4. B · O(n)
  5. 5. A · O(n)
  6. 6. C · O(n log n + k log n)
  7. 7. C · Багато ключів через колізії можуть потрапити в один і той самий кошик
  8. 8. D · O(1) на інкремент

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