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

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

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

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

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

1.Легка

Висоту дерева зазвичай визначають як:

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

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

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

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

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

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

  1. A40
  2. B50
  3. C20
  4. D70
5.Середня

Скільки часу потрібно, щоб перевірити наявність ребра (u, v) за допомогою матриці суміжності?

  1. AO(1)
  2. BO(log V)
  3. CO(V)
  4. DO(E)
6.Середня

Скільки триває пошук слова довжиною L у префіксному дереві (trie) з фіксованим алфавітом?

  1. AO(n), де n — кількість слів
  2. BO(log n), де n — кількість слів
  3. CO(L), незалежно від кількості збережених слів
  4. DO(L × n)
7.Складна

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

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

Вузол AVL-дерева незбалансований, бо праве піддерево його лівої дитини стало надто високим (випадок «ліво-право»). Яке виправлення застосовують?

  1. AОдинарний правий поворот у вузлі
  2. BПравий поворот у лівій дитині, потім лівий поворот у вузлі
  3. CЛівий поворот у лівій дитині, потім правий поворот у вузлі
  4. DОдинарний лівий поворот у вузлі

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

  1. 1. A · Кількість ребер на найдовшому шляху від кореня до листка
  2. 2. C · Повертає верхній елемент, не видаляючи його
  3. 3. B · Вершин (вузлів), з'єднаних ребрами
  4. 4. C · 20
  5. 5. A · O(1)
  6. 6. C · O(L), незалежно від кількості збережених слів
  7. 7. D · З можливими хибнопозитивними, але без хибнонегативних результатів
  8. 8. C · Лівий поворот у лівій дитині, потім правий поворот у вузлі

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