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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

  1. AАдрес первого узла
  2. BNull (узла нет)
  3. CЧисло узлов в списке
  4. DАдрес предыдущего узла
3.Лёгкая

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

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

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

  1. A1
  2. B√n
  3. Cn (дерево превращается в связный список)
  4. Dlog₂ n
5.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

  1. AВ порядке вставки
  2. BПо уровням
  3. CВ порядке возрастания (отсортированно)
  4. DВсегда в порядке убывания
6.Средняя

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

  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. B · Граф, в котором у каждого ребра есть числовое значение, например стоимость или расстояние
  2. 2. B · Null (узла нет)
  3. 3. B · Два разных ключа отображаются в один и тот же индекс
  4. 4. C · n (дерево превращается в связный список)
  5. 5. C · В порядке возрастания (отсортированно)
  6. 6. B · Списки смежности
  7. 7. A · Одиночный правый поворот в несбалансированном узле
  8. 8. B · Чтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем

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