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

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

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

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

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

1.Легка

В однозв'язному списку кожен вузол містить:

  1. AДані та посилання на наступний вузол
  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Рядок із V булевих значень
4.Середня

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

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

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

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

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

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

Дерево відрізків (segment tree) зазвичай використовують для:

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

Об'єкт зберігається як ключ у геш-відображенні (hash map), а потім змінюється поле, яке використовує його геш-функція. Який імовірний результат?

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

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

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

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