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

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

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

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

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

1.Легка

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

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

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

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

Яка операція має складність O(1) для масиву, але O(n) для однозв'язного списку?

  1. AЧитання першого елемента
  2. BДоступ до елемента з індексом i
  3. CВидалення головного елемента
  4. DВставлення на початок
4.Середня

Ключі 50, 30, 70, 20, 40 вставляють у такому порядку в порожнє бінарне дерево пошуку. Яка ліва дитина вузла 30?

  1. A20
  2. B50
  3. C70
  4. D40
5.Середня

Дорожня мережа має 100,000 перехресть, кожне з'єднане приблизно з 4 іншими. Яке подання найдоречніше?

  1. AОдин відсортований масив вершин
  2. BМатриця суміжності
  3. CСписок суміжності
  4. DБінарна купа ребер
6.Середня

Скільки часу потрібно, щоб перевірити наявність ребра (u, v) за допомогою матриці суміжності?

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

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

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

Алгоритм Кана для топологічного сортування раз у раз видаляє вершини з напівстепенем входу 0. Яка структура зберігає ці вершини?

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

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

  1. 1. D · Вузол, потім ліве піддерево, потім праве піддерево
  2. 2. A · Вершин (вузлів), з'єднаних ребрами
  3. 3. B · Доступ до елемента з індексом i
  4. 4. A · 20
  5. 5. C · Список суміжності
  6. 6. B · O(1)
  7. 7. C · Поворотами піднімає вузол, до якого звернулися, у корінь
  8. 8. B · Черга (або будь-яка колекція) вершин із напівстепенем входу 0

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