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

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

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

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

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

1.Легка

Який із цих часів виконання є поліноміальним?

  1. AO(n!)
  2. BO(n³)
  3. CO(2ⁿ)
  4. DO(nⁿ)
2.Легка

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

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

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

  1. A4 секунди
  2. B2 секунди
  3. C1 секунду
  4. D8 секунд
4.Середня

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

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

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

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

Нижня межа для сортування на основі порівнянь у найгіршому випадку становить:

  1. AΩ(n²)
  2. BΩ(log n)
  3. CΩ(n log n)
  4. DΩ(n)
7.Складна

Як класифікують задачу комівояжера?

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

Чому бінарний пошук не дає часу O(log n) на однозв'язному списку?

  1. AЗв'язні списки неможливо сортувати
  2. BБінарному пошуку потрібно щонайменше вдвічі більше пам'яті
  3. CПорівняння вузлів зв'язного списку повільніші
  4. DЩоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом

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

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

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