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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что такое взвешенный граф?

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

Что такое степень вершины в неориентированном графе?

  1. AЧисло вершин графа
  2. BЧисло инцидентных ей рёбер
  3. CДлина самого длинного пути из неё
  4. DЕё позиция в списке смежности
4.Средняя

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

  1. A1
  2. Bn (дерево превращается в связный список)
  3. Clog₂ n
  4. D√n
5.Средняя

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

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

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

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

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

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

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

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

Ответы

  1. 1. B · Пар ключ–значение, расположение которых определяет хеш-функция
  2. 2. D · Граф, в котором у каждого ребра есть числовое значение, например стоимость или расстояние
  3. 3. B · Число инцидентных ей рёбер
  4. 4. B · n (дерево превращается в связный список)
  5. 5. B · Самый левый узел его правого поддерева
  6. 6. D · Элементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
  7. 7. B · O(n)
  8. 8. B · O(n) времени и O(1) дополнительной памяти

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