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

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

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

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

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

1.Легка

Який із цих часів виконання є поліноміальним?

  1. AO(n³)
  2. BO(2ⁿ)
  3. CO(nⁿ)
  4. DO(n!)
2.Легка

Які три кроки алгоритму «розділяй і володарюй»?

  1. AРозділити, підкорити, об'єднати
  2. BВгадати, перевірити, повторити
  3. CПрочитати, обчислити, записати
  4. DВідсортувати, знайти, повернути
3.Легка

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

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

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

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

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

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

Скільки рівнів має рекурсія сортування злиттям для масиву з n елементів?

  1. AБлизько n
  2. BБлизько n / 2
  3. CБлизько √n
  4. DБлизько log₂ n
7.Складна

Узявши обидва кінці кожного ребра максимального (за включенням) паросполучення, отримують вершинне покриття. Наскільки воно добре?

  1. AЩонайбільше в log n разів більше за мінімум
  2. BЗавжди мінімальне вершинне покриття
  3. CНевідомої якості порівняно з оптимумом
  4. DЩонайбільше вдвічі більше за мінімальне вершинне покриття
8.Складна

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

  1. AO(V³)
  2. BO(V × E)
  3. CO((V + E) log V)
  4. DO(V + E)

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

  1. 1. A · O(n³)
  2. 2. A · Розділити, підкорити, об'єднати
  3. 3. A · Скінченна послідовність чітко визначених кроків, що розв'язує задачу
  4. 4. B · Жадібний використовує 3 монети; оптимум — 2
  5. 5. D · O(d(n + k))
  6. 6. D · Близько log₂ n
  7. 7. D · Щонайбільше вдвічі більше за мінімальне вершинне покриття
  8. 8. C · O((V + E) log V)

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