Структуры данных: лист заданий с ответами

Бесплатный лист заданий для печати по теме «Структуры данных»: 8 задач от простых до экзаменационного уровня, с ответами. Распечатайте его или сохраните как PDF.

Новый лист заданийЗаниматься онлайн с подсказками

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое свойство max-кучи?

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

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

  1. AОчередь
  2. BХеш-таблица
  3. CСтек
  4. DСвязный список
3.Лёгкая

Какая структура данных используется для обхода дерева по уровням (level-order)?

  1. AОчередь
  2. BХеш-таблица
  3. CОчередь с приоритетом
  4. DСтек
4.Средняя

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

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

Как найти минимальный ключ в двоичном дереве поиска?

  1. AИдти от корня по правым потомкам, пока правого потомка не окажется
  2. BОбойти все листья и сравнить их
  3. CИдти от корня по левым потомкам, пока левого потомка не окажется
  4. DПосмотреть только на корень
7.Сложная

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

  1. AЧтобы хеш-таблица была отсортирована
  2. BЧтобы не нужно было увеличивать таблицу
  3. CЧтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем
  4. DЧтобы гарантировать, что никакие два ключа никогда не столкнутся, какие бы ключи ни присылал атакующий
8.Сложная

Почему базы данных часто используют для индексов B+ деревья, а не обычные B-деревья?

  1. AB+ деревья используют двоичные внутренние узлы, что сокращает число чтений с диска
  2. BВсе записи находятся в связанных листьях, что делает сканирование диапазонов эффективным
  3. CB+ деревья хранят данные только в корне
  4. DB+ деревья не нужно балансировать

Ответы

  1. 1. C · Ключ каждого родителя больше или равен ключам его потомков
  2. 2. C · Стек
  3. 3. A · Очередь
  4. 4. A · O(log n)
  5. 5. A · 20
  6. 6. C · Идти от корня по левым потомкам, пока левого потомка не окажется
  7. 7. C · Чтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем
  8. 8. B · Все записи находятся в связанных листьях, что делает сканирование диапазонов эффективным

Полные пошаговые решения: занимайтесь этой темой на examproblems.com.