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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

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

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

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

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

Кольцевой буфер (ring buffer) обычно используют для реализации:

  1. AОчереди фиксированного размера
  2. BОбхода графа
  3. CХеш-функции
  4. DДвоичного дерева поиска
6.Средняя

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

  1. AO(n log n)
  2. BO(1)
  3. CO(n)
  4. DO(log n)
7.Сложная

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

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

Дерево отрезков (segment tree) обычно используют для:

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

Ответы

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

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