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

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

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

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

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

1.Легка

Що містить вказівник next останнього вузла однозв'язного списку?

  1. AАдресу першого вузла
  2. BАдресу попереднього вузла
  3. CNull (жодного вузла)
  4. DКількість вузлів у списку
2.Легка

Граф складається з:

  1. AЛише кореня та листків
  2. BВершин (вузлів), з'єднаних ребрами
  3. CРядків і стовпців
  4. DЛише ключів і гешів
3.Легка

В однозв'язному списку кожен вузол містить:

  1. AДані та індекс
  2. BЛише дані
  3. CДані та посилання на наступний вузол
  4. DДані та посилання на всі інші вузли
4.Середня

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

  1. A(i − 1) mod n
  2. B(i + 1) mod n
  3. C2i + 1
  4. Di + 1
5.Середня

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

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

Як працює extract-min у бінарній мін-купі?

  1. AОстанній елемент переміщують у корінь і просіюють униз
  2. BШукають новий мінімум серед усіх листків
  3. CВидаляють останній елемент масиву
  4. DВидаляють корінь і зсувають усі елементи на одну позицію ліворуч
7.Складна

Яку гарантію щодо висоти дерева з n ключами дають правила червоно-чорного дерева?

  1. AВисота щонайбільше 2 log2(n + 1)
  2. BВисота щонайбільше n / 2
  3. CВисота щонайбільше log2 n + 1
  4. DВисота рівно log2 n
8.Складна

Часова складність операції decrease-key у бінарній купі (за відомої позиції елемента) становить:

  1. AO(n)
  2. BO(log n)
  3. CO(1)
  4. DO(n log n)

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

  1. 1. C · Null (жодного вузла)
  2. 2. B · Вершин (вузлів), з'єднаних ребрами
  3. 3. C · Дані та посилання на наступний вузол
  4. 4. B · (i + 1) mod n
  5. 5. C · Мін-чергу з пріоритетом
  6. 6. A · Останній елемент переміщують у корінь і просіюють униз
  7. 7. A · Висота щонайбільше 2 log2(n + 1)
  8. 8. B · O(log n)

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