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

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

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

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

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

1.Легка

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

  1. ADequeue
  2. BInsert
  3. CEnqueue
  4. DPush
2.Легка

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

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

У якому порядку зворотний обхід (postorder) бінарного дерева відвідує вузли?

  1. AПраве піддерево, потім вузол, потім ліве піддерево
  2. BЛіве піддерево, потім вузол, потім праве піддерево
  3. CЛіве піддерево, потім праве піддерево, потім вузол
  4. DВузол, потім ліве піддерево, потім праве піддерево
4.Середня

Який метод розв'язання колізій зберігає ключі, що конфліктують, у списку в тому самому кошику?

  1. AМетод ланцюжків (separate chaining)
  2. BЛінійне зондування
  3. CПодвійне гешування
  4. DКвадратичне зондування
5.Середня

Скільки вузлів має ідеальне бінарне дерево висоти h, якщо висоту рахують у ребрах?

  1. A2h
  2. Bh2
  3. C2h + 1
  4. D2h+1 − 1
6.Середня

Що правильно щодо матриці суміжності неорієнтованого графа?

  1. AКожен рядок містить рівно одну 1
  2. BВона завжди верхньотрикутна
  3. CВона симетрична відносно головної діагоналі
  4. DЇї головна діагональ завжди містить одиниці
7.Складна

Яка пара обходів завжди однозначно визначає бінарне дерево з різними ключами?

  1. AЛише обхід по рівнях
  2. BПрямий і симетричний обходи
  3. CПрямий і зворотний обходи
  4. DЛише прямий обхід
8.Складна

Який очікуваний час пошуку за простого рівномірного гешування в геш-таблиці з ланцюжками, n ключами та m кошиками?

  1. AO(log n)
  2. BO(n)
  3. CO(1 + α), де α = n / m
  4. DO(m)

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

  1. 1. A · Dequeue
  2. 2. C · Купу
  3. 3. C · Ліве піддерево, потім праве піддерево, потім вузол
  4. 4. A · Метод ланцюжків (separate chaining)
  5. 5. D · 2h+1 − 1
  6. 6. C · Вона симетрична відносно головної діагоналі
  7. 7. B · Прямий і симетричний обходи
  8. 8. C · O(1 + α), де α = n / m

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