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

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

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

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

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

1.Легка

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

  1. AInsert
  2. BPush
  3. CEnqueue
  4. DDequeue
2.Легка

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

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

Що зберігає відображення (map, словник)?

  1. AЗначення, відсортовані за розміром
  2. BПари ключ–значення з унікальними ключами
  3. CПари однакових ключів
  4. DЛише значення в порядку вставлення
4.Середня

У бінарній мін-купі, що зберігається в масиві (індексація з 0), діти вузла з індексом i розташовані на позиціях:

  1. Ai/2 і i/2 + 1
  2. Bi + 1 і i + 2
  3. C2i + 1 і 2i + 2
  4. D2i і 2i + 1
5.Середня

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

  1. AO(1)
  2. BO(log n)
  3. CO(n log n)
  4. DO(n)
6.Середня

Яку структуру даних використовують, щоб перевірити, чи збалансовані дужки в «{[()]}»?

  1. AСтек
  2. BГеш-таблицю
  3. CБінарне дерево пошуку
  4. DЧергу
7.Складна

У BST з коренем 50, лівим піддеревом 30 (діти 20, 40) і правим піддеревом 70 (діти 60, 80) корінь видаляють за допомогою наступника в симетричному порядку. Який ключ стає новим коренем?

  1. A80
  2. B40
  3. C70
  4. D60
8.Складна

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

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

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

  1. 1. D · Dequeue
  2. 2. B · Повертає верхній елемент, не видаляючи його
  3. 3. B · Пари ключ–значення з унікальними ключами
  4. 4. C · 2i + 1 і 2i + 2
  5. 5. B · O(log n)
  6. 6. A · Стек
  7. 7. D · 60
  8. 8. D · Щоб зробити дуже малоймовірним, що зловмисник підбере багато ключів, які всі матимуть колізію

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