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

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

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

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

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

1.Легка

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

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

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

  1. AСортування злиттям
  2. BСортування бульбашкою
  3. CПірамідальне сортування
  4. DШвидке сортування (quicksort)
3.Легка

Що таке алгоритм?

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

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

Приблизно скільки порівнянь потребує бінарний пошук у найгіршому випадку на відсортованому масиві з 1,000,000 елементів?

  1. AБлизько 100
  2. BБлизько 1,000
  3. CБлизько 20
  4. DБлизько 500,000
6.Середня

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

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

Чому пошук у геш-таблиці в середньому має складність O(1), а в найгіршому випадку — O(n)?

  1. AБагато ключів через колізії можуть потрапити в один і той самий кошик
  2. BДоступ до масивів має складність O(n)
  3. CКлючі спершу потрібно відсортувати
  4. DГеш-функції повільні
8.Складна

Чому алгоритм Дейкстри може давати неправильні результати, коли деякі ваги ребер від'ємні?

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

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

  1. 1. B · O(n²)
  2. 2. B · Сортування бульбашкою
  3. 3. A · Скінченна послідовність чітко визначених кроків, що розв'язує задачу
  4. 4. B · O(n²)
  5. 5. C · Близько 20
  6. 6. C · O(n)
  7. 7. A · Багато ключів через колізії можуть потрапити в один і той самий кошик
  8. 8. D · Вершину остаточно фіксують під час вилучення, але пізніше від'ємне ребро ще може дати їй коротший шлях

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