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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

  1. AEnqueue
  2. BPeek
  3. CPop
  4. DPush
3.Лёгкая

Что делает операция peek (или top) стека?

  1. AУдаляет все элементы из стека
  2. BВозвращает верхний элемент, не удаляя его
  3. CВозвращает нижний элемент стека
  4. DУдаляет верхний элемент и возвращает его
4.Средняя

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

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

Что верно для матрицы смежности неориентированного графа?

  1. AНа её главной диагонали всегда стоят единицы
  2. BОна симметрична относительно главной диагонали
  3. CВ каждой строке ровно одна 1
  4. DОна всегда верхнетреугольная
6.Средняя

Какую структуру данных использует выполняющаяся программа для отслеживания активных вызовов функций и их локальных переменных?

  1. AОчередь памяти кучи
  2. BСтек вызовов
  3. CХеш-таблицу функций
  4. DДвоичное дерево поиска кадров
7.Сложная

Удаление узла с двумя потомками из двоичного дерева поиска обычно выполняют так:

  1. AМеняют его местами с корнем
  2. BЗаменяют его in-order преемником (или предшественником) и удаляют тот узел
  3. CУдаляют всё поддерево
  4. DПерестраивают поддерево под ним с нуля и заново вставляют каждый содержавшийся в нём ключ
8.Сложная

Какое утверждение о пирамидальной сортировке (heapsort) верно?

  1. AОна устойчива и требует O(n) дополнительной памяти
  2. BОна сортирует на месте за O(n log n) в худшем случае, но не является устойчивой
  3. CЕй нужно двоичное дерево поиска как дополнительное хранилище, поэтому она использует O(n) дополнительной памяти
  4. DОна работает за O(n) на любых входных данных

Ответы

  1. 1. C · Очередь
  2. 2. D · Push
  3. 3. B · Возвращает верхний элемент, не удаляя его
  4. 4. B · O(L), независимо от числа хранимых слов
  5. 5. B · Она симметрична относительно главной диагонали
  6. 6. B · Стек вызовов
  7. 7. B · Заменяют его in-order преемником (или предшественником) и удаляют тот узел
  8. 8. B · Она сортирует на месте за O(n log n) в худшем случае, но не является устойчивой

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