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

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

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

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

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

1.Легка

Що визначає бінарне дерево?

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

Що таке корінь дерева?

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

Що таке властивість макс-купи?

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

Ключі 50, 30, 70, 20, 40 вставляють у такому порядку в порожнє бінарне дерево пошуку. Яка ліва дитина вузла 30?

  1. A50
  2. B20
  3. C40
  4. D70
5.Середня

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

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

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

  1. AO(1)
  2. BO(n log n)
  3. CO(log n)
  4. DO(n)
7.Складна

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

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

Який очікуваний час пошуку за простого рівномірного гешування в геш-таблиці з ланцюжками, n ключами та m кошиками?

  1. AO(1 + α), де α = n / m
  2. BO(n)
  3. CO(log n)
  4. DO(m)

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

  1. 1. A · Кожен вузол має щонайбільше двох дітей
  2. 2. C · Верхній вузол, який не має батька
  3. 3. C · Ключ кожного батька більший або дорівнює ключам його дітей
  4. 4. B · 20
  5. 5. A · Збалансоване бінарне дерево пошуку
  6. 6. C · O(log n)
  7. 7. C · Черга (або будь-яка колекція) вершин із напівстепенем входу 0
  8. 8. A · O(1 + α), де α = n / m

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