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

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

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

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

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

1.Легка

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

  1. AАдресу першого вузла
  2. BNull (жодного вузла)
  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(n), де n — кількість слів
  2. BO(log n), де n — кількість слів
  3. CO(L × n)
  4. DO(L), незалежно від кількості збережених слів
5.Середня

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

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

Яка вартість вставлення елемента в середину масиву з n елементів?

  1. AO(n), бо наступні елементи доводиться зсувати
  2. BO(1), бо індекс відомий
  3. CO(n²), бо кожен елемент переміщується n разів
  4. DO(log n) через бінарний пошук
7.Складна

Вставлення ключа в AVL-дерево робить ліве піддерево вузла надто високим, причому новий ключ потрапив у ліве піддерево його лівої дитини (випадок «ліво-ліво»). Яке виправлення застосовують?

  1. AОдинарний лівий поворот у незбалансованому вузлі
  2. BПерефарбування вузла та його дитини
  3. CЛівий поворот у дитині, потім правий поворот у вузлі
  4. DОдинарний правий поворот у незбалансованому вузлі
8.Складна

Динамічний масив подвоюється, коли заповнюється. Чому багато реалізацій зменшують його лише тоді, коли він заповнений на чверть, а не наполовину?

  1. AЩоб масив залишався відсортованим
  2. BБо зменшення вдвічі за половинного заповнення призвело б до втрати елементів
  3. CЩоб уникнути повторних змін розміру, коли push і pop чергуються біля межі
  4. DБо розподілювач пам'яті може звільняти пам'ять лише чвертями блока

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

  1. 1. B · Null (жодного вузла)
  2. 2. B · Кожен вузол має щонайбільше двох дітей
  3. 3. A · Менші за значення вузла
  4. 4. D · O(L), незалежно від кількості збережених слів
  5. 5. A · O(V²)
  6. 6. A · O(n), бо наступні елементи доводиться зсувати
  7. 7. D · Одинарний правий поворот у незбалансованому вузлі
  8. 8. C · Щоб уникнути повторних змін розміру, коли push і pop чергуються біля межі

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