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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Хеш-таблица (hash table) хранит данные в виде:

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

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

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

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

  1. AO(V × E)
  2. BO(V²)
  3. CO(E²)
  4. DO(V + E)
5.Средняя

Как работает extract-min в двоичной min-куче?

  1. AПоследний элемент перемещают в корень и опускают вниз (sift down)
  2. BУдаляют корень и сдвигают все элементы на одну позицию влево
  3. CИщут новый минимум среди всех листьев
  4. DУдаляют последний элемент массива
6.Средняя

Приложению нужен быстрый поиск, а также вывод ключей в отсортированном порядке и запросы по диапазону. Какая структура подходит лучше всего?

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

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

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

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

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

Ответы

  1. 1. C · Узлы с общим родителем
  2. 2. D · Пар ключ–значение, расположение которых определяет хеш-функция
  3. 3. D · Отображает ключ в индекс таблицы
  4. 4. D · O(V + E)
  5. 5. A · Последний элемент перемещают в корень и опускают вниз (sift down)
  6. 6. A · Сбалансированное двоичное дерево поиска
  7. 7. A · O(n)
  8. 8. A · O(n) времени и O(1) дополнительной памяти

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