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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. AЛевое поддерево, затем узел, затем правое поддерево
  2. BУзел, затем левое поддерево, затем правое поддерево
  3. CПо уровням сверху вниз
  4. DЛевое поддерево, затем правое поддерево, затем узел
2.Лёгкая

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

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

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

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

Префиксное дерево (trie) особенно эффективно для:

  1. AХранения матриц
  2. BПоиска кратчайших путей
  3. CСортировки чисел
  4. DПоиска по префиксу, например автодополнения
5.Средняя

Сколько времени занимает проверка существования ребра (u, v) с помощью матрицы смежности?

  1. AO(V)
  2. BO(log V)
  3. CO(E)
  4. DO(1)
6.Средняя

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

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

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

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

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

  1. AОно хранит каждое слово в хеш-таблице в корне вместо отдельных узлов
  2. BОно сливает цепочки узлов с одним потомком в одно ребро, помеченное строкой
  3. CОно хранит только первую букву каждого слова
  4. DОно сортирует потомков каждого узла по частоте

Ответы

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

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