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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что хранится для каждой вершины в представлении графа списками смежности?

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

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

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

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

  1. APush
  2. BDequeue
  3. CEnqueue
  4. DInsert
4.Средняя

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

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

Ключи 50, 30, 70, 20, 40 вставляются в таком порядке в пустое двоичное дерево поиска. Кто левый потомок 30?

  1. A50
  2. B20
  3. C70
  4. D40
6.Средняя

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

  1. AO(n), где n — число слов
  2. BO(log n), где n — число слов
  3. CO(L), независимо от числа хранимых слов
  4. DO(L × n)
7.Сложная

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

  1. AНеобходимость в хеш-функции
  2. BПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
  3. CНеобходимость хранить ключи в таблице
  4. DСтоимость O(n) чтения значения по ключу
8.Сложная

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

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

Ответы

  1. 1. A · Список соседних вершин
  2. 2. D · Стек
  3. 3. B · Dequeue
  4. 4. B · Идти от корня по левым потомкам, пока левого потомка не окажется
  5. 5. B · 20
  6. 6. C · O(L), независимо от числа хранимых слов
  7. 7. B · Первичную кластеризацию, при которой образуются длинные серии занятых ячеек
  8. 8. B · Левый поворот в левом потомке, затем правый поворот в узле

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