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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что делает операция peek (или top) стека?

  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.Средняя

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

  1. AСтек
  2. BОчередь с приоритетом по минимуму
  3. CОчередь FIFO
  4. DМножество без упорядочения
5.Средняя

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

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

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

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

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

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

Какому свойству должно удовлетворять красно-чёрное дерево?

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

Ответы

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

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