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

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

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

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

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

1.Легка

Що таке дек (deque, двостороння черга)?

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

Яку структуру даних використовує виконувана програма, щоб відстежувати активні виклики функцій та їхні локальні змінні?

  1. AГеш-таблицю функцій
  2. BБінарне дерево пошуку фреймів
  3. CСтек викликів
  4. DЧергу пам'яті купи
5.Середня

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

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

У бінарній мін-купі, що зберігається в масиві (індексація з 0), діти вузла з індексом i розташовані на позиціях:

  1. A2i і 2i + 1
  2. Bi/2 і i/2 + 1
  3. C2i + 1 і 2i + 2
  4. Di + 1 і i + 2
7.Складна

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

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

Які витрати часу й додаткової пам'яті на обернення однозв'язного списку на місці?

  1. AO(n log n) часу та O(1) додаткової пам'яті
  2. BO(n) часу та O(1) додаткової пам'яті
  3. CO(n) часу та O(n) додаткової пам'яті
  4. DO(1) часу та O(1) додаткової пам'яті

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

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

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