Рубрики

Структуры данных и алгоритмы | Набор 23

На экзамене GATE CS 2005 были заданы следующие вопросы.

1. Что из следующего является ключевым фактором для предпочтения B-деревьев бинарным деревьям поиска для индексации отношений базы данных?
(а) Базы данных имеют большое количество записей
(б) Базы данных отсортированы по первичному ключу
(c) B-деревья требуют меньше памяти, чем бинарные деревья поиска
(d) Диски для передачи данных находятся в блоках.

Ответ (г)
Дисковый блок содержит достаточно большое количество ключей. В отличие от BST, где каждый узел содержит только один ключ, B-Tree предназначен для большого количества ключей, поэтому высота дерева мала.

2. Сколько разных двоичных деревьев поиска можно создать из 4 разных ключей?
(а) 5
(б) 14
(с) 24
(г) 42

Ответ (б)

Вот систематический способ перечислить эти BST. Рассмотрим все возможные бинарные деревья поиска с каждым элементом в корне. Если имеется n узлов, то для каждого выбора корневого узла существует n — 1 некорневых узлов, и эти некорневые узлы должны быть разделены на те, которые меньше выбранного корня, и те, которые больше выбранного корня ,

Допустим, узел i выбран в качестве корня. Тогда есть i — 1 узлов меньше, чем i и n — i узлов больше, чем i. Для каждого из этих двух наборов узлов существует определенное количество возможных поддеревьев.

Пусть t (n) будет общим количеством BST с n узлами. Общее количество BST с i в корне равно t (i — 1) t (n — i). Два слагаемых умножаются вместе, потому что расположения в левом и правом поддеревьях независимы. То есть для каждого расположения в левом дереве и для каждого расположения в правом дереве вы получаете один BST с i в корне.

Суммирование по i дает общее количество бинарных деревьев поиска с n узлами.

Базовый случай: t (0) = 1 и t (1) = 1, то есть есть один пустой BST и один BST с одним узлом.



3. В полном k-арном дереве каждый внутренний узел имеет ровно k дочерних элементов. Количество листьев в таком дереве с n внутренними узлами составляет:
(а) нк
(б) (n — 1) k + 1
(c) n (k — 1) + 1
(d) n (k — 1)

Ответ (с)

4) Предположим, что T (n) = 2T (n / 2) + n, T (0) = T (1) = 1
Какой из следующих является ложным.

а) T (n) = O (n ^ 2)
б) T (n) = Θ (nLogn)
в) T (n) = Ω (n 2 )
d) T (n) = O (nLogn)

Ответ (с)
Данное рекуррентное соотношение может быть решено с помощью основной теоремы . Оно лежит в случае 2 основной теоремы. Или, если вы помните рекуррентное отношение сортировки слиянием или быстрой сортировки в лучшем случае, вы можете угадать значение T (n).

T (n) = Θ (nLogn)

По определению обозначения Big O мы можем сказать.
Θ (nLogn) = O (nLogn) = O (n ^ 2)

Θ (nLogn) может быть равно Ω (n) или Ω (nLogn), но не Ω (n ^ 2)

Пожалуйста, смотрите GATE Corner для всех документов / решений / объяснений предыдущего года, учебных планов, важных дат, заметок и т. Д.

Пожалуйста, пишите комментарии, если вы найдете какие-либо неправильные ответы / объяснения, или вы хотите поделиться дополнительной информацией по темам, обсужденным выше.

Рекомендуемые посты:

Структуры данных и алгоритмы | Набор 23

0.00 (0%) 0 votes