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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое корень дерева?

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

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

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

Что хранится для каждой вершины в представлении графа списками смежности?

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

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

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

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

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

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

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

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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

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

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

Ответы

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

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