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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

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

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

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

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

Сколько памяти занимает матрица смежности графа с V вершинами?

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

Кольцевой буфер (ring buffer) обычно используют для реализации:

  1. AДвоичного дерева поиска
  2. BХеш-функции
  3. CОбхода графа
  4. DОчереди фиксированного размера
6.Средняя

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

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

В BST с корнем 50, левым поддеревом 30 (потомки 20, 40) и правым поддеревом 70 (потомки 60, 80) корень удаляют с помощью in-order преемника. Какой ключ станет новым корнем?

  1. A60
  2. B40
  3. C70
  4. D80
8.Сложная

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

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

Ответы

  1. 1. C · Число хранимых элементов, делённое на число корзин
  2. 2. D · Два разных ключа отображаются в один и тот же индекс
  3. 3. A · Очередь
  4. 4. A · O(V²)
  5. 5. D · Очереди фиксированного размера
  6. 6. D · В порядке возрастания (отсортированно)
  7. 7. A · 60
  8. 8. A · С возможными ложноположительными, но без ложноотрицательных результатов

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