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

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

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

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

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

1.Легка

Що таке зважений граф?

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

У якому порядку прямий обхід (preorder) бінарного дерева відвідує вузли?

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

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

  1. AЛінійне зондування
  2. BМетод ланцюжків (separate chaining)
  3. CПодвійне гешування
  4. DКвадратичне зондування
6.Середня

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

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

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

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

Потрібно зберігати k найменших значень із потоку n чисел, використовуючи O(k) пам'яті. Який підхід працює за час O(n log k)?

  1. AМін-купа, що містить усі n значень, з якої наприкінці вилучають k найменших
  2. BЧерга FIFO з останніх k значень
  3. CМакс-купа розміру k, корінь якої замінюють, коли надходить менше значення
  4. DВідсортований масив усіх n значень

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

  1. 1. B · Граф, у якому кожне ребро має числове значення, як-от вартість чи відстань
  2. 2. D · Вузол, потім ліве піддерево, потім праве піддерево
  3. 3. C · Кожен вузол має щонайбільше двох дітей
  4. 4. D · Іти від кореня лівими дітьми, доки лівої дитини не буде
  5. 5. B · Метод ланцюжків (separate chaining)
  6. 6. D · Елементи масиву розташовані суцільно, тож добре використовують кеш процесора
  7. 7. B · Лівий поворот у лівій дитині, потім правий поворот у вузлі
  8. 8. C · Макс-купа розміру k, корінь якої замінюють, коли надходить менше значення

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