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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

Какую структуру обычно используют для реализации очереди с приоритетом?

  1. AНеупорядоченный односвязный список
  2. BСтроку
  3. CСтек
  4. DКучу
3.Лёгкая

В односвязном списке каждый узел содержит:

  1. AДанные и ссылку на следующий узел
  2. BТолько данные
  3. CДанные и индекс
  4. DДанные и ссылки на все остальные узлы
4.Средняя

В двоичной min-куче, хранящейся в массиве (индексация с 0), потомки узла с индексом i находятся на позициях:

  1. Ai + 1 и i + 2
  2. Bi/2 и i/2 + 1
  3. C2i + 1 и 2i + 2
  4. D2i и 2i + 1
5.Средняя

Какую структуру данных использует поиск в глубину (DFS, итеративная версия)?

  1. AОчередь
  2. BТолько хеш-таблицу
  3. CКучу
  4. DСтек
6.Средняя

Какова высота двоичного дерева поиска с n узлами в худшем случае, если ключи вставляются в отсортированном порядке?

  1. A√n
  2. B1
  3. Cn (дерево превращается в связный список)
  4. Dlog₂ n
7.Сложная

Фильтр Блума может ответить на вопрос «принадлежит ли этот элемент множеству?»:

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

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

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

Ответы

  1. 1. C · Число хранимых элементов, делённое на число корзин
  2. 2. D · Кучу
  3. 3. A · Данные и ссылку на следующий узел
  4. 4. C · 2i + 1 и 2i + 2
  5. 5. D · Стек
  6. 6. C · n (дерево превращается в связный список)
  7. 7. C · С возможными ложноположительными, но без ложноотрицательных результатов
  8. 8. B · Хеш-таблица в сочетании с двусвязным списком

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