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

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

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

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

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

1.Легка

Що містить вказівник next останнього вузла однозв'язного списку?

  1. ANull (жодного вузла)
  2. BАдресу першого вузла
  3. CКількість вузлів у списку
  4. DАдресу попереднього вузла
2.Легка

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

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

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

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

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

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

Застосунку потрібен швидкий пошук, а також виведення ключів у відсортованому порядку та відповіді на запити діапазону. Яка структура підходить найкраще?

  1. AСтек
  2. BЗбалансоване бінарне дерево пошуку
  3. CНевідсортований зв'язний список
  4. DГеш-таблиця
6.Середня

Як працює extract-min у бінарній мін-купі?

  1. AВидаляють корінь і зсувають усі елементи на одну позицію ліворуч
  2. BОстанній елемент переміщують у корінь і просіюють униз
  3. CШукають новий мінімум серед усіх листків
  4. DВидаляють останній елемент масиву
7.Складна

Видалення вузла з двома дітьми з бінарного дерева пошуку зазвичай виконують так:

  1. AЗамінюють його in-order наступником (або попередником) і видаляють той вузол
  2. BМіняють його місцями з коренем
  3. CПеребудовують піддерево під ним з нуля й повторно вставляють усі ключі, які воно містило
  4. DВидаляють усе піддерево
8.Складна

Об'єкт зберігається як ключ у геш-відображенні (hash map), а потім змінюється поле, яке використовує його геш-функція. Який імовірний результат?

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

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

  1. 1. A · Null (жодного вузла)
  2. 2. D · Ліве піддерево, потім праве піддерево, потім вузол
  3. 3. A · Вузли зі спільним батьком
  4. 4. B · Список суміжності
  5. 5. B · Збалансоване бінарне дерево пошуку
  6. 6. B · Останній елемент переміщують у корінь і просіюють униз
  7. 7. A · Замінюють його in-order наступником (або попередником) і видаляють той вузол
  8. 8. A · Пошук об'єкта може не вдатися, бо він лежить у кошику для свого старого гешу

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