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

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

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

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

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

1.Легка

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

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

Який клас складності зростає найшвидше для великих n?

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

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

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

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

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

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

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

Яка часова складність швидкого сортування (quicksort) у найгіршому випадку?

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

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

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

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

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

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

  1. 1. C · Розділити, підкорити, об'єднати
  2. 2. A · O(2ⁿ)
  3. 3. D · O(1)
  4. 4. B · O(n²)
  5. 5. C · O(log n)
  6. 6. A · O(n²)
  7. 7. D · O(n)
  8. 8. B · O(1) на інкремент

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