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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая структура данных используется для обхода дерева по уровням (level-order)?

  1. AСтек
  2. BХеш-таблица
  3. CОчередь
  4. DОчередь с приоритетом
2.Лёгкая

В каком порядке прямой обход (preorder) двоичного дерева посещает узлы?

  1. AЛевое поддерево, затем узел, затем правое поддерево
  2. BУзел, затем левое поддерево, затем правое поддерево
  3. CЛевое поддерево, затем правое поддерево, затем узел
  4. DПо уровням сверху вниз
3.Лёгкая

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

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

Хеш-таблица размера 7 использует h(k) = k mod 7 и линейное пробирование. Где окажется 17 после вставки 10?

  1. AВ индексе 0
  2. BВ индексе 4
  3. CВ индексе 3
  4. DВ индексе 6
5.Средняя

Какова временная сложность поиска ключа в сбалансированном двоичном дереве поиска?

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

Сколько памяти занимает матрица смежности графа с V вершинами?

  1. AO(log V)
  2. BO(V + E)
  3. CO(V²)
  4. DO(E)
7.Сложная

Почему B-деревья используются в базах данных и файловых системах?

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

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

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

Ответы

  1. 1. C · Очередь
  2. 2. B · Узел, затем левое поддерево, затем правое поддерево
  3. 3. B · Граф, в котором у каждого ребра есть числовое значение, например стоимость или расстояние
  4. 4. B · В индексе 4
  5. 5. C · O(log n)
  6. 6. C · O(V²)
  7. 7. A · Высокая степень ветвления делает дерево неглубоким и сокращает число медленных чтений с диска
  8. 8. D · Каждый путь от узла до его листьев-потомков содержит одинаковое число чёрных узлов

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