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

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

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

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

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

1.Легка

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

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

Що таке корінь дерева?

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

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

  1. AРядок із V булевих значень
  2. BЗагальна кількість ребер у графі
  3. CСписок сусідніх вершин
  4. DНайкоротший шлях до кожної іншої вершини
4.Середня

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

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

Яке значення постфіксного виразу 3 4 + 2 * ?

  1. A14
  2. B11
  3. C10
  4. D24
6.Середня

Бінарне дерево має корінь 1 з лівою дитиною 2 і правою дитиною 3; вузол 2 має дітей 4 (ліва) і 5 (права). Який зворотний обхід (postorder)?

  1. A1 2 4 5 3
  2. B4 2 5 1 3
  3. C4 5 2 3 1
  4. D5 4 3 2 1
7.Складна

Яка вартість однієї операції find у найгіршому випадку в структурі union-find з n елементами без об'єднання за рангом і стиснення шляхів?

  1. AO(n)
  2. BO(α(n))
  3. CO(1)
  4. DO(log n)
8.Складна

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

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

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

  1. 1. C · Стек
  2. 2. D · Верхній вузол, який не має батька
  3. 3. C · Список сусідніх вершин
  4. 4. C · В індексі ⌊(i − 1) / 2⌋
  5. 5. A · 14
  6. 6. C · 4 5 2 3 1
  7. 7. A · O(n)
  8. 8. C · Щоб перевірити, чи вже з'єднані два кінці ребра

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