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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что содержит каждый узел двусвязного списка?

  1. AДанные и только указатель на следующий узел
  2. BДве копии данных и один указатель
  3. CДанные и два указателя: один на следующий узел и один на узел после него
  4. DДанные, указатель на следующий узел и указатель на предыдущий узел
2.Лёгкая

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

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

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

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

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

  1. AСвязные списки всегда хранят элементы на диске
  2. BЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
  3. CМассивы требуют меньше инструкций для сравнения значений
  4. DОбход массива занимает в сумме O(1), а связного списка — O(n)
5.Средняя

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

  1. A50
  2. B40
  3. C70
  4. D20
6.Средняя

Какой абстрактный тип данных использует алгоритм Дейкстры для выбора следующей обрабатываемой вершины?

  1. AСтек
  2. BОчередь FIFO
  3. CОчередь с приоритетом по минимуму
  4. DМножество без упорядочения
7.Сложная

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

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

Как определить, есть ли цикл в односвязном списке, используя O(1) дополнительной памяти?

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

Ответы

  1. 1. D · Данные, указатель на следующий узел и указатель на предыдущий узел
  2. 2. B · Стек
  3. 3. C · Узел, затем левое поддерево, затем правое поддерево
  4. 4. B · Элементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
  5. 5. D · 20
  6. 6. C · Очередь с приоритетом по минимуму
  7. 7. C · Высокая степень ветвления делает дерево неглубоким и сокращает число медленных чтений с диска
  8. 8. B · Двигать один указатель на один шаг, а другой на два и проверять, встретятся ли они

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