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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

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

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

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

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

Сколько времени занимает поиск слова длины L в префиксном дереве (trie) с фиксированным алфавитом?

  1. AO(L × n)
  2. BO(log n), где n — число слов
  3. CO(n), где n — число слов
  4. DO(L), независимо от числа хранимых слов
5.Средняя

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

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

Зачем нужен сторожевой (фиктивный, sentinel) узел в связном списке?

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

Нужно хранить k наименьших значений из потока n чисел, используя O(k) памяти. Какой подход работает за время O(n log k)?

  1. AMin-куча, хранящая все n значений, из которой в конце извлекаются k наименьших
  2. BОчередь FIFO последних k значений
  3. CMax-куча размера k, корень которой заменяется, когда приходит меньшее значение
  4. DОтсортированный массив всех n значений
8.Сложная

Почему в хеш-таблице с открытой адресацией удаление часто выполняют с помощью метки «надгробие» (tombstone)?

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

Ответы

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

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