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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какая структура данных используется для обхода дерева по уровням (level-order)?

  1. AОчередь с приоритетом
  2. BОчередь
  3. CХеш-таблица
  4. DСтек
3.Лёгкая

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

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

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

  1. AВ индексе 3
  2. BВ индексе 4
  3. CВ индексе 0
  4. DВ индексе 6
5.Средняя

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

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

  1. AМаксимума нет
  2. B2
  3. C1
  4. D0,5
7.Сложная

Какова стоимость одной операции find в худшем случае в структуре union-find с n элементами без объединения по рангу и сжатия путей?

  1. AO(log n)
  2. BO(1)
  3. CO(α(n))
  4. DO(n)
8.Сложная

Почему из стандартного фильтра Блума нельзя просто удалить элементы, обнулив их биты?

  1. AФильтры Блума хранят элементы целиком, и их невозможно снова найти после хеширования
  2. BУдаление повысило бы долю ложноположительных результатов до 100%
  3. CЭти биты могут принадлежать и другим элементам, что вызвало бы ложноотрицательные результаты
  4. DБиты фильтра Блума нельзя менять после создания

Ответы

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

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