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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

В каком порядке обратный обход (postorder) двоичного дерева посещает узлы?

  1. AЛевое поддерево, затем правое поддерево, затем узел
  2. BЛевое поддерево, затем узел, затем правое поддерево
  3. CУзел, затем левое поддерево, затем правое поддерево
  4. DПравое поддерево, затем узел, затем левое поддерево
2.Лёгкая

Что такое дек (deque, двусторонняя очередь)?

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

Какова определяющая особенность множества как абстрактного типа данных?

  1. AОно хранит пары ключ–значение
  2. BОно хранит элементы в отсортированном порядке
  3. CОно допускает доступ только с одного конца
  4. DОно хранит элементы без повторений
4.Средняя

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

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

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

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

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

  1. A0,5
  2. B1
  3. C2
  4. DМаксимума нет
7.Сложная

Какие операции поддерживает за O(log n) дерево Фенвика (binary indexed tree) над массивом из n чисел?

  1. AВставку элементов в любую позицию
  2. BПоиск медианы за O(1)
  3. CЗапросы префиксных сумм и обновления отдельного элемента
  4. DСортировку массива и двоичный поиск
8.Сложная

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

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

Ответы

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

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