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

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

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

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

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

1.Легка

Що таке зважений граф?

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

Яка структура даних працює за принципом «першим прийшов — першим вийшов» (FIFO)?

  1. AСтек
  2. BКупа
  3. CЧерга
  4. DБінарне дерево
3.Легка

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

  1. ADequeue
  2. BPush
  3. CInsert
  4. DEnqueue
4.Середня

Скільки триває пошук слова довжиною L у префіксному дереві (trie) з фіксованим алфавітом?

  1. AO(L), незалежно від кількості збережених слів
  2. BO(log n), де n — кількість слів
  3. CO(L × n)
  4. DO(n), де n — кількість слів
5.Середня

Який абстрактний тип даних використовує алгоритм Дейкстри, щоб обрати наступну вершину для обробки?

  1. AЧергу FIFO
  2. BМін-чергу з пріоритетом
  3. CМножину без упорядкування
  4. DСтек
6.Середня

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

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

Чому в геш-таблиці з відкритою адресацією видалення часто виконують за допомогою позначки «надгробок» (tombstone)?

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

Об'єкт зберігається як ключ у геш-відображенні (hash map), а потім змінюється поле, яке використовує його геш-функція. Який імовірний результат?

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

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

  1. 1. D · Граф, у якому кожне ребро має числове значення, як-от вартість чи відстань
  2. 2. C · Черга
  3. 3. A · Dequeue
  4. 4. A · O(L), незалежно від кількості збережених слів
  5. 5. B · Мін-чергу з пріоритетом
  6. 6. C · Метод ланцюжків (separate chaining)
  7. 7. B · Звільнення комірки могло б розірвати послідовність зондування для інших ключів
  8. 8. C · Пошук об'єкта може не вдатися, бо він лежить у кошику для свого старого гешу

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