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

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

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

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

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

1.Легка

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

  1. AЛіве піддерево, потім праве піддерево, потім вузол
  2. BЛіве піддерево, потім вузол, потім праве піддерево
  3. CПраве піддерево, потім вузол, потім ліве піддерево
  4. DВузол, потім ліве піддерево, потім праве піддерево
2.Легка

Що таке цикл у графі?

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

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

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

Що правильно щодо матриці суміжності неорієнтованого графа?

  1. AЇї головна діагональ завжди містить одиниці
  2. BКожен рядок містить рівно одну 1
  3. CВона симетрична відносно головної діагоналі
  4. DВона завжди верхньотрикутна
5.Середня

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

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

Що відбувається, коли геш-таблиця виконує повторне гешування (rehash) після того, як коефіцієнт заповнення перевищив поріг?

  1. AЛише ключі з колізіями переміщуються в новий список переповнення в кінці таблиці
  2. BВиділяється більша таблиця, і кожен ключ вставляється знову
  3. CНаявні ключі сортуються на місці
  4. DНайстаріші ключі видаляються, щоб звільнити місце
7.Складна

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

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

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

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

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

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

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