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

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

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

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

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

1.Легка

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

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

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

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

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

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

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

  1. AСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних
  2. BРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів
  3. CСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  4. DСортування вставками має складність O(n log n) у найгіршому випадку
5.Середня

Що обчислює алгоритм Флойда–Воршелла і як швидко?

  1. AМінімальне кістякове дерево за O(E log V)
  2. BНайкоротші шляхи між усіма парами вершин за O(V³)
  3. CТопологічний порядок за O(V²)
  4. DНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
6.Середня

Пошук у ширину в незваженому графі знаходить:

  1. AМінімальне кістякове дерево
  2. BТопологічний порядок у будь-якому графі
  3. CНайкоротші шляхи в графах, що містять ребра з від'ємними вагами
  4. DНайкоротші шляхи (за кількістю ребер) від початкової вершини
7.Складна

Яке визначення класу P правильне?

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

Що випливало б, якби хтось знайшов поліноміальний алгоритм для однієї NP-повної задачі?

  1. AПроблема зупинки стала б розв'язною
  2. BЛише ця одна задача перейшла б до P
  3. CУсі алгоритми з експоненційним часом негайно стали б працювати за лінійний час
  4. DКожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP

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

  1. 1. C · O(log n)
  2. 2. D · O(n + k)
  3. 3. D · Воно багаторазово знаходить мінімум невідсортованої частини й переставляє його на початок
  4. 4. C · Сортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  5. 5. B · Найкоротші шляхи між усіма парами вершин за O(V³)
  6. 6. D · Найкоротші шляхи (за кількістю ребер) від початкової вершини
  7. 7. A · Задачі розпізнавання, розв'язні детермінованим алгоритмом за поліноміальний час
  8. 8. D · Кожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP

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