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

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

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

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

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

1.Легка

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

  1. APeek
  2. BPush
  3. CEnqueue
  4. DPop
2.Легка

Що таке листок у дереві?

  1. AВузол без дітей
  2. BВузол із найбільшим значенням
  3. CВузол без батька
  4. DВузол рівно з однією дитиною
3.Легка

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

  1. AНевпорядкований однозв'язний список
  2. BКупу
  3. CРядок
  4. DСтек
4.Середня

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

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

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

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

Як вставляють новий елемент у бінарну купу?

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

Які витрати часу й додаткової пам'яті на обернення однозв'язного списку на місці?

  1. AO(n) часу та O(n) додаткової пам'яті
  2. BO(1) часу та O(1) додаткової пам'яті
  3. CO(n log n) часу та O(1) додаткової пам'яті
  4. DO(n) часу та O(1) додаткової пам'яті
8.Складна

Для чого використовують структуру union-find в алгоритмі Краскала для мінімального кістякового дерева?

  1. AЩоб відсортувати ребра за вагою
  2. BЩоб обрати початкову вершину
  3. CЩоб перевірити, чи вже з'єднані два кінці ребра
  4. DЩоб зберігати поточну відстань кожної вершини від джерела під час пошуку

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

  1. 1. B · Push
  2. 2. A · Вузол без дітей
  3. 3. B · Купу
  4. 4. D · Крайній лівий вузол його правого піддерева
  5. 5. B · Пошуку за префіксом, наприклад автодоповнення
  6. 6. A · Розміщують його в кінці масиву й просіюють угору, поки він порушує властивість купи
  7. 7. D · O(n) часу та O(1) додаткової пам'яті
  8. 8. C · Щоб перевірити, чи вже з'єднані два кінці ребра

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