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

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

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

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

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

1.Легка

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

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

Що таке алгоритм повного перебору?

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

Задачу зазвичай називають практично розв'язною (tractable), якщо:

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

Швидке сортування завжди бере опорним перший елемент. На яких вхідних даних воно демонструє поведінку найгіршого випадку?

  1. AНа масиві у випадковому порядку
  2. BНа вже відсортованому масиві
  3. CНа масиві довжини 2
  4. DНа масиві, всі елементи якого різні
5.Середня

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

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

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

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

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

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

Чому бінарний пошук не дає часу O(log n) на однозв'язному списку?

  1. AЩоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом
  2. BПорівняння вузлів зв'язного списку повільніші
  3. CЗв'язні списки неможливо сортувати
  4. DБінарному пошуку потрібно щонайменше вдвічі більше пам'яті

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

  1. 1. B · Збереження результатів викликів функції, щоб повторні виклики отримували відповідь із пам'яті
  2. 2. C · Алгоритм, що перебирає всі можливі кандидати на розв'язок
  3. 3. C · Її можна розв'язати за поліноміальний час
  4. 4. B · На вже відсортованому масиві
  5. 5. D · Сортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  6. 6. C · Вона викликає себе, доки не переповниться стек викликів
  7. 7. A · Версія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною
  8. 8. A · Щоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом

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