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

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

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

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

Имя: ____________________   Дата: ____________

1.Лёгкая

Высота дерева обычно определяется как:

  1. AОбщее число узлов в дереве, считая корень и каждый лист
  2. BЧисло листьев в дереве
  3. CЧисло потомков корня
  4. DЧисло рёбер на самом длинном пути от корня до листа
2.Лёгкая

Что такое коэффициент заполнения (load factor) хеш-таблицы?

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

Как называется операция стека, добавляющая элемент на вершину?

  1. APush
  2. BPeek
  3. CEnqueue
  4. DPop
4.Средняя

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

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

Где в двоичной куче, хранящейся в массиве с индексацией от 0, находится родитель узла с индексом i?

  1. AВ индексе ⌊i / 2⌋ + 1
  2. BВ индексе i − 1
  3. CВ индексе ⌊(i − 1) / 2⌋
  4. DВ индексе 2i + 1
6.Средняя

Каков максимально возможный коэффициент заполнения хеш-таблицы с открытой адресацией?

  1. AМаксимума нет
  2. B2
  3. C0,5
  4. D1
7.Сложная

Какому свойству должно удовлетворять красно-чёрное дерево?

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

Какое свойство поддерживает любое B-дерево идеально сбалансированным?

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

Ответы

  1. 1. D · Число рёбер на самом длинном пути от корня до листа
  2. 2. C · Число хранимых элементов, делённое на число корзин
  3. 3. A · Push
  4. 4. B · O(V + E)
  5. 5. C · В индексе ⌊(i − 1) / 2⌋
  6. 6. D · 1
  7. 7. A · Каждый путь от узла до его листьев-потомков содержит одинаковое число чёрных узлов
  8. 8. D · Все листья находятся на одной глубине

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