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

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

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

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

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

1.Легка

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

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

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

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

Що таке дек (deque, двостороння черга)?

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

Як працює extract-min у бінарній мін-купі?

  1. AШукають новий мінімум серед усіх листків
  2. BВидаляють корінь і зсувають усі елементи на одну позицію ліворуч
  3. CОстанній елемент переміщують у корінь і просіюють униз
  4. DВидаляють останній елемент масиву
5.Середня

Яка вартість вставлення елемента в середину масиву з n елементів?

  1. AO(1), бо індекс відомий
  2. BO(n²), бо кожен елемент переміщується n разів
  3. CO(log n) через бінарний пошук
  4. DO(n), бо наступні елементи доводиться зсувати
6.Середня

Чому обхід масиву на практиці часто значно швидший, ніж обхід зв'язного списку такої самої довжини?

  1. AЕлементи масиву розташовані суцільно, тож добре використовують кеш процесора
  2. BЗв'язні списки завжди зберігають елементи на диску
  3. CМасиви використовують менше інструкцій для порівняння значень
  4. DОбхід масиву загалом має складність O(1), а обхід зв'язного списку — O(n)
7.Складна

Якого правила мають дотримуватися геш і рівність, щоб геш-таблиця працювала правильно?

  1. AРівні ключі мусять мати рівні геш-значення
  2. BРізні ключі мусять мати різні геш-значення
  3. CГеш-значення мусять бути простими числами
  4. DРівні геш-значення означають рівні ключі
8.Складна

Яка основна перевага списку з пропусками (skip list) над відсортованим зв'язним списком?

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

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

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

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