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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Глубина узла в дереве — это:

  1. AЧисло рёбер от корня до этого узла
  2. BЧисло потомков этого узла
  3. CЧисло узлов в его поддереве
  4. DЧисло рёбер от этого узла до самого глубокого листа
3.Лёгкая

Что хранит отображение (map, словарь)?

  1. AПары одинаковых ключей
  2. BТолько значения в порядке вставки
  3. CПары ключ–значение с уникальными ключами
  4. DЗначения, отсортированные по размеру
4.Средняя

Префиксное дерево (trie) особенно эффективно для:

  1. AПоиска по префиксу, например автодополнения
  2. BПоиска кратчайших путей
  3. CХранения матриц
  4. DСортировки чисел
5.Средняя

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

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

Как найти минимальный ключ в двоичном дереве поиска?

  1. AИдти от корня по правым потомкам, пока правого потомка не окажется
  2. BОбойти все листья и сравнить их
  3. CИдти от корня по левым потомкам, пока левого потомка не окажется
  4. DПосмотреть только на корень
7.Сложная

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

  1. A80
  2. B70
  3. C40
  4. D60
8.Сложная

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

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

Ответы

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

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