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

Безкоштовний робочий аркуш для друку «Структури даних»: 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.Середня

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

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

Скільки пам'яті займає матриця суміжності графа з V вершинами?

  1. AO(V²)
  2. BO(V + E)
  3. CO(log V)
  4. DO(E)
6.Середня

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

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

Якій властивості має відповідати червоно-чорне дерево?

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

У BST з коренем 50, лівим піддеревом 30 (діти 20, 40) і правим піддеревом 70 (діти 60, 80) корінь видаляють за допомогою наступника в симетричному порядку. Який ключ стає новим коренем?

  1. A70
  2. B80
  3. C40
  4. D60

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

  1. 1. D · Кількість ребер на найдовшому шляху від кореня до листка
  2. 2. B · Одним суцільним блоком, один за одним
  3. 3. B · Купу
  4. 4. A · O(L), незалежно від кількості збережених слів
  5. 5. A · O(V²)
  6. 6. B · Стек
  7. 7. A · Кожен шлях від вузла до його листків-нащадків містить однакову кількість чорних вузлів
  8. 8. D · 60

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