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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какая структура данных работает по принципу «последним пришёл — первым ушёл» (LIFO)?

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

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

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

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

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

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

  1. A1
  2. Blog₂ n
  3. Cn (дерево превращается в связный список)
  4. D√n
6.Средняя

Префиксное дерево (trie) особенно эффективно для:

  1. AСортировки чисел
  2. BПоиска кратчайших путей
  3. CПоиска по префиксу, например автодополнения
  4. DХранения матриц
7.Сложная

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

  1. AНеобходимость хранить ключи в таблице
  2. BПервичную кластеризацию, при которой образуются длинные серии занятых ячеек
  3. CСтоимость O(n) чтения значения по ключу
  4. DНеобходимость в хеш-функции
8.Сложная

Какому правилу должны подчиняться хеш и равенство, чтобы хеш-таблица работала правильно?

  1. AРавные ключи должны иметь равные значения хеша
  2. BРазные ключи должны иметь разные значения хеша
  3. CИз равенства хешей следует равенство ключей
  4. DЗначения хеша должны быть простыми числами

Ответы

  1. 1. C · Граф, в котором у каждого ребра есть числовое значение, например стоимость или расстояние
  2. 2. A · Стек
  3. 3. B · В одном непрерывном блоке, один за другим
  4. 4. A · Стек вызовов
  5. 5. C · n (дерево превращается в связный список)
  6. 6. C · Поиска по префиксу, например автодополнения
  7. 7. B · Первичную кластеризацию, при которой образуются длинные серии занятых ячеек
  8. 8. A · Равные ключи должны иметь равные значения хеша

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