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

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

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

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

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

1.Легка

Що таке корінь дерева?

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

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

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

Що таке вузли-брати (siblings) у дереві?

  1. AВузли без дітей
  2. BВузли на однаковій глибині в різних піддеревах
  3. CВузол і його батько
  4. DВузли зі спільним батьком
4.Середня

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

  1. A2i + 1
  2. B(i + 1) mod n
  3. Ci + 1
  4. D(i − 1) mod n
5.Середня

Кільцевий буфер (ring buffer) зазвичай використовують для реалізації:

  1. AБінарного дерева пошуку
  2. BЧерги фіксованого розміру
  3. CОбходу графа
  4. DГеш-функції
6.Середня

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

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

Дерево відрізків (segment tree) зазвичай використовують для:

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

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

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

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

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

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