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

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

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

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

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

1.Легка

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

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

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

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

Що визначає бінарне дерево?

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

Який максимально можливий коефіцієнт заповнення геш-таблиці з відкритою адресацією?

  1. AМаксимуму немає
  2. B2
  3. C1
  4. D0,5
5.Середня

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

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

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

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

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

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

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

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

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

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

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