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

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

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

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

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

1.Легка

Що таке рекурсія?

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

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

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

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

  1. A12
  2. B10
  3. C512
  4. D32
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²)
  3. CO(n)
  4. DO(n log n)
6.Середня

Який розв'язок рекурентного співвідношення T(n) = 2T(n/2) + O(1)?

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

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

  1. AЇї завжди можна розв'язати за O(V + E)
  2. BВона нерозв'язна
  3. CЦе NP-складна задача
  4. DЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами

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

  1. 1. C · Функція, яка викликає саму себе для менших вхідних даних
  2. 2. B · Велике O
  3. 3. B · 10
  4. 4. D · Найкоротші шляхи (за кількістю ребер) від початкової вершини
  5. 5. B · O(n²)
  6. 6. D · O(n)
  7. 7. D · O(n)
  8. 8. C · Це NP-складна задача

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