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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Какая структура данных лучше всего подходит для функции «отменить» (undo) в текстовом редакторе?

  1. AСтек
  2. BХеш-множество
  3. CГраф
  4. DОчередь
2.Лёгкая

Как элементы массива хранятся в памяти?

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

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

  1. AЛевое поддерево, затем узел, затем правое поддерево
  2. BЛевое поддерево, затем правое поддерево, затем узел
  3. CПравое поддерево, затем узел, затем левое поддерево
  4. DУзел, затем левое поддерево, затем правое поддерево
4.Средняя

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

  1. AЧто ни у одного узла нет двух потомков
  2. BХранение ключей в порядке вставки
  3. CПоиск за константное время в любом случае
  4. DВысоту O(log n) благодаря перебалансировке
5.Средняя

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

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

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

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

Что делает косое дерево (splay tree) после каждого обращения?

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

  1. AХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  2. BДелать размер буфера степенью двойки
  3. CХранить front и rear в одной переменной
  4. DВсегда очищать буфер, когда front равен rear, так что состояние — пустой

Ответы

  1. 1. A · Стек
  2. 2. D · В одном непрерывном блоке, один за другим
  3. 3. B · Левое поддерево, затем правое поддерево, затем узел
  4. 4. D · Высоту O(log n) благодаря перебалансировке
  5. 5. B · В порядке возрастания (отсортированно)
  6. 6. B · O(V + E)
  7. 7. A · Поворотами поднимает узел, к которому обращались, в корень
  8. 8. A · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной

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