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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

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

Какая структура данных используется для обхода дерева по уровням (level-order)?

  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.Средняя

Сколько узлов в идеальном (perfect) двоичном дереве высоты h, если высота считается в рёбрах?

  1. A2h + 1
  2. B2h
  3. C2h+1 − 1
  4. Dh2
6.Средняя

Чему равно значение постфиксного выражения 3 4 + 2 * ?

  1. A10
  2. B24
  3. C11
  4. D14
7.Сложная

Для каждого элемента массива нужно найти следующий больший элемент справа за общее время O(n). Какая структура поможет?

  1. AОчередь, хранящая каждую пару элементов
  2. BДвоичное дерево поиска, перестраиваемое для каждого элемента
  3. CХеш-таблица всех элементов
  4. DСтек, хранящий элементы, ожидающие своего ответа
8.Сложная

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

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

Ответы

  1. 1. D · Оно хранит элементы без повторений
  2. 2. B · Очередь
  3. 3. A · Граф, рёбра которого направлены от одной вершины к другой
  4. 4. C · Идти от корня по левым потомкам, пока левого потомка не окажется
  5. 5. C · 2h+1 − 1
  6. 6. D · 14
  7. 7. D · Стек, хранящий элементы, ожидающие своего ответа
  8. 8. B · Первичную кластеризацию, при которой образуются длинные серии занятых ячеек

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