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

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

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

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

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

1.Легка

Просторова складність вимірює:

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

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

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

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

  1. AO(2ⁿ)
  2. BO(n³)
  3. CO(n!)
  4. DO(nⁿ)
4.Середня

Що означає, що задача має оптимальну підструктуру?

  1. AОптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
  2. BЗадача має рівно один оптимальний розв'язок, спільний для кожної підзадачі
  3. CУсі підзадачі мають однаковий розмір
  4. DЗадачу можна розв'язати за сталий час
5.Середня

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

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

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

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

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

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

Для якого варіанта задачі про рюкзак жадібне правило «брати предмети в порядку цінності на одиницю ваги» завжди дає оптимальну відповідь?

  1. AДля неперервного (дробового) рюкзака, де предмети можна ділити
  2. BДля жодного варіанта
  3. CДля обох варіантів
  4. DДля рюкзака 0/1, де предмети завжди потрібно брати цілими

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

  1. 1. C · Обсяг пам'яті, потрібний алгоритму зі зростанням вхідних даних
  2. 2. C · O(n)
  3. 3. B · O(n³)
  4. 4. A · Оптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
  5. 5. A · O(n²)
  6. 6. A · O(n²)
  7. 7. B · Щоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом
  8. 8. A · Для неперервного (дробового) рюкзака, де предмети можна ділити

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