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

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

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

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

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

1.Легка

Що таке базовий випадок рекурсивної функції?

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

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

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

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

  1. AМале омега
  2. BВелике O
  3. CВелике Тета
  4. DВелике Омега
4.Середня

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

Який алгоритм сортування є стійким?

  1. AСортування злиттям
  2. BШвидке сортування (типова версія на місці)
  3. CСортування вибором (типова версія)
  4. DПірамідальне сортування
6.Середня

Приблизно скільки порівнянь потребує бінарний пошук у найгіршому випадку на відсортованому масиві з 1,000,000 елементів?

  1. AБлизько 100
  2. BБлизько 1,000
  3. CБлизько 500,000
  4. DБлизько 20
7.Складна

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

  1. AO(n²)
  2. BO(n)
  3. CO(n log n)
  4. DO(log n)
8.Складна

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

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

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

  1. 1. C · Випадок, на який відповідають безпосередньо, без нового рекурсивного виклику
  2. 2. A · O(log n)
  3. 3. B · Велике O
  4. 4. A · O(n)
  5. 5. A · Сортування злиттям
  6. 6. D · Близько 20
  7. 7. B · O(n)
  8. 8. D · O(1) на інкремент

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