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

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

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

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

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

1.Легка

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

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

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

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

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

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

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

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

  1. AПошук у глибину (DFS)
  2. BАлгоритм Краскала
  3. CАлгоритм Дейкстри
  4. DУ всіх випадках потрібен алгоритм Беллмана–Форда
6.Середня

Яка часова складність: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

  1. AΘ(log n)
  2. BΘ(n²)
  3. CΘ(n log n)
  4. DΘ(n)
8.Складна

Алгоритм Штрассена множить матриці, використовуючи 7 замість 8 рекурсивних множень блоків половинного розміру. Який його час виконання?

  1. AΘ(n³)
  2. BΘ(n2)
  3. CΘ(nlog₂ 7), близько n2,81
  4. DΘ(n² log n)

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

  1. 1. C · «Розділяй і володарюй»
  2. 2. C · Сортування бульбашкою
  3. 3. A · Велике O
  4. 4. C · Сортування злиттям
  5. 5. C · Алгоритм Дейкстри
  6. 6. B · O(n log n)
  7. 7. C · Θ(n log n)
  8. 8. C · Θ(nlog₂ 7), близько n2,81

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