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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

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

  1. AБинарное дерево
  2. BКуча
  3. CОчередь
  4. DСтек
2.Лёгкая

Граф состоит из:

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

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

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

Как в кольцевой очереди, хранящейся в массиве ёмкостью n, вычисляется следующая позиция после индекса i?

  1. A2i + 1
  2. Bi + 1
  3. C(i − 1) mod n
  4. D(i + 1) mod n
5.Средняя

АВЛ-деревья (AVL) и красно-чёрные деревья гарантируют:

  1. AХранение ключей в порядке вставки
  2. BВысоту O(log n) благодаря перебалансировке
  3. CЧто ни у одного узла нет двух потомков
  4. DПоиск за константное время в любом случае
6.Средняя

Сколько памяти занимают списки смежности для графа с V вершинами и E рёбрами?

  1. AO(V + E)
  2. BO(V²)
  3. CO(V × E)
  4. DO(E²)
7.Сложная

Чем radix-дерево (сжатое префиксное дерево) лучше обычного trie?

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

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

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

Ответы

  1. 1. C · Очередь
  2. 2. B · Вершин (узлов), соединённых рёбрами
  3. 3. C · Левое поддерево, затем правое поддерево, затем узел
  4. 4. D · (i + 1) mod n
  5. 5. B · Высоту O(log n) благодаря перебалансировке
  6. 6. A · O(V + E)
  7. 7. A · Оно сливает цепочки узлов с одним потомком в одно ребро, помеченное строкой
  8. 8. C · Max-куча размера k, корень которой заменяется, когда приходит меньшее значение

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