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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

  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Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  4. DВсю кучу перестраивают с нуля
5.Средняя

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

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

Что верно для матрицы смежности неориентированного графа?

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

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

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

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

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

Ответы

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

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