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

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

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

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

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

1.Легка

Що робить операція peek (або top) стека?

  1. AВидаляє всі елементи зі стека
  2. BПовертає верхній елемент, не видаляючи його
  3. CПовертає нижній елемент стека
  4. DВидаляє верхній елемент і повертає його
2.Легка

Що таке степінь вершини в неорієнтованому графі?

  1. AКількість вершин у графі
  2. BКількість ребер, з'єднаних із нею
  3. CДовжина найдовшого шляху з неї
  4. DЇї позиція в списку суміжності
3.Легка

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

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

Який максимально можливий коефіцієнт заповнення геш-таблиці з відкритою адресацією?

  1. AМаксимуму немає
  2. B1
  3. C2
  4. D0,5
5.Середня

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

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

AVL-дерева та червоно-чорні дерева гарантують:

  1. AЩо жоден вузол не має двох дітей
  2. BПошук за сталий час у будь-якому випадку
  3. CВисоту O(log n) завдяки перебалансуванню
  4. DЗберігання ключів у порядку вставлення
7.Складна

Яка пара обходів завжди однозначно визначає бінарне дерево з різними ключами?

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

Яке твердження про пірамідальне сортування (heapsort) правильне?

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

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

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

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