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

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

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

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

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

1.Легка

Чому дорівнює log₂ 1024?

  1. A12
  2. B512
  3. C32
  4. D10
2.Легка

Яке позначення описує нижню межу зростання?

  1. AO (велике O)
  2. BΩ (велике Омега)
  3. Co (мале o)
  4. DΘ (велике Тета)
3.Легка

Яка оцінка «велике O» для 3n² + 5n + 2?

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

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

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

Яка часова складність швидкого сортування (quicksort) у найгіршому випадку?

  1. AO(log n)
  2. BO(n²)
  3. CO(n log n)
  4. DO(n)
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Алгоритм Краскала
  3. CАлгоритм Флойда–Воршелла
  4. DАлгоритм Дейкстри
8.Складна

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

  1. AКожне порівняння триває логарифмічний час
  2. BБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь
  3. CКожен елемент треба порівняти щонайменше один раз
  4. DДерево рішень з n можливими результатами має глибину щонайменше log₂ n

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

  1. 1. D · 10
  2. 2. B · Ω (велике Омега)
  3. 3. C · O(n²)
  4. 4. C · O(mn)
  5. 5. B · O(n²)
  6. 6. D · O(V × E)
  7. 7. B · Алгоритм Краскала
  8. 8. D · Дерево рішень з n можливими результатами має глибину щонайменше log₂ n

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