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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Сколько рёбер в дереве с n узлами?

  1. An
  2. Bn − 1
  3. C2n
  4. Dn + 1
2.Лёгкая

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

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

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

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

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

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

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

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

Префиксное дерево (trie) особенно эффективно для:

  1. AСортировки чисел
  2. BХранения матриц
  3. CПоиска по префиксу, например автодополнения
  4. DПоиска кратчайших путей
7.Сложная

Какая структура позволяет вычислить максимум каждого окна размера k в массиве за общее время O(n)?

  1. AОдносвязный список элементов окна
  2. BОтсортированный массив, обновляемый сдвигами
  3. CДек, хранящий индексы в порядке убывания значений
  4. DMin-куча, перестраиваемая для каждого окна
8.Сложная

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

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

Ответы

  1. 1. B · n − 1
  2. 2. A · Граф, рёбра которого направлены от одной вершины к другой
  3. 3. D · Очередь
  4. 4. C · Метод цепочек (separate chaining)
  5. 5. D · O(V + E)
  6. 6. C · Поиска по префиксу, например автодополнения
  7. 7. C · Дек, хранящий индексы в порядке убывания значений
  8. 8. D · Чтобы сделать крайне маловероятным, что атакующий подберёт много ключей с одинаковым хешем

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