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

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

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

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

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

1.Легка

Яка нотація описує верхню межу зростання?

  1. AВелике Омега
  2. BВелике O
  3. CВелике Тета
  4. DМале омега
2.Легка

Яка часова складність бінарного пошуку у відсортованому масиві?

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

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

  1. AШвидке сортування (quicksort)
  2. BСортування злиттям
  3. CПірамідальне сортування
  4. DСортування бульбашкою
4.Середня

Жадібний алгоритм:

  1. AВикористовує лише рекурсію
  2. BЗавжди дає оптимальний розв'язок
  3. CПеребирає всі можливі розв'язки
  4. DНа кожному кроці робить локально найкращий вибір
5.Середня

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

Що вимірює амортизований аналіз?

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

Яка з цих задач виконуваності, як відомо, розв'язна за поліноміальний час?

  1. A3-SAT, де кожен диз'юнкт має рівно три літерали
  2. B2-SAT, де кожен диз'юнкт має щонайбільше два літерали
  3. CВиконуваність схем
  4. DЗагальна SAT для формул у кон'юнктивній нормальній формі
8.Складна

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

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

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

  1. 1. B · Велике O
  2. 2. B · O(log n)
  3. 3. D · Сортування бульбашкою
  4. 4. D · На кожному кроці робить локально найкращий вибір
  5. 5. D · O(n²)
  6. 6. D · Середню вартість операції на послідовності операцій у найгіршому випадку
  7. 7. B · 2-SAT, де кожен диз'юнкт має щонайбільше два літерали
  8. 8. B · Після V − 1 раундів він перевіряє, чи можна ще релаксувати якесь ребро

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