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

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

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

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

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

1.Легка

Що зберігається для кожної вершини в поданні графа списками суміжності?

  1. AРядок із V булевих значень
  2. BНайкоротший шлях до кожної іншої вершини
  3. CЗагальна кількість ребер у графі
  4. DСписок сусідніх вершин
2.Легка

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

  1. AЧерга
  2. BСтек
  3. CГраф
  4. DГеш-множина
3.Легка

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

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

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

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

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

  1. Alog₂ n
  2. B1
  3. Cn (дерево перетворюється на зв'язний список)
  4. D√n
6.Середня

Чому бінарну купу можна зберігати в масиві без жодних вказівників?

  1. AКупи ніколи не містять понад 100 елементів
  2. BЦе повне бінарне дерево, тож позиції визначаються простими формулами індексів
  3. CУсі ключі в купі однакові
  4. DМасиви автоматично зберігають ключі відсортованими, тож вказівники не потрібні
7.Складна

Яка властивість підтримує кожне B-дерево ідеально збалансованим?

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

У циклічному буфері front == rear може означати як порожній, так і заповнений буфер. Який поширений спосіб їх розрізнити?

  1. AЗберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
  2. BЗавжди очищати буфер щоразу, коли front дорівнює rear, тож стан — порожній
  3. CРобити розмір буфера степенем двійки
  4. DЗберігати front і rear в одній змінній

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

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

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