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

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

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

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

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

1.Легка

Алгоритм O(n) працює 3 секунди для n = 1 мільйон. Приблизно скільки він працюватиме для n = 2 мільйони?

  1. A3 секунди
  2. B9 секунд
  3. C6 секунд
  4. D12 секунд
2.Легка

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

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

Що таке алгоритм?

  1. AБудь-яка комп'ютерна програма з графічним інтерфейсом
  2. BСтруктура даних, що зберігає числа
  3. CСкінченна послідовність чітко визначених кроків, що розв'язує задачу
  4. DМова програмування, призначена для запису математичних формул
4.Середня

Яка часова складність стандартного алгоритму динамічного програмування для найдовшої спільної підпослідовності рядків довжиною m і n?

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

Який розв'язок рекурентного співвідношення T(n) = T(n − 1) + O(1)?

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

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

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

Чому алгоритм Дейкстри може давати неправильні результати, коли деякі ваги ребер від'ємні?

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

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

  1. AO(n) на інкремент
  2. BO(1) на інкремент
  3. CO(n log n) на інкремент
  4. DO(log n) на інкремент

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

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

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