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

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

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

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

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

1.Легка

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

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

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

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

Що з наведеного зростає найповільніше зі збільшенням n?

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

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

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

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

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

Швидке сортування завжди бере опорним перший елемент. На яких вхідних даних воно демонструє поведінку найгіршого випадку?

  1. AНа масиві, всі елементи якого різні
  2. BНа масиві у випадковому порядку
  3. CНа масиві довжини 2
  4. DНа вже відсортованому масиві
7.Складна

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

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

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

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

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

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

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