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

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

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

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

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

1.Легка

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

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

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

  1. AБлизько n / 2
  2. BБлизько n
  3. CБлизько log₂ n
  4. DБлизько n²
3.Легка

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

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

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

  1. AЖадібний використовує 2 монети; оптимум — 2
  2. BЖадібний використовує 3 монети; оптимум — 2
  3. CЖадібний використовує 4 монети; оптимум — 3
  4. DЖадібний використовує 3 монети; оптимум — 3
5.Середня

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

  1. AНі, бо «велике O» завжди має вказувати точну швидкість зростання функції
  2. BНі, бо для великих n n³ менше за n²
  3. CТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
  4. DТак, але лише якщо n менше за 100
6.Середня

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

  1. AO(V × E)
  2. BO(V³ × E)
  3. CO(E log V)
  4. DO(V + E)
7.Складна

Як алгоритм Беллмана–Форда виявляє цикл від'ємної ваги, досяжний із джерела?

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

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

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

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

  1. 1. C · Обсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
  2. 2. C · Близько log₂ n
  3. 3. C · Очікуваний час за заданого розподілу вхідних даних розміру n
  4. 4. B · Жадібний використовує 3 монети; оптимум — 2
  5. 5. C · Так, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³
  6. 6. A · O(V × E)
  7. 7. B · Після V − 1 раундів він перевіряє, чи можна ще релаксувати якесь ребро
  8. 8. D · W — число, тому час експоненційний відносно кількості бітів, використаних для запису W

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