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

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

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

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

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

1.Легка

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

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

Просторова складність вимірює:

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

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

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

Яка часова складність швидкого сортування (quicksort) у найгіршому випадку?

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

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

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

Розв'язком рекурентного співвідношення T(n) = 2T(n/2) + O(n) є:

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

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

  1. AЦе NP-складна задача
  2. BВона нерозв'язна
  3. CЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами
  4. DЇї завжди можна розв'язати за O(V + E)
8.Складна

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

  1. AТак, але лише для масивів, коротших за 100
  2. BНі, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних
  3. CНі, бо сортування вставками не є сортуванням порівняннями
  4. DТак, отже, нижня межа хибна

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

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

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