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

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

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

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

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

1.Легка

Що описує час виконання алгоритму в найгіршому випадку?

  1. AЧас на найменших вхідних даних
  2. BМаксимальний час на всіх вхідних даних розміру n
  3. CОчікуваний час на випадкових вхідних даних розміру n
  4. DЧас на повільному комп'ютері
2.Легка

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

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

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

  1. AБлизько log₂ n
  2. BБлизько n / 2
  3. CБлизько n²
  4. DБлизько n
4.Середня

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

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

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

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

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

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

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

  1. AНевідомої якості порівняно з оптимумом
  2. BЩонайбільше в log n разів більше за мінімум
  3. CЩонайбільше вдвічі більше за мінімальне вершинне покриття
  4. DЗавжди мінімальне вершинне покриття
8.Складна

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

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

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

  1. 1. B · Максимальний час на всіх вхідних даних розміру n
  2. 2. B · Розділити, підкорити, об'єднати
  3. 3. A · Близько log₂ n
  4. 4. D · O(1)
  5. 5. D · O(log n)
  6. 6. A · O(n²)
  7. 7. C · Щонайбільше вдвічі більше за мінімальне вершинне покриття
  8. 8. D · O(1) на інкремент

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