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

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

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

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

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

1.Легка

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

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

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

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

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

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

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

  1. AНі, бо для великих n n³ менше за n²
  2. BТак, але лише якщо n менше за 100
  3. CНі, бо «велике O» завжди має вказувати точну швидкість зростання функції
  4. DТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
5.Середня

Скільки рівнів має рекурсія сортування злиттям для масиву з n елементів?

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

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

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

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

  1. AАлгоритм Прима, що починає з однієї вершини
  2. BАлгоритм Флойда–Воршелла
  3. CАлгоритм Дейкстри
  4. DАлгоритм Краскала
8.Складна

Яка оцінка для log(n!) правильна?

  1. AΘ(n)
  2. BΘ(log n)
  3. CΘ(n²)
  4. DΘ(n log n)

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

  1. 1. C · O(1)
  2. 2. A · O(n²)
  3. 3. A · «Розділяй і володарюй»
  4. 4. D · Так, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
  5. 5. B · Близько log₂ n
  6. 6. C · O(log n)
  7. 7. D · Алгоритм Краскала
  8. 8. D · Θ(n log n)

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