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

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

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

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

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

1.Легка

Граф складається з:

  1. AЛише кореня та листків
  2. BРядків і стовпців
  3. CЛише ключів і гешів
  4. DВершин (вузлів), з'єднаних ребрами
2.Легка

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

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

Геш-таблиця (hash table) зберігає дані у вигляді:

  1. AРядка фіксованої довжини
  2. BЛише відсортованого списку
  3. CДерева з упорядкованими ключами
  4. DПар ключ–значення, розташування яких визначає геш-функція
4.Середня

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

  1. AВ індексі i − 1
  2. BВ індексі 2i + 1
  3. CВ індексі ⌊i / 2⌋ + 1
  4. DВ індексі ⌊(i − 1) / 2⌋
5.Середня

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

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

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

  1. A1
  2. Bn (дерево перетворюється на зв'язний список)
  3. Clog₂ n
  4. D√n
7.Складна

У циклічному буфері front == rear може означати як порожній, так і заповнений буфер. Який поширений спосіб їх розрізнити?

  1. AЗберігати front і rear в одній змінній
  2. BЗберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
  3. CРобити розмір буфера степенем двійки
  4. DЗавжди очищати буфер щоразу, коли front дорівнює rear, тож стан — порожній
8.Складна

Яку проблему лінійного зондування переважно зменшує подвійне гешування?

  1. AПотребу зберігати ключі в таблиці
  2. BПотребу в геш-функції
  3. CВартість O(n) читання значення ключа
  4. DПервинну кластеризацію, коли утворюються довгі серії зайнятих комірок

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

  1. 1. D · Вершин (вузлів), з'єднаних ребрами
  2. 2. A · Null (жодного вузла)
  3. 3. D · Пар ключ–значення, розташування яких визначає геш-функція
  4. 4. D · В індексі ⌊(i − 1) / 2⌋
  5. 5. C · O(V²)
  6. 6. B · n (дерево перетворюється на зв'язний список)
  7. 7. B · Зберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
  8. 8. D · Первинну кластеризацію, коли утворюються довгі серії зайнятих комірок

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