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

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

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

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

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

1.Легка

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

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

Що таке алгоритм повного перебору?

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

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

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

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

  1. AБлизько 20
  2. BБлизько 100
  3. CБлизько 500,000
  4. DБлизько 1,000
5.Середня

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

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

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

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

Задача про рюкзак 0/1, розв'язана динамічним програмуванням, потребує O(nW) часу. Чому це називають псевдополіноміальним часом?

  1. AТому що він працює лише для W = 0
  2. BТому що n завжди мале
  3. CW — число, тому час експоненційний відносно кількості бітів, використаних для запису W
  4. DТому що алгоритм рандомізований, а його час роботи змінюється для кожних вхідних даних
8.Складна

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

  1. AO(V + E)
  2. BO(V³)
  3. CO(V × E)
  4. DO((V + E) log V)

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

  1. 1. C · O(n)
  2. 2. D · Алгоритм, що перебирає всі можливі кандидати на розв'язок
  3. 3. D · Скінченна послідовність чітко визначених кроків, що розв'язує задачу
  4. 4. A · Близько 20
  5. 5. C · O(n log n)
  6. 6. C · O(n²)
  7. 7. C · W — число, тому час експоненційний відносно кількості бітів, використаних для запису W
  8. 8. D · O((V + E) log V)

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