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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое узлы-братья (siblings) в дереве?

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

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

  1. AКуча
  2. BОчередь
  3. CСтек
  4. DБинарное дерево
3.Лёгкая

Что такое дек (deque, двусторонняя очередь)?

  1. AДве отдельные очереди в одном массиве
  2. BОчередь, отсортированная по приоритету
  3. CСтруктура, допускающая вставку и удаление с обоих концов
  4. DОчередь, допускающая удаление только с конца
4.Средняя

Как найти минимальный ключ в двоичном дереве поиска?

  1. AОбойти все листья и сравнить их
  2. BИдти от корня по правым потомкам, пока правого потомка не окажется
  3. CИдти от корня по левым потомкам, пока левого потомка не окажется
  4. DПосмотреть только на корень
5.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

  1. AВ порядке возрастания (отсортированно)
  2. BВ порядке вставки
  3. CВсегда в порядке убывания
  4. DПо уровням
6.Средняя

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

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

Узел АВЛ-дерева разбалансирован, потому что правое поддерево его левого потомка стало слишком высоким (случай левый–правый). Какое исправление применяется?

  1. AПравый поворот в левом потомке, затем левый поворот в узле
  2. BЛевый поворот в левом потомке, затем правый поворот в узле
  3. CОдиночный левый поворот в узле
  4. DОдиночный правый поворот в узле
8.Сложная

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

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

Ответы

  1. 1. B · Узлы с общим родителем
  2. 2. B · Очередь
  3. 3. C · Структура, допускающая вставку и удаление с обоих концов
  4. 4. C · Идти от корня по левым потомкам, пока левого потомка не окажется
  5. 5. A · В порядке возрастания (отсортированно)
  6. 6. C · O(V²)
  7. 7. B · Левый поворот в левом потомке, затем правый поворот в узле
  8. 8. D · Max-куча размера k, корень которой заменяется, когда приходит меньшее значение

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