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

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

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

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

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

1.Легка

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

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

Яку складність зазвичай має алгоритм із двома вкладеними циклами, кожен із яких виконується n разів?

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

Доступ до елемента масиву за індексом займає:

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

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

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

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

Чому динамічне програмування не дає реального пришвидшення для сортування злиттям?

  1. AЙого підзадачі не перекриваються, тож нічого використати повторно
  2. BДинамічне програмування працює лише на задачах про графи, а не на масивах
  3. CСортування злиттям не має рекурсивної структури
  4. DСортування злиттям уже має складність O(n)
7.Складна

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

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

Яке твердження про P і NP є правильним?

  1. AКожна задача з P також належить до NP
  2. BДоведено, що P ≠ NP
  3. CРозв'язки задач NP неможливо швидко перевірити
  4. DNP означає «неполіноміальний» (not polynomial)

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

  1. 1. D · Розділити, підкорити, об'єднати
  2. 2. B · O(n²)
  3. 3. A · O(1)
  4. 4. C · O(n)
  5. 5. B · O(n³)
  6. 6. A · Його підзадачі не перекриваються, тож нічого використати повторно
  7. 7. B · O(n)
  8. 8. A · Кожна задача з P також належить до NP

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