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

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

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

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

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

1.Легка

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

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

Глибина вузла в дереві — це:

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

У якому порядку зворотний обхід (postorder) бінарного дерева відвідує вузли?

  1. AЛіве піддерево, потім вузол, потім праве піддерево
  2. BПраве піддерево, потім вузол, потім ліве піддерево
  3. CЛіве піддерево, потім праве піддерево, потім вузол
  4. DВузол, потім ліве піддерево, потім праве піддерево
4.Середня

Ви маєте посилання на вузол у середині списку. У якому списку його можна видалити за O(1)?

  1. AУ відсортованому масиві
  2. BУ динамічному масиві
  3. CВ однозв'язному списку
  4. DУ двозв'язному списку
5.Середня

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

  1. AІти від кореня лівими дітьми, доки лівої дитини не буде
  2. BВідвідати кожен листок і порівняти їх
  3. CІти від кореня правими дітьми, доки правої дитини не буде
  4. DПодивитися лише на корінь
6.Середня

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

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

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

  1. AВисота щонайбільше n / 2
  2. BВисота рівно log2 n
  3. CВисота щонайбільше 2 log2(n + 1)
  4. DВисота щонайбільше log2 n + 1
8.Складна

Фільтр Блума може відповісти на запитання «чи належить цей елемент множині?»:

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

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

  1. 1. A · Кількість збережених елементів, поділена на кількість кошиків
  2. 2. B · Кількість ребер від кореня до цього вузла
  3. 3. C · Ліве піддерево, потім праве піддерево, потім вузол
  4. 4. D · У двозв'язному списку
  5. 5. A · Іти від кореня лівими дітьми, доки лівої дитини не буде
  6. 6. A · O(n), бо наступні елементи доводиться зсувати
  7. 7. C · Висота щонайбільше 2 log2(n + 1)
  8. 8. C · З можливими хибнопозитивними, але без хибнонегативних результатів

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