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

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

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

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

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

1.Легка

Що таке вузли-брати (siblings) у дереві?

  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.Середня

Як вставляють новий елемент у бінарну купу?

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

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

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

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

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

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

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

Дерево відрізків (segment tree) зазвичай використовують для:

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

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

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

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