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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что делает хеш-функция в хеш-таблице?

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

Как называется операция очереди, удаляющая элемент из начала?

  1. ADequeue
  2. BEnqueue
  3. CInsert
  4. DPush
4.Средняя

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

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

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

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

  1. AВ индексе i − 1
  2. BВ индексе ⌊(i − 1) / 2⌋
  3. CВ индексе ⌊i / 2⌋ + 1
  4. DВ индексе 2i + 1
7.Сложная

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

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

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

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

Ответы

  1. 1. B · Стек
  2. 2. D · Отображает ключ в индекс таблицы
  3. 3. A · Dequeue
  4. 4. B · Стек вызовов
  5. 5. C · Идти от корня по левым потомкам, пока левого потомка не окажется
  6. 6. B · В индексе ⌊(i − 1) / 2⌋
  7. 7. A · Поворотами поднимает узел, к которому обращались, в корень
  8. 8. A · Эти биты могут принадлежать и другим элементам, что вызвало бы ложноотрицательные результаты

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