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

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

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

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

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

1.Легка

Що таке цикл у графі?

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

Префіксне дерево (trie) особливо ефективне для:

  1. AСортування чисел
  2. BЗберігання матриць
  3. CПошуку за префіксом, наприклад автодоповнення
  4. DПошуку найкоротших шляхів
6.Середня

Скільки часу потрібно, щоб перевірити наявність ребра (u, v) за допомогою матриці суміжності?

  1. AO(log V)
  2. BO(1)
  3. CO(E)
  4. DO(V)
7.Складна

Фільтр Блума може відповісти на запитання «чи належить цей елемент множині?»:

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

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

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

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

  1. 1. A · Шлях, що починається й закінчується в одній вершині
  2. 2. D · Два різні ключі відображаються в один індекс
  3. 3. D · Вона зберігає елементи без дублікатів
  4. 4. A · Іти від кореня лівими дітьми, доки лівої дитини не буде
  5. 5. C · Пошуку за префіксом, наприклад автодоповнення
  6. 6. B · O(1)
  7. 7. C · З можливими хибнопозитивними, але без хибнонегативних результатів
  8. 8. D · Одинарний правий поворот у незбалансованому вузлі

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