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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

В двоичном дереве поиска значения в левом поддереве узла:

  1. AРасположены в случайном порядке
  2. BРавны значению узла
  3. CМеньше значения узла
  4. DБольше значения узла
2.Лёгкая

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

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

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

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

  1. A√n
  2. Bn (дерево превращается в связный список)
  3. Clog₂ n
  4. D1
5.Средняя

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

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

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

  1. AОчередь с приоритетом по минимуму
  2. BМножество без упорядочения
  3. CОчередь FIFO
  4. DСтек
7.Сложная

В чём главное преимущество списка с пропусками (skip list) перед отсортированным связным списком?

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

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

  1. AСортировку массива и двоичный поиск
  2. BВставку элементов в любую позицию
  3. CПоиск медианы за O(1)
  4. DЗапросы префиксных сумм и обновления отдельного элемента

Ответы

  1. 1. C · Меньше значения узла
  2. 2. C · Число хранимых элементов, делённое на число корзин
  3. 3. C · Узел, затем левое поддерево, затем правое поддерево
  4. 4. B · n (дерево превращается в связный список)
  5. 5. D · Списки смежности
  6. 6. A · Очередь с приоритетом по минимуму
  7. 7. D · Ожидаемый поиск за O(log n) благодаря нескольким уровням указателей вперёд
  8. 8. D · Запросы префиксных сумм и обновления отдельного элемента

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