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

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

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

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

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

1.Легка

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

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

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

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

Час виконання алгоритму — O(n). Як називається таке зростання?

  1. AЛогарифмічне
  2. BЛінійне
  3. CСтале
  4. DКвадратичне
4.Середня

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

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

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

  1. AКомпілятор завжди перетворює її на цикл, що безпечно завершується
  2. BВона викликає себе, доки не переповниться стек викликів
  3. CВона автоматично повертає 0
  4. DВона виконується за час O(1)
6.Середня

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

Яке твердження про вибір k-го найменшого елемента невідсортованого масиву правильне?

  1. AQuickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку
  2. BВибір завжди потребує Ω(n log n), бо вимагає сортування
  3. CВибір можливий лише за O(n²)
  4. DQuickselect працює за O(log n) у найгіршому випадку, бо рекурсивно переходить лише в один бік від опорного елемента
8.Складна

Як класифікують задачу комівояжера?

  1. AВерсія розпізнавання належить до P, а оптимізаційна — NP-повна
  2. BВона належить до P, бо її розв'язує алгоритм Дейкстри, відвідуючи кожне місто один раз
  3. CВона нерозв'язна
  4. DВерсія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною

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

  1. 1. D · Сортування бульбашкою
  2. 2. C · Максимальний час на всіх вхідних даних розміру n
  3. 3. B · Лінійне
  4. 4. B · Обрати заявку, що закінчується найраніше, а потім повторити із сумісними
  5. 5. B · Вона викликає себе, доки не переповниться стек викликів
  6. 6. D · O(n³)
  7. 7. A · Quickselect працює за очікуваний час O(n), а метод медіани медіан гарантує O(n) у найгіршому випадку
  8. 8. D · Версія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною

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