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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Как называется операция очереди, удаляющая элемент из начала?

  1. AEnqueue
  2. BInsert
  3. CPush
  4. DDequeue
2.Лёгкая

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

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

Что такое корень дерева?

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

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

  1. Ah2
  2. B2h + 1
  3. C2h+1 − 1
  4. D2h
5.Средняя

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

  1. Alog₂ n
  2. B√n
  3. Cn (дерево превращается в связный список)
  4. D1
6.Средняя

У узла двоичного дерева поиска есть правое поддерево. Где находится его in-order преемник?

  1. AСамый правый узел его левого поддерева
  2. BВсегда его правый потомок
  3. CВсегда его родитель
  4. DСамый левый узел его правого поддерева
7.Сложная

Каковы затраты времени и дополнительной памяти на разворот односвязного списка на месте?

  1. AO(n) времени и O(n) дополнительной памяти
  2. BO(1) времени и O(1) дополнительной памяти
  3. CO(n log n) времени и O(1) дополнительной памяти
  4. DO(n) времени и O(1) дополнительной памяти
8.Сложная

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

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

Ответы

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

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