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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Граф состоит из:

  1. AВершин (узлов), соединённых рёбрами
  2. BТолько ключей и хешей
  3. CСтрок и столбцов
  4. DТолько корня и листьев
2.Лёгкая

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

  1. AСтек
  2. BОчередь
  3. CХеш-множество
  4. DГраф
3.Лёгкая

Что такое ориентированный граф?

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

  1. Ai + 1
  2. B2i + 1
  3. C(i + 1) mod n
  4. D(i − 1) mod n
5.Средняя

У вас есть ссылка на узел в середине списка. В каком списке его можно удалить за O(1)?

  1. AВ двусвязном списке
  2. BВ односвязном списке
  3. CВ динамическом массиве
  4. DВ отсортированном массиве
6.Средняя

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

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

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

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

Что делает косое дерево (splay tree) после каждого обращения?

  1. AПерестраивает всё дерево в сбалансированном виде
  2. BПеремещает узел, к которому обращались, в лист
  3. CПоворотами поднимает узел, к которому обращались, в корень
  4. DПерекрашивает узлы на пути поиска

Ответы

  1. 1. A · Вершин (узлов), соединённых рёбрами
  2. 2. A · Стек
  3. 3. C · Граф, рёбра которого направлены от одной вершины к другой
  4. 4. C · (i + 1) mod n
  5. 5. A · В двусвязном списке
  6. 6. C · Очередь с приоритетом по минимуму
  7. 7. B · Одиночный правый поворот в несбалансированном узле
  8. 8. C · Поворотами поднимает узел, к которому обращались, в корень

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