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

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

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

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

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

1.Легка

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

  1. A512
  2. B12
  3. C10
  4. D32
2.Легка

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

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

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

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

Скільки пам'яті стека використовує проста рекурсивна функція факторіала fact(n) = n × fact(n − 1)?

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

Яке твердження про рекурсивну функцію без досяжного базового випадку правильне?

  1. AВона викликає себе, доки не переповниться стек викликів
  2. BКомпілятор завжди перетворює її на цикл, що безпечно завершується
  3. CВона виконується за час O(1)
  4. DВона автоматично повертає 0
6.Середня

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

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

Для якого варіанта задачі про рюкзак жадібне правило «брати предмети в порядку цінності на одиницю ваги» завжди дає оптимальну відповідь?

  1. AДля обох варіантів
  2. BДля неперервного (дробового) рюкзака, де предмети можна ділити
  3. CДля рюкзака 0/1, де предмети завжди потрібно брати цілими
  4. DДля жодного варіанта
8.Складна

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

  1. AO(n)
  2. BO(n log n)
  3. CO(n²)
  4. DO(log n)

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

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

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