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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. AЧисло узлов в списке
  2. BАдрес предыдущего узла
  3. CАдрес первого узла
  4. DNull (узла нет)
2.Лёгкая

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

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

Высота дерева обычно определяется как:

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

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

  1. AПоиск за константное время в любом случае
  2. BХранение ключей в порядке вставки
  3. CВысоту O(log n) благодаря перебалансировке
  4. DЧто ни у одного узла нет двух потомков
5.Средняя

Что верно для матрицы смежности неориентированного графа?

  1. AВ каждой строке ровно одна 1
  2. BОна всегда верхнетреугольная
  3. CНа её главной диагонали всегда стоят единицы
  4. DОна симметрична относительно главной диагонали
6.Средняя

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

  1. AСписки смежности
  2. BДвоичная куча рёбер
  3. CОдин отсортированный массив вершин
  4. DМатрица смежности
7.Сложная

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

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

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

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

Ответы

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

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