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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Хеш-таблица (hash table) хранит данные в виде:

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

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

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

Сколько памяти занимает матрица смежности графа с V вершинами?

  1. AO(V + E)
  2. BO(E)
  3. CO(V²)
  4. DO(log V)
6.Средняя

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

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

Какую гарантию дают правила красно-чёрного дерева относительно высоты дерева с n ключами?

  1. AВысота не превышает n / 2
  2. BВысота равна ровно log2 n
  3. CВысота не превышает log2 n + 1
  4. DВысота не превышает 2 log2(n + 1)
8.Сложная

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

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

Ответы

  1. 1. B · Пар ключ–значение, расположение которых определяет хеш-функция
  2. 2. A · Меньше значения узла
  3. 3. D · Число инцидентных ей рёбер
  4. 4. C · 2h+1 − 1
  5. 5. C · O(V²)
  6. 6. A · Стек
  7. 7. D · Высота не превышает 2 log2(n + 1)
  8. 8. A · Стек, хранящий элементы, ожидающие своего ответа

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