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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

  1. AОно хранит пары ключ–значение
  2. BОно хранит элементы без повторений
  3. CОно допускает доступ только с одного конца
  4. DОно хранит элементы в отсортированном порядке
3.Лёгкая

Как называется операция стека, добавляющая элемент на вершину?

  1. APop
  2. BEnqueue
  3. CPeek
  4. DPush
4.Средняя

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

  1. A1 2 4 5 3
  2. B5 4 3 2 1
  3. C4 2 5 1 3
  4. D4 5 2 3 1
5.Средняя

Сколько памяти занимает матрица смежности графа с V вершинами?

  1. AO(V + E)
  2. BO(V²)
  3. CO(log V)
  4. DO(E)
6.Средняя

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

  1. AМаксимума нет
  2. B2
  3. C1
  4. D0,5
7.Сложная

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

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

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

  1. AПравый поворот в левом потомке, затем левый поворот в узле
  2. BОдиночный правый поворот в узле
  3. CОдиночный левый поворот в узле
  4. DЛевый поворот в левом потомке, затем правый поворот в узле

Ответы

  1. 1. D · Данные, указатель на следующий узел и указатель на предыдущий узел
  2. 2. B · Оно хранит элементы без повторений
  3. 3. D · Push
  4. 4. D · 4 5 2 3 1
  5. 5. B · O(V²)
  6. 6. C · 1
  7. 7. C · Все записи находятся в связанных листьях, что делает сканирование диапазонов эффективным
  8. 8. D · Левый поворот в левом потомке, затем правый поворот в узле

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