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

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

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

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

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

1.Легка

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

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

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

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

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

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

Як алгоритм Прима будує мінімальне кістякове дерево?

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

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

  1. AO(n)
  2. BO(n² log n)
  3. CO(n³)
  4. DO(n²)
6.Середня

Що означає, що задача має оптимальну підструктуру?

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

Який прийом забезпечує очікуваний час роботи O(n log n) для швидкого сортування на будь-яких вхідних даних?

  1. AЗастосування рекурсії лише до лівої частини
  2. BВибір опорного елемента випадково з рівномірним розподілом
  3. CВибір завжди першого елемента
  4. DСортування вхідних даних перед запуском швидкого сортування
8.Складна

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

  1. AДерево рішень з n можливими результатами має глибину щонайменше log₂ n
  2. BКожен елемент треба порівняти щонайменше один раз
  3. CБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь
  4. DКожне порівняння триває логарифмічний час

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

  1. 1. C · Швидке сортування (quicksort)
  2. 2. D · Максимальний час на всіх вхідних даних розміру n
  3. 3. A · O(n)
  4. 4. C · Він вирощує одне дерево від початкової вершини, додаючи найдешевше ребро, що виходить із дерева
  5. 5. C · O(n³)
  6. 6. D · Оптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
  7. 7. B · Вибір опорного елемента випадково з рівномірним розподілом
  8. 8. A · Дерево рішень з n можливими результатами має глибину щонайменше log₂ n

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