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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

Что содержит каждый узел двусвязного списка?

  1. AДанные и только указатель на следующий узел
  2. BДве копии данных и один указатель
  3. CДанные и два указателя: один на следующий узел и один на узел после него
  4. DДанные, указатель на следующий узел и указатель на предыдущий узел
4.Средняя

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

  1. AОчередь
  2. BТолько хеш-таблицу
  3. CСтек
  4. DКучу
5.Средняя

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

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

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

  1. AХеш-таблица
  2. BСбалансированное двоичное дерево поиска
  3. CСтек
  4. DНеотсортированный связный список
7.Сложная

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

  1. AТолько для чисел
  2. BС возможными ложноотрицательными, но без ложноположительных результатов
  3. CС возможными ложноположительными, но без ложноотрицательных результатов
  4. DВсегда точно
8.Сложная

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

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

Ответы

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

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