Рубрики

ВОРОТА | GATE-CS-2005 | Вопрос 36

В полном k-арном дереве каждый внутренний узел имеет ровно k дочерних элементов. Число листьев в таком дереве с n внутренними узлами равно
(А) нк
(B) (n — 1) k + 1
(С) n (k — 1) + 1
(D) n (k — 1)

Ответ: (с)
Объяснение:
Необходимый фон — деревья и рекуррентная связь

Мы должны решить эту проблему путем формирования рекуррентного отношения. Пусть T (n) будет числом листьев в дереве, имеющем n внутренних узлов. Мы должны как-то связать T (n) с T (n-1).

Рассмотрим дерево с n = 1. Это дерево будет иметь ровно k листьев.

Попробуйте создать дерево с 2 внутренними узлами из приведенного выше дерева. Мы должны сделать один листовой узел внутренним, и при этом мы получаем больше k листьев. Таким образом, число листовых узлов во вновь построенном дереве будет на один меньше исходного дерева, так как мы изменили один лист на внутренний узел плюс k (недавно преобразованный узел теперь породил еще k листьев).


Thus, T(n)   = T(n-1) - 1 + k = T(n-1) + k -1
             = T(n-2) + 2*(k-1)		 Solving By Substitution Method
	     = T(n-3) + 3*(k-1)
	     .
	     .
	     .
	     = T(n-(n-1)) + (n-1)*(k-1)	 
	     = T(1) + (n-1)*(k-1)
	     = k + (n-1)*(k-1)             Forming Base Case : T(1) = k
             = n(k – 1) + 1

В Gate мы предложим вам решить этот вопрос, взяв 2-3 примера и исключив варианты. Но в интервью позже вам, возможно, придется показать им, как вы формируете и решаете рекуррентные отношения.

Это объяснение было внесено Пранджулом Ахуджей.

Посетите следующую ссылку, чтобы узнать больше о повторяющихся отношениях:

MIT видео лекция по асимптотической записи | Рецидивы | Замена, Мастер Метод

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2005 | Вопрос 36

0.00 (0%) 0 votes