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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что содержит указатель next последнего узла односвязного списка?

  1. AАдрес первого узла
  2. BЧисло узлов в списке
  3. CNull (узла нет)
  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Каждый узел окрашен в красный или чёрный цвет
  4. DВысоты левого и правого поддеревьев различаются не более чем на 1
5.Средняя

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

  1. AO(1)
  2. BO(E)
  3. CO(log V)
  4. DO(V)
6.Средняя

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

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

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

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

Динамический массив удваивается при заполнении. Почему многие реализации уменьшают его, только когда он заполнен на четверть, а не наполовину?

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

Ответы

  1. 1. C · Null (узла нет)
  2. 2. A · Узел без потомков
  3. 3. A · Число рёбер на самом длинном пути от корня до листа
  4. 4. D · Высоты левого и правого поддеревьев различаются не более чем на 1
  5. 5. A · O(1)
  6. 6. D · Элементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
  7. 7. C · С возможными ложноположительными, но без ложноотрицательных результатов
  8. 8. D · Чтобы избежать повторных изменений размера, когда push и pop чередуются вблизи границы

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