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

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

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

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

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

1.Легка

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

  1. AЧитання першого елемента
  2. BДоступ до елемента з індексом i
  3. CВидалення головного елемента
  4. DВставлення на початок
2.Легка

Яка визначальна риса множини як абстрактного типу даних?

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

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

  1. AСписок сусідніх вершин
  2. BРядок із V булевих значень
  3. CНайкоротший шлях до кожної іншої вершини
  4. DЗагальна кількість ребер у графі
4.Середня

Що відбувається, коли геш-таблиця виконує повторне гешування (rehash) після того, як коефіцієнт заповнення перевищив поріг?

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

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

  1. AВідвідати кожен листок і порівняти їх
  2. BІти від кореня правими дітьми, доки правої дитини не буде
  3. CПодивитися лише на корінь
  4. DІти від кореня лівими дітьми, доки лівої дитини не буде
6.Середня

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

  1. AЛінійне зондування
  2. BМетод ланцюжків (separate chaining)
  3. CКвадратичне зондування
  4. DПодвійне гешування
7.Складна

Яка структура дає змогу обчислити максимум кожного вікна розміру k у масиві за загальний час O(n)?

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

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

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

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

  1. 1. B · Доступ до елемента з індексом i
  2. 2. C · Вона зберігає елементи без дублікатів
  3. 3. A · Список сусідніх вершин
  4. 4. A · Виділяється більша таблиця, і кожен ключ вставляється знову
  5. 5. D · Іти від кореня лівими дітьми, доки лівої дитини не буде
  6. 6. B · Метод ланцюжків (separate chaining)
  7. 7. C · Дек, що зберігає індекси в порядку спадання значень
  8. 8. D · Лівий поворот у лівій дитині, потім правий поворот у вузлі

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