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

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

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

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

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

1.Легка

Яка визначальна риса множини як абстрактного типу даних?

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

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

  1. AEnqueue
  2. BPop
  3. CPeek
  4. DPush
3.Легка

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

  1. AГеш-множина
  2. BЧерга
  3. CСтек
  4. DГраф
4.Середня

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

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

Дорожня мережа має 100,000 перехресть, кожне з'єднане приблизно з 4 іншими. Яке подання найдоречніше?

  1. AМатриця суміжності
  2. BСписок суміжності
  3. CОдин відсортований масив вершин
  4. DБінарна купа ребер
6.Середня

Як знайти мінімальний ключ у бінарному дереві пошуку?

  1. AВідвідати кожен листок і порівняти їх
  2. BІти від кореня лівими дітьми, доки лівої дитини не буде
  3. CПодивитися лише на корінь
  4. DІти від кореня правими дітьми, доки правої дитини не буде
7.Складна

Алгоритм Кана для топологічного сортування раз у раз видаляє вершини з напівстепенем входу 0. Яка структура зберігає ці вершини?

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

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

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

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

  1. 1. D · Вона зберігає елементи без дублікатів
  2. 2. D · Push
  3. 3. C · Стек
  4. 4. D · O(L), незалежно від кількості збережених слів
  5. 5. B · Список суміжності
  6. 6. B · Іти від кореня лівими дітьми, доки лівої дитини не буде
  7. 7. B · Черга (або будь-яка колекція) вершин із напівстепенем входу 0
  8. 8. D · Усі листки розташовані на однаковій глибині

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