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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что хранит отображение (map, словарь)?

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

Что такое узлы-братья (siblings) в дереве?

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

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

  1. AМетод цепочек (separate chaining)
  2. BЛинейное пробирование
  3. CДвойное хеширование
  4. DКвадратичное пробирование
5.Средняя

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

  1. A40
  2. B70
  3. C50
  4. D20
6.Средняя

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

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

Временная сложность операции decrease-key в двоичной куче (при известной позиции элемента) составляет:

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

Вставка ключа в АВЛ-дерево делает левое поддерево узла слишком высоким, причём новый ключ попал в левое поддерево его левого потомка (случай левый–левый). Какое исправление применяется?

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

Ответы

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

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