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

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

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

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

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

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

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

  1. A2i + 1
  2. Bi + 1
  3. C(i − 1) mod n
  4. D(i + 1) mod n
7.Складна

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

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

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

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

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

  1. 1. B · Верхній вузол, який не має батька
  2. 2. D · Купу
  3. 3. C · Дані та посилання на наступний вузол
  4. 4. C · O(V²)
  5. 5. A · O(V + E)
  6. 6. D · (i + 1) mod n
  7. 7. C · Зберігати окремий лічильник елементів або завжди залишати одну комірку невикористаною
  8. 8. B · Одинарний правий поворот у незбалансованому вузлі

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