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

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

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

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

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

1.Легка

Що бінарний пошук вимагає від вхідних даних?

  1. AМасив має бути відсортованим
  2. BДовжина масиву має бути степенем двійки
  3. CМасив має містити лише додатні числа
  4. DМасив має містити не більше 1000 елементів
2.Легка

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

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

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

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

Чому основу логарифма в «великому O» зазвичай не вказують, як-от в O(log n)?

  1. AОснова має значення лише для малих n
  2. BУсі логарифми в інформатиці мають основу 10, тож вона мається на увазі
  3. CЛогарифми з різними основами відрізняються лише сталим множником
  4. DЛогарифми завжди округлюють до цілих
5.Середня

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

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

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

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

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

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

Яка оцінка для log(n!) правильна?

  1. AΘ(n log n)
  2. BΘ(log n)
  3. CΘ(n)
  4. DΘ(n²)

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

  1. 1. A · Масив має бути відсортованим
  2. 2. C · O(n²)
  3. 3. B · Максимальний час на всіх вхідних даних розміру n
  4. 4. C · Логарифми з різними основами відрізняються лише сталим множником
  5. 5. C · O(n)
  6. 6. B · O(n)
  7. 7. D · O(n)
  8. 8. A · Θ(n log n)

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