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

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

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

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

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

1.Легка

Яка структура даних найкраще підходить для функції «скасувати» (undo) у текстовому редакторі?

  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.Середня

Ключі 50, 30, 70, 20, 40 вставляють у такому порядку в порожнє бінарне дерево пошуку. Яка ліва дитина вузла 30?

  1. A20
  2. B40
  3. C70
  4. D50
6.Середня

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

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

Скільки триває пошук довільного ключа в бінарній мін-купі з n елементів?

  1. AO(log log n)
  2. BO(log n)
  3. CO(n)
  4. DO(1)
8.Складна

Яка структура даних забезпечує кеш LRU (least recently used) з операціями get і put за O(1)?

  1. AГеш-мапа в поєднанні з двозв'язним списком
  2. BЛише стек
  3. CЛише бінарне дерево пошуку
  4. DОдин відсортований масив

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

  1. 1. D · Стек
  2. 2. C · Два різні ключі відображаються в один індекс
  3. 3. B · Відображає ключ в індекс у таблиці
  4. 4. C · Висоти лівого та правого піддерев відрізняються щонайбільше на 1
  5. 5. A · 20
  6. 6. A · Висоту O(log n) завдяки перебалансуванню
  7. 7. C · O(n)
  8. 8. A · Геш-мапа в поєднанні з двозв'язним списком

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