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

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

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

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

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

1.Легка

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

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

Що таке властивість макс-купи?

  1. AКлюч кожного батька більший або дорівнює ключам його дітей
  2. BУсі листки містять максимальний ключ
  3. CКлючі відсортовано зліва направо
  4. DКлюч кожної лівої дитини більший або дорівнює ключу її правого брата чи сестри
3.Легка

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

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

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

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

Яку структуру даних використовує виконувана програма, щоб відстежувати активні виклики функцій та їхні локальні змінні?

  1. AСтек викликів
  2. BЧергу пам'яті купи
  3. CГеш-таблицю функцій
  4. DБінарне дерево пошуку фреймів
6.Середня

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

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

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

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

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

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

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

  1. 1. A · Повертає верхній елемент, не видаляючи його
  2. 2. A · Ключ кожного батька більший або дорівнює ключам його дітей
  3. 3. D · Дані, вказівник на наступний вузол і вказівник на попередній вузол
  4. 4. A · Останній елемент переміщують у корінь і просіюють униз
  5. 5. A · Стек викликів
  6. 6. B · Збалансоване бінарне дерево пошуку
  7. 7. A · Черга (або будь-яка колекція) вершин із напівстепенем входу 0
  8. 8. B · O(n) часу та O(1) додаткової пам'яті

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