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

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

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

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

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

1.Легка

Як працює сортування вибором?

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

Що описує час виконання алгоритму в найгіршому випадку?

  1. AМаксимальний час на всіх вхідних даних розміру n
  2. BОчікуваний час на випадкових вхідних даних розміру n
  3. CЧас на найменших вхідних даних
  4. DЧас на повільному комп'ютері
3.Легка

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

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

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

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

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

Що означає, що задача має оптимальну підструктуру?

  1. AОптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
  2. BЗадачу можна розв'язати за сталий час
  3. CЗадача має рівно один оптимальний розв'язок, спільний для кожної підзадачі
  4. DУсі підзадачі мають однаковий розмір
7.Складна

Що випливало б, якби хтось знайшов поліноміальний алгоритм для однієї NP-повної задачі?

  1. AКожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
  2. BУсі алгоритми з експоненційним часом негайно стали б працювати за лінійний час
  3. CЛише ця одна задача перейшла б до P
  4. DПроблема зупинки стала б розв'язною
8.Складна

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

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

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

  1. 1. C · Воно багаторазово знаходить мінімум невідсортованої частини й переставляє його на початок
  2. 2. A · Максимальний час на всіх вхідних даних розміру n
  3. 3. C · Випадок, на який відповідають безпосередньо, без нового рекурсивного виклику
  4. 4. A · O(n³)
  5. 5. A · O(log n)
  6. 6. A · Оптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
  7. 7. A · Кожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
  8. 8. D · Це NP-складна задача

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