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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

Что такое дек (deque, двусторонняя очередь)?

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

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

  1. A40
  2. B20
  3. C50
  4. D70
6.Средняя

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

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

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

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

Ответы

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

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