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

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

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

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

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

1.Легка

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

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

У бінарному дереві пошуку значення в лівому піддереві вузла:

  1. AДорівнюють значенню вузла
  2. BБільші за значення вузла
  3. CМенші за значення вузла
  4. DРозташовані у випадковому порядку
3.Легка

Що робить операція peek (або top) стека?

  1. AПовертає нижній елемент стека
  2. BПовертає верхній елемент, не видаляючи його
  3. CВидаляє верхній елемент і повертає його
  4. DВидаляє всі елементи зі стека
4.Середня

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

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

Яка часова складність пошуку ключа в збалансованому бінарному дереві пошуку?

  1. AO(n)
  2. BO(log n)
  3. CO(n log n)
  4. DO(1)
6.Середня

Застосунку потрібен швидкий пошук, а також виведення ключів у відсортованому порядку та відповіді на запити діапазону. Яка структура підходить найкраще?

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

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

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

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

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

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

  1. 1. C · Ліве піддерево, потім праве піддерево, потім вузол
  2. 2. C · Менші за значення вузла
  3. 3. B · Повертає верхній елемент, не видаляючи його
  4. 4. C · Список суміжності
  5. 5. B · O(log n)
  6. 6. B · Збалансоване бінарне дерево пошуку
  7. 7. B · Поворотами піднімає вузол, до якого звернулися, у корінь
  8. 8. C · O(n) часу та O(1) додаткової пам'яті

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