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

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

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

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

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

1.Легка

Що таке базовий випадок рекурсивної функції?

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

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

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

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

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

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

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

Який алгоритм сортування є стійким?

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

Яка часова складність: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Топологічне сортування можливе лише для:

  1. AНеорієнтованих графів
  2. BПовних графів
  3. CГрафів із від'ємними вагами
  4. DОрієнтованих ациклічних графів
8.Складна

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

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

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

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

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