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

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

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

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

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

1.Легка

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

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

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

  1. AВставлення на початок
  2. BЧитання першого елемента
  3. CДоступ до елемента з індексом i
  4. DВидалення головного елемента
3.Легка

Що містить вказівник next останнього вузла однозв'язного списку?

  1. AАдресу попереднього вузла
  2. BКількість вузлів у списку
  3. CАдресу першого вузла
  4. DNull (жодного вузла)
4.Середня

Яка вартість вставлення елемента в середину масиву з n елементів?

  1. AO(1), бо індекс відомий
  2. BO(n), бо наступні елементи доводиться зсувати
  3. CO(log n) через бінарний пошук
  4. DO(n²), бо кожен елемент переміщується n разів
5.Середня

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який прямий обхід (preorder)?

  1. A4 2 5 1 3
  2. B1 2 3 4 5
  3. C4 5 2 3 1
  4. D1 2 4 5 3
6.Середня

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

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

Для чого використовують структуру union-find в алгоритмі Краскала для мінімального кістякового дерева?

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

Чим radix-дерево (стиснене префіксне дерево) краще за звичайне trie?

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

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

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

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