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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Где находится наименьший элемент двоичной min-кучи?

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

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

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

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

  1. AУзел, затем левое поддерево, затем правое поддерево
  2. BЛевое поддерево, затем правое поддерево, затем узел
  3. CЛевое поддерево, затем узел, затем правое поддерево
  4. DПо уровням сверху вниз
4.Средняя

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

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

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

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

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

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

Сколько времени занимает поиск произвольного ключа в двоичной min-куче из n элементов?

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

В кольцевом буфере front == rear может означать и «пуст», и «полон». Какой распространённый способ их различить?

  1. AХранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной
  2. BХранить front и rear в одной переменной
  3. CВсегда очищать буфер, когда front равен rear, так что состояние — пустой
  4. DДелать размер буфера степенью двойки

Ответы

  1. 1. A · В корне
  2. 2. C · Стек
  3. 3. A · Узел, затем левое поддерево, затем правое поддерево
  4. 4. C · Сбалансированное двоичное дерево поиска
  5. 5. B · Стек
  6. 6. C · O(L), независимо от числа хранимых слов
  7. 7. A · O(n)
  8. 8. A · Хранить отдельный счётчик элементов или всегда оставлять одну ячейку свободной

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