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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

  1. AEnqueue
  2. BPop
  3. CPeek
  4. DPush
3.Лёгкая

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

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

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

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

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

  1. AМатрица смежности
  2. BСписки смежности
  3. CОдин отсортированный массив вершин
  4. DДвоичная куча рёбер
6.Средняя

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

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

  1. AМатрица смежности, фиксирующая, какие вершины уже удалены
  2. BОчередь (или любая коллекция) вершин с полустепенью захода 0
  3. CMax-куча, упорядоченная по полустепени исхода
  4. DСтек всех посещённых рёбер
8.Сложная

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

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

Ответы

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

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