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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Как элементы массива хранятся в памяти?

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

Что такое свойство max-кучи?

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

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

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

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

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

Как найти минимальный ключ в двоичном дереве поиска?

  1. AОбойти все листья и сравнить их
  2. BИдти от корня по правым потомкам, пока правого потомка не окажется
  3. CИдти от корня по левым потомкам, пока левого потомка не окажется
  4. DПосмотреть только на корень
6.Средняя

Очередь реализована двумя стеками: push в стек «in», pop из стека «out», который при опустошении заполняется из «in». Какова амортизированная стоимость одной операции?

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

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

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

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

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

Ответы

  1. 1. A · В одном непрерывном блоке, один за другим
  2. 2. B · Ключ каждого родителя больше или равен ключам его потомков
  3. 3. B · Пары ключ–значение с уникальными ключами
  4. 4. C · O(1)
  5. 5. C · Идти от корня по левым потомкам, пока левого потомка не окажется
  6. 6. C · O(1)
  7. 7. D · Поиск объекта может не удаться, потому что он лежит в корзине своего старого хеша
  8. 8. B · Max-куча размера k, корень которой заменяется, когда приходит меньшее значение

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