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

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

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

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

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

1.Легка

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

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

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

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

Як називається зростання O(2ⁿ)?

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

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

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

Скільки рівнів має рекурсія сортування злиттям для масиву з n елементів?

  1. AБлизько log₂ n
  2. BБлизько n
  3. CБлизько n / 2
  4. DБлизько √n
6.Середня

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

  1. AЖадібний використовує 3 монети; оптимум — 2
  2. BЖадібний використовує 3 монети; оптимум — 3
  3. CЖадібний використовує 4 монети; оптимум — 3
  4. DЖадібний використовує 2 монети; оптимум — 2
7.Складна

Проблема зупинки показує, що:

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

Яке визначення класу P правильне?

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

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

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

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