Робочий аркуш «Структури даних» з відповідями

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

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

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

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

1.Легка

Яка структура даних працює за принципом «останнім прийшов — першим вийшов» (LIFO)?

  1. AГеш-таблиця
  2. BСтек
  3. CЧерга
  4. DЗв'язний список
2.Легка

Що таке колізія в геш-таблиці?

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

Яка головна відмінність між статичним і динамічним масивом?

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

Як обчислюють наступну позицію після індексу i в циклічній черзі, що зберігається в масиві місткістю n?

  1. A(i − 1) mod n
  2. B2i + 1
  3. Ci + 1
  4. D(i + 1) mod n
5.Середня

Яку структуру даних використовують, щоб перевірити, чи збалансовані дужки в «{[()]}»?

  1. AБінарне дерево пошуку
  2. BГеш-таблицю
  3. CСтек
  4. DЧергу
6.Середня

Де розташований батько вузла з індексом i в бінарній купі, що зберігається в масиві з індексацією від 0?

  1. AВ індексі ⌊i / 2⌋ + 1
  2. BВ індексі ⌊(i − 1) / 2⌋
  3. CВ індексі 2i + 1
  4. DВ індексі i − 1
7.Складна

Яке твердження про пірамідальне сортування (heapsort) правильне?

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

Які операції підтримує дерево Фенвіка (binary indexed tree) над масивом із n чисел за O(log n)?

  1. AВставлення елементів у будь-яку позицію
  2. BСортування масиву та бінарний пошук
  3. CЗнаходження медіани за O(1)
  4. DЗапити префіксних сум і оновлення окремих елементів

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

  1. 1. B · Стек
  2. 2. C · Два різні ключі відображаються в один індекс
  3. 3. C · Динамічний масив може зростати, переміщуючись до більшого блоку пам'яті
  4. 4. D · (i + 1) mod n
  5. 5. C · Стек
  6. 6. B · В індексі ⌊(i − 1) / 2⌋
  7. 7. A · Воно сортує на місці за час O(n log n) у найгіршому випадку, але не є стабільним
  8. 8. D · Запити префіксних сум і оновлення окремих елементів

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