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

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

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

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

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

1.Легка

Просторова складність вимірює:

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

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

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

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

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

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

  1. AСталою
  2. BЛінійною
  3. CЕкспоненційною
  4. DЛогарифмічною
5.Середня

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

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

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

  1. AO(n) на інкремент
  2. BO(1) на інкремент
  3. CO(log n) на інкремент
  4. DO(n log n) на інкремент
8.Складна

Узявши обидва кінці кожного ребра максимального (за включенням) паросполучення, отримують вершинне покриття. Наскільки воно добре?

  1. AЩонайбільше вдвічі більше за мінімальне вершинне покриття
  2. BЗавжди мінімальне вершинне покриття
  3. CНевідомої якості порівняно з оптимумом
  4. DЩонайбільше в log n разів більше за мінімум

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

  1. 1. B · Обсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
  2. 2. A · Функція, яка викликає саму себе для менших вхідних даних
  3. 3. B · Воно багаторазово знаходить мінімум невідсортованої частини й переставляє його на початок
  4. 4. C · Експоненційною
  5. 5. B · O(n)
  6. 6. D · O(n log n + k log n)
  7. 7. B · O(1) на інкремент
  8. 8. A · Щонайбільше вдвічі більше за мінімальне вершинне покриття

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