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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что хранится для каждой вершины в представлении графа списками смежности?

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

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

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

У двоичного дерева корень 1 с левым потомком 2 и правым потомком 3; у узла 2 потомки 4 (левый) и 5 (правый). Каков обратный обход (postorder)?

  1. A5 4 3 2 1
  2. B4 2 5 1 3
  3. C4 5 2 3 1
  4. D1 2 4 5 3
5.Средняя

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

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

Как вставляется новый элемент в двоичную кучу?

  1. AЕго вставляют в отсортированную позицию, сдвигая все бо́льшие элементы на одно место вправо
  2. BЕго помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  3. CЕго помещают в корень и опускают вниз
  4. DВсю кучу перестраивают с нуля
7.Сложная

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

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

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

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

Ответы

  1. 1. A · Два разных ключа отображаются в один и тот же индекс
  2. 2. C · Список соседних вершин
  3. 3. A · Меньше значения узла
  4. 4. C · 4 5 2 3 1
  5. 5. B · O(1)
  6. 6. B · Его помещают в конец массива и поднимают вверх (sift up), пока он нарушает свойство кучи
  7. 7. B · Чтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем
  8. 8. D · Очередь (или любая коллекция) вершин с полустепенью захода 0

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