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

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

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

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

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

1.Легка

Яка структура даних найкраще підходить для функції «скасувати» (undo) у текстовому редакторі?

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

Чому обхід масиву на практиці часто значно швидший, ніж обхід зв'язного списку такої самої довжини?

  1. AЕлементи масиву розташовані суцільно, тож добре використовують кеш процесора
  2. BЗв'язні списки завжди зберігають елементи на диску
  3. CМасиви використовують менше інструкцій для порівняння значень
  4. DОбхід масиву загалом має складність O(1), а обхід зв'язного списку — O(n)
5.Середня

Яку структуру даних використовує пошук у глибину (DFS, ітеративна версія)?

  1. AСтек
  2. BЧерга
  3. CЛише геш-таблиця
  4. DКупа
6.Середня

Яке призначення сторожового (фіктивного, sentinel) вузла у зв'язному списку?

  1. AЗробити список відсортованим
  2. BЗберігати кількість елементів
  3. CНе дати списку зростати понад фіксовану максимальну кількість вузлів
  4. DСпростити код, усунувши особливі випадки на голові чи хвості
7.Складна

Яку проблему лінійного зондування переважно зменшує подвійне гешування?

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

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

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

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

  1. 1. C · Стек
  2. 2. B · Ключ кожного батька більший або дорівнює ключам його дітей
  3. 3. B · Вузол без дітей
  4. 4. A · Елементи масиву розташовані суцільно, тож добре використовують кеш процесора
  5. 5. A · Стек
  6. 6. D · Спростити код, усунувши особливі випадки на голові чи хвості
  7. 7. B · Первинну кластеризацію, коли утворюються довгі серії зайнятих комірок
  8. 8. D · Стек, що зберігає елементи, які чекають на свою відповідь

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