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

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

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

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

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

1.Легка

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

  1. AO(E log V)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V²)
2.Легка

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

  1. AСортування бульбашкою
  2. BСортування вставками
  3. CСортування злиттям
  4. DШвидке сортування (quicksort)
3.Легка

Як працює сортування вибором?

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

Який час виконання порозрядного сортування LSD для n цілих чисел із d цифрами в системі числення з основою k?

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

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

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

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

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

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

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

Як співвідносяться n! і 2ⁿ для великих n?

  1. A2ⁿ зростає швидше, ніж n!
  2. Bn! є O(n²)
  3. Cn! зростає швидше, ніж 2ⁿ
  4. DВони зростають з однаковою швидкістю

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

  1. 1. B · O(V + E)
  2. 2. D · Швидке сортування (quicksort)
  3. 3. C · Воно багаторазово знаходить мінімум невідсортованої частини й переставляє його на початок
  4. 4. A · O(d(n + k))
  5. 5. D · Сортування злиттям
  6. 6. A · O(n²)
  7. 7. A · Щонайбільше вдвічі більше за мінімальне вершинне покриття
  8. 8. C · n! зростає швидше, ніж 2ⁿ

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