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

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

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

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

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

1.Легка

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

  1. APop
  2. BPush
  3. CPeek
  4. DEnqueue
2.Легка

Граф складається з:

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

Що робить операція peek (або top) стека?

  1. AПовертає верхній елемент, не видаляючи його
  2. BВидаляє верхній елемент і повертає його
  3. CПовертає нижній елемент стека
  4. DВидаляє всі елементи зі стека
4.Середня

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

  1. AO(n)
  2. BO(log n)
  3. CO(1)
  4. DO(n log n)
5.Середня

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

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

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

  1. AO(E²)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(V²)
7.Складна

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

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

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

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

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

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

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