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

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

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

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

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

1.Легка

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

  1. AO(V²)
  2. BO(E log V)
  3. CO(V + E)
  4. DO(V × E)
2.Легка

Час виконання алгоритму — O(n). Як називається таке зростання?

  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.Середня

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

  1. AΩ(log n)
  2. BΩ(n log n)
  3. CΩ(n²)
  4. DΩ(n)
5.Середня

Яка часова складність: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Динамічне програмування корисне, коли задача має:

  1. AЖодних підзадач, тож її можна розв'язати за один крок
  2. BЛише випадкові вхідні дані
  3. CПерекривні підзадачі та оптимальну підструктуру
  4. DОдин цикл
7.Складна

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

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

Яка різниця між нерозв'язною задачею та практично нерозв'язною?

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

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

  1. 1. C · O(V + E)
  2. 2. A · Лінійне
  3. 3. A · 4 секунди
  4. 4. B · Ω(n log n)
  5. 5. A · O(n log n)
  6. 6. C · Перекривні підзадачі та оптимальну підструктуру
  7. 7. A · O(1) на інкремент
  8. 8. B · Для нерозв'язної задачі немає алгоритму для всіх вхідних даних; для практично нерозв'язної він є, але надто повільний

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