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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

Какую структуру обычно используют для реализации очереди с приоритетом?

  1. AСтек
  2. BКучу
  3. CСтроку
  4. DНеупорядоченный односвязный список
4.Средняя

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

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

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

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

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

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

Для чего используется структура union-find в алгоритме Краскала построения минимального остовного дерева?

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

Каковы затраты времени и дополнительной памяти на разворот односвязного списка на месте?

  1. AO(n) времени и O(n) дополнительной памяти
  2. BO(1) времени и O(1) дополнительной памяти
  3. CO(n) времени и O(1) дополнительной памяти
  4. DO(n log n) времени и O(1) дополнительной памяти

Ответы

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

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