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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое взвешенный граф?

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

Где находится наименьший элемент двоичной min-кучи?

  1. AВ последней позиции массива
  2. BВ каком-то листе, который придётся искать
  3. CВ самом левом листе
  4. DВ корне
3.Лёгкая

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

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

  1. A2i + 1
  2. B(i + 1) mod n
  3. Ci + 1
  4. D(i − 1) mod n
5.Средняя

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(1), потому что индекс известен
  2. BO(n), потому что последующие элементы нужно сдвинуть
  3. CO(log n) из-за двоичного поиска
  4. DO(n²), потому что каждый элемент сдвигается n раз
6.Средняя

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

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

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

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

Ответы

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

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