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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что определяет двоичное дерево?

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

Что такое корень дерева?

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

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

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

Какой метод разрешения коллизий хранит конфликтующие ключи в списке в той же корзине?

  1. AЛинейное пробирование
  2. BМетод цепочек (separate chaining)
  3. CКвадратичное пробирование
  4. DДвойное хеширование
5.Средняя

Что верно для матрицы смежности неориентированного графа?

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

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

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

Каково при простом равномерном хешировании ожидаемое время поиска в хеш-таблице с цепочками, n ключами и m корзинами?

  1. AO(n)
  2. BO(m)
  3. CO(1 + α), где α = n / m
  4. DO(log n)
8.Сложная

Какую проблему линейного пробирования в основном уменьшает двойное хеширование?

  1. AНеобходимость в хеш-функции
  2. BНеобходимость хранить ключи в таблице
  3. CСтоимость O(n) чтения значения по ключу
  4. DПервичную кластеризацию, при которой образуются длинные серии занятых ячеек

Ответы

  1. 1. D · У каждого узла не более двух потомков
  2. 2. B · Верхний узел, у которого нет родителя
  3. 3. D · Null (узла нет)
  4. 4. B · Метод цепочек (separate chaining)
  5. 5. B · Она симметрична относительно главной диагонали
  6. 6. C · O(1)
  7. 7. C · O(1 + α), где α = n / m
  8. 8. D · Первичную кластеризацию, при которой образуются длинные серии занятых ячеек

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