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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Что содержит указатель next последнего узла односвязного списка?

  1. AАдрес первого узла
  2. BЧисло узлов в списке
  3. CАдрес предыдущего узла
  4. DNull (узла нет)
2.Лёгкая

Что определяет двоичное дерево?

  1. AВ дереве ровно два уровня
  2. BУ каждого узла ровно два потомка
  3. CУ каждого узла не более двух потомков
  4. DКаждый узел хранит двоичное число
3.Лёгкая

Что делает операция peek (или top) стека?

  1. AВозвращает нижний элемент стека
  2. BУдаляет верхний элемент и возвращает его
  3. CВозвращает верхний элемент, не удаляя его
  4. DУдаляет все элементы из стека
4.Средняя

Симметричный обход (in-order) двоичного дерева поиска посещает ключи:

  1. AВ порядке возрастания (отсортированно)
  2. BПо уровням
  3. CВ порядке вставки
  4. DВсегда в порядке убывания
5.Средняя

В дорожной сети 100 000 перекрёстков, каждый соединён примерно с 4 другими. Какое представление подходит лучше всего?

  1. AМатрица смежности
  2. BДвоичная куча рёбер
  3. CОдин отсортированный массив вершин
  4. DСписки смежности
6.Средняя

Какова стоимость вставки элемента в середину массива из n элементов?

  1. AO(log n) из-за двоичного поиска
  2. BO(n), потому что последующие элементы нужно сдвинуть
  3. CO(1), потому что индекс известен
  4. DO(n²), потому что каждый элемент сдвигается n раз
7.Сложная

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

  1. AОдин только прямой
  2. BПрямой и обратный (preorder и postorder)
  3. CПрямой и симметричный (preorder и inorder)
  4. DОдин только обход по уровням
8.Сложная

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

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

Ответы

  1. 1. D · Null (узла нет)
  2. 2. C · У каждого узла не более двух потомков
  3. 3. C · Возвращает верхний элемент, не удаляя его
  4. 4. A · В порядке возрастания (отсортированно)
  5. 5. D · Списки смежности
  6. 6. B · O(n), потому что последующие элементы нужно сдвинуть
  7. 7. C · Прямой и симметричный (preorder и inorder)
  8. 8. B · Высота не превышает 2 log2(n + 1)

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