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

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

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

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

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

1.Легка

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

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

Яка часова складність лінійного пошуку в невідсортованому масиві з n елементів (у найгіршому випадку)?

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

Алгоритм O(n²) працює 1 секунду для n = 1000. Приблизно скільки він працюватиме для n = 2000?

  1. A8 секунд
  2. B1 секунду
  3. C4 секунди
  4. D2 секунди
4.Середня

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

  1. AРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів
  2. BСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
  3. CСортування вставками має складність O(n log n) у найгіршому випадку
  4. DСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних
5.Середня

Пошук у ширину в незваженому графі знаходить:

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

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

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

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

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

Яка з цих задач виконуваності, як відомо, розв'язна за поліноміальний час?

  1. AЗагальна SAT для формул у кон'юнктивній нормальній формі
  2. BВиконуваність схем
  3. C3-SAT, де кожен диз'юнкт має рівно три літерали
  4. D2-SAT, де кожен диз'юнкт має щонайбільше два літерали

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

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

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