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

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

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

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

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

1.Легка

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

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

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

  1. AЧас на повільному комп'ютері
  2. BЧас на найменших вхідних даних
  3. CОчікуваний час на випадкових вхідних даних розміру n
  4. DМаксимальний час на всіх вхідних даних розміру n
3.Легка

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

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

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

У відсортованому масиві ви шукаєте два елементи із заданою сумою, рухаючи по одному вказівнику з кожного кінця всередину. Яка часова складність?

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

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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

Яка з цих задач виконуваності, як відомо, розв'язна за поліноміальний час?

  1. A2-SAT, де кожен диз'юнкт має щонайбільше два літерали
  2. BЗагальна SAT для формул у кон'юнктивній нормальній формі
  3. C3-SAT, де кожен диз'юнкт має рівно три літерали
  4. DВиконуваність схем

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

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

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