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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

В односвязном списке каждый узел содержит:

  1. AДанные и ссылку на следующий узел
  2. BТолько данные
  3. CДанные и индекс
  4. DДанные и ссылки на все остальные узлы
2.Лёгкая

Что содержит указатель next последнего узла односвязного списка?

  1. AЧисло узлов в списке
  2. BАдрес первого узла
  3. CNull (узла нет)
  4. DАдрес предыдущего узла
3.Лёгкая

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

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

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

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

  1. AДвойное хеширование
  2. BМетод цепочек (separate chaining)
  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. A70
  2. B80
  3. C40
  4. D60
8.Сложная

Сколько времени занимает поиск произвольного ключа в двоичной min-куче из n элементов?

  1. AO(log n)
  2. BO(log log n)
  3. CO(1)
  4. DO(n)

Ответы

  1. 1. A · Данные и ссылку на следующий узел
  2. 2. C · Null (узла нет)
  3. 3. C · Стек
  4. 4. D · Выделяется таблица большего размера, и каждый ключ вставляется заново
  5. 5. B · Метод цепочек (separate chaining)
  6. 6. B · Стек
  7. 7. D · 60
  8. 8. D · O(n)

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