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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое коллизия в хеш-таблице?

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

Какая структура данных используется для обхода дерева по уровням (level-order)?

  1. AОчередь
  2. BОчередь с приоритетом
  3. CСтек
  4. DХеш-таблица
3.Лёгкая

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

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

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

  1. AO(V²)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(E²)
5.Средняя

Почему двоичную кучу можно хранить в массиве без каких-либо указателей?

  1. AМассивы автоматически хранят ключи в отсортированном порядке, поэтому указатели не нужны
  2. BВсе ключи в куче равны
  3. CВ кучах никогда не бывает больше 100 элементов
  4. DЭто полное двоичное дерево, поэтому позиции подчиняются простым формулам индексов
6.Средняя

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

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

Какое утверждение о пирамидальной сортировке (heapsort) верно?

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

Зачем серверу выбирать хеш-функцию случайно из универсального семейства?

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

Ответы

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

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