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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое корень дерева?

  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.Средняя

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

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

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

  1. An (дерево превращается в связный список)
  2. Blog₂ n
  3. C1
  4. D√n
6.Средняя

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

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

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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

Ответы

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

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