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

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

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

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

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

1.Легка

Що таке вузли-брати (siblings) у дереві?

  1. AВузли на однаковій глибині в різних піддеревах
  2. BВузли зі спільним батьком
  3. CВузол і його батько
  4. DВузли без дітей
2.Легка

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

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

Яку структуру даних використовують для обходу дерева по рівнях?

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

Яку структуру даних використовує пошук у глибину (DFS, ітеративна версія)?

  1. AСтек
  2. BКупа
  3. CЛише геш-таблиця
  4. DЧерга
5.Середня

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

  1. Ai + 1
  2. B(i + 1) mod n
  3. C(i − 1) mod n
  4. D2i + 1
6.Середня

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

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

Чому бази даних для індексів часто використовують B+ дерева, а не звичайні B-дерева?

  1. AB+ дерева не потребують збалансування
  2. BB+ дерева використовують бінарні внутрішні вузли, що зменшує кількість зчитувань із диска
  3. CУсі записи розташовані у зв'язаних листках, що робить сканування діапазонів ефективним
  4. DB+ дерева зберігають дані лише в корені
8.Складна

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

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

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

  1. 1. B · Вузли зі спільним батьком
  2. 2. C · Доступ до елемента з індексом i
  3. 3. C · Чергу
  4. 4. A · Стек
  5. 5. B · (i + 1) mod n
  6. 6. C · O(L), незалежно від кількості збережених слів
  7. 7. C · Усі записи розташовані у зв'язаних листках, що робить сканування діапазонів ефективним
  8. 8. C · O(n) часу та O(1) додаткової пам'яті

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