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

Безкоштовний робочий аркуш для друку «Структури даних»: 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.Середня

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

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

Де розташований батько вузла з індексом i в бінарній купі, що зберігається в масиві з індексацією від 0?

  1. AВ індексі i − 1
  2. BВ індексі 2i + 1
  3. CВ індексі ⌊(i − 1) / 2⌋
  4. DВ індексі ⌊i / 2⌋ + 1
6.Середня

Скільки пам'яті використовує список суміжності для графа з V вершинами та E ребрами?

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

Що робить розширюване дерево (splay tree) після кожного звертання?

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

Для кожного елемента масиву потрібно знайти наступний більший елемент праворуч від нього за загальний час O(n). Яка структура допоможе?

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

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

  1. 1. A · Купу
  2. 2. C · Дані та посилання на наступний вузол
  3. 3. D · Відображає ключ в індекс у таблиці
  4. 4. C · O(L), незалежно від кількості збережених слів
  5. 5. C · В індексі ⌊(i − 1) / 2⌋
  6. 6. C · O(V + E)
  7. 7. C · Поворотами піднімає вузол, до якого звернулися, у корінь
  8. 8. D · Стек, що зберігає елементи, які чекають на свою відповідь

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