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

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

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

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

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

1.Легка

Що таке мемоізація?

  1. AНаписання коментарів біля кожного рядка коду
  2. BЗбереження результатів викликів функції, щоб повторні виклики отримували відповідь із пам'яті
  3. CАвтоматичне перетворення рекурсії на рівносильний цикл, щоб стек викликів не був потрібен
  4. DЗвільнення пам'яті після повернення з функції
2.Легка

Що таке базовий випадок рекурсивної функції?

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

Що описує час виконання в середньому випадку?

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

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

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

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

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

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

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

Задача про рюкзак 0/1, розв'язана динамічним програмуванням, потребує O(nW) часу. Чому це називають псевдополіноміальним часом?

  1. AW — число, тому час експоненційний відносно кількості бітів, використаних для запису W
  2. BТому що алгоритм рандомізований, а його час роботи змінюється для кожних вхідних даних
  3. CТому що n завжди мале
  4. DТому що він працює лише для W = 0
8.Складна

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

  1. AЗадачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката
  2. BЗадачі, які неможливо розв'язати за поліноміальний час
  3. CЗадачі, які не може розв'язати жоден алгоритм
  4. DЗадачі, що не є поліноміальними

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

  1. 1. B · Збереження результатів викликів функції, щоб повторні виклики отримували відповідь із пам'яті
  2. 2. D · Випадок, на який відповідають безпосередньо, без нового рекурсивного виклику
  3. 3. C · Очікуваний час за заданого розподілу вхідних даних розміру n
  4. 4. C · Він вирощує одне дерево від початкової вершини, додаючи найдешевше ребро, що виходить із дерева
  5. 5. B · O(n)
  6. 6. C · O(d(n + k))
  7. 7. A · W — число, тому час експоненційний відносно кількості бітів, використаних для запису W
  8. 8. A · Задачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката

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