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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что делает хеш-функция в хеш-таблице?

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

В чём главное отличие статического массива от динамического?

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

Какая операция выполняется за O(1) для массива, но за O(n) для односвязного списка?

  1. AВставка в начало
  2. BУдаление головного элемента
  3. CЧтение первого элемента
  4. DДоступ к элементу с индексом i
4.Средняя

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

  1. AОдин отсортированный массив вершин
  2. BДвоичная куча рёбер
  3. CСписки смежности
  4. DМатрица смежности
5.Средняя

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

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

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

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

Почему из стандартного фильтра Блума нельзя просто удалить элементы, обнулив их биты?

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

Объект хранится как ключ в хеш-отображении, а затем меняется поле, используемое его хеш-функцией. Каков вероятный результат?

  1. AОтображение выбрасывает ошибку в момент изменения поля
  2. BНичего не меняется, потому что хеш ключа вычисляется только один раз при запуске программы
  3. CПоиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
  4. DОтображение автоматически переносит ключ в новую корзину

Ответы

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

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