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

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

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

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

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

1.Легка

Що таке коефіцієнт заповнення (load factor) геш-таблиці?

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

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

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

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

  1. AЗв'язний список
  2. BЧерга
  3. CСтек
  4. DГеш-таблиця
4.Середня

Вузол бінарного дерева пошуку має праве піддерево. Де розташований його наступник у симетричному порядку (in-order successor)?

  1. AКрайній лівий вузол його правого піддерева
  2. BКрайній правий вузол його лівого піддерева
  3. CЗавжди його права дитина
  4. DЗавжди його батько
5.Середня

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

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

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

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

Потрібно зберігати k найменших значень із потоку n чисел, використовуючи O(k) пам'яті. Який підхід працює за час O(n log k)?

  1. AВідсортований масив усіх n значень
  2. BЧерга FIFO з останніх k значень
  3. CМакс-купа розміру k, корінь якої замінюють, коли надходить менше значення
  4. DМін-купа, що містить усі n значень, з якої наприкінці вилучають k найменших
8.Складна

Яка структура дає змогу обчислити максимум кожного вікна розміру k у масиві за загальний час O(n)?

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

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

  1. 1. A · Кількість збережених елементів, поділена на кількість кошиків
  2. 2. B · Граф, у якому кожне ребро має числове значення, як-от вартість чи відстань
  3. 3. C · Стек
  4. 4. A · Крайній лівий вузол його правого піддерева
  5. 5. C · Елементи масиву розташовані суцільно, тож добре використовують кеш процесора
  6. 6. D · Мін-чергу з пріоритетом
  7. 7. C · Макс-купа розміру k, корінь якої замінюють, коли надходить менше значення
  8. 8. B · Дек, що зберігає індекси в порядку спадання значень

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