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

Бесплатный лист заданий для печати по теме «Структуры данных»: 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Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  3. CЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
  4. DВсю кучу перестраивают с нуля
5.Средняя

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

  1. AЧтобы хранить число элементов
  2. BЧтобы упростить код, убрав особые случаи в голове или хвосте
  3. CЧтобы список был отсортирован
  4. DЧтобы список не мог вырасти сверх фиксированного максимального числа узлов
6.Средняя

Какая структура данных используется, чтобы проверить, сбалансированы ли скобки в «{[()]}»?

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

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

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

Какому свойству должно удовлетворять красно-чёрное дерево?

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

Ответы

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

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