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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Что хранит отображение (map, словарь)?

  1. AПары одинаковых ключей
  2. BПары ключ–значение с уникальными ключами
  3. CТолько значения в порядке вставки
  4. DЗначения, отсортированные по размеру
3.Лёгкая

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

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

Почему обход массива на практике часто гораздо быстрее обхода связного списка той же длины?

  1. AСвязные списки всегда хранят элементы на диске
  2. BМассивы требуют меньше инструкций для сравнения значений
  3. CЭлементы массива расположены непрерывно, поэтому хорошо используют кэш процессора
  4. DОбход массива занимает в сумме O(1), а связного списка — O(n)
5.Средняя

Что происходит, когда хеш-таблица выполняет рехеширование после превышения порога коэффициента заполнения?

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

Какое условие балансировки поддерживает АВЛ-дерево в каждом узле?

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

Алгоритм Кана для топологической сортировки многократно удаляет вершины с полустепенью захода 0. Какая структура хранит эти вершины?

  1. AМатрица смежности, фиксирующая, какие вершины уже удалены
  2. BОчередь (или любая коллекция) вершин с полустепенью захода 0
  3. CСтек всех посещённых рёбер
  4. DMax-куча, упорядоченная по полустепени исхода
8.Сложная

Какая структура данных обеспечивает кэш LRU (least recently used) с операциями get и put за O(1)?

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

Ответы

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

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