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

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

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

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

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

1.Легка

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

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

Що таке степінь вершини в неорієнтованому графі?

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

Як елементи масиву зберігаються в пам'яті?

  1. AУ дереві сторінок пам'яті
  2. BОдним суцільним блоком, один за одним
  3. CУ випадкових місцях, обраних гешем
  4. DРозкидано, зв'язані вказівниками
4.Середня

Яку умову збалансованості AVL-дерево підтримує в кожному вузлі?

  1. AКожен вузол пофарбовано в червоний або чорний колір
  2. BУсі листки розташовані рівно на однаковій глибині
  3. CВисоти лівого та правого піддерев відрізняються щонайбільше на 1
  4. DОбидва піддерева кожного вузла містять рівно однакову кількість вузлів
5.Середня

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

  1. A2
  2. B0,5
  3. C1
  4. DМаксимуму немає
6.Середня

Чому обхід масиву на практиці часто значно швидший, ніж обхід зв'язного списку такої самої довжини?

  1. AЕлементи масиву розташовані суцільно, тож добре використовують кеш процесора
  2. BОбхід масиву загалом має складність O(1), а обхід зв'язного списку — O(n)
  3. CЗв'язні списки завжди зберігають елементи на диску
  4. DМасиви використовують менше інструкцій для порівняння значень
7.Складна

Що робить розширюване дерево (splay tree) після кожного звертання?

  1. AПерефарбовує вузли на шляху пошуку
  2. BПоворотами піднімає вузол, до якого звернулися, у корінь
  3. CПереміщує вузол, до якого звернулися, у листок
  4. DПеребудовує все дерево у збалансовану форму
8.Складна

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

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

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

  1. 1. C · Повертає верхній елемент, не видаляючи його
  2. 2. A · Кількість ребер, з'єднаних із нею
  3. 3. B · Одним суцільним блоком, один за одним
  4. 4. C · Висоти лівого та правого піддерев відрізняються щонайбільше на 1
  5. 5. C · 1
  6. 6. A · Елементи масиву розташовані суцільно, тож добре використовують кеш процесора
  7. 7. B · Поворотами піднімає вузол, до якого звернулися, у корінь
  8. 8. A · Щоб зробити дуже малоймовірним, що зловмисник підбере багато ключів, які всі матимуть колізію

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