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

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

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

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

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

1.Легка

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

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

Яка оцінка «велике O» для 3n² + 5n + 2?

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

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

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

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

  1. AБлизько log₂ n
  2. BБлизько n / 2
  3. CБлизько √n
  4. DБлизько n
5.Середня

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

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

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

Що треба зробити, щоб показати, що нова задача X є NP-складною?

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

Для якого варіанта задачі про рюкзак жадібне правило «брати предмети в порядку цінності на одиницю ваги» завжди дає оптимальну відповідь?

  1. AДля рюкзака 0/1, де предмети завжди потрібно брати цілими
  2. BДля неперервного (дробового) рюкзака, де предмети можна ділити
  3. CДля жодного варіанта
  4. DДля обох варіантів

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

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

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