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

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

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

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

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

1.Легка

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

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

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

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

Як називається операція стека, що додає елемент на вершину?

  1. APeek
  2. BPush
  3. CPop
  4. DEnqueue
4.Середня

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

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

Яке значення постфіксного виразу 3 4 + 2 * ?

  1. A11
  2. B14
  3. C24
  4. D10
6.Середня

AVL-дерева та червоно-чорні дерева гарантують:

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

У BST з коренем 50, лівим піддеревом 30 (діти 20, 40) і правим піддеревом 70 (діти 60, 80) корінь видаляють за допомогою наступника в симетричному порядку. Який ключ стає новим коренем?

  1. A40
  2. B60
  3. C70
  4. D80
8.Складна

Яка пара обходів завжди однозначно визначає бінарне дерево з різними ключами?

  1. AПрямий і симетричний обходи
  2. BЛише прямий обхід
  3. CПрямий і зворотний обходи
  4. DЛише обхід по рівнях

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

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

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