(A) 111
(B) 999
(C) 9999
(D) None of the above
Ans:-C
Explanation:-
The formula for calculating the maximum number of nodes in a B-tree of order order n of depth h is
mh+1-1
Here, m=10 and h=3. So the formula becomes
104-1 which is 10000-1=9999 and therefore C is the correct option.
22. A binary tree with 27 nodes has _______ null branches.
(A) 54
(B) 27
(C) 26
(D) None of the above
Ans:-D
Explanation:-
This is quite a straightforward one. A binary tree with n nodes has n+1 null branches. So a binary tree with 27 nodes will have 28 null branches. Since 28 is not available as a option, D is the correct answer.
There is some question based on binary trees or trees in most of the NET paper. The following question is from June 2011 paper and this is also based on trees.
The number of different trees with 8 nodes is
(A) 256
(B) 255
(C) 248
(D) None of these
Ans:-C
Explanation:-
The number of different trees with n nodes can be calculated as 2n-n. Here the value of n=8. So, the formula would become
28-8=256-8=248
So the answer is 248 and so the option is C.
23. The time complexity to build a heap of n elements is
(A) 0(1)
(B) 0(lgn)
(C) 0(n)
(D) 0(nlgn)
Ans:-C
Explanation:-
The WORST CASE COMPLEXITY to build a heap of n elements is the option C.
22.You have explained The number of different trees with n nodes can be calculated as 2^n-n. But in june 2012 qeustion no 36 "Number of binary trees formed with 5 nodes are "
ReplyDeletethere is no option like 27(2^5-5).I have find one more formula for this like ( (1/n+1)*2nCn, acc to this formula the ans 42 was there and that was given in key also
Which one is right ?
I think in that que.they are asking about tree not about binary tree, that's why formula should change
DeleteI have encountered a formula which gives the number of extended binary trees with n nodes is given by the nth catalan number and the formua for the same is (2n!)/(n+1)!n!. If you calculate using this formula the answer is 42 and that is given in the key as well as you said. But i have found the above mentioned formula too for calculating the number of different trees. Probably we need to research further on the same topic as and when we encounter a relevant question and deliberate on it further.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete21. What is the maximum number of nodes in a B-tree of order 10 of depth 3 (root at depth 0) ?
ReplyDeleteNo. nodes in a B-tree of order m and height h, m^h-1/m-1.
=10^3-1/10-1=999/9=111
Instead you explained how to find no. of keys in a B-tree
root is at depth 0 thus the formula would be m^(h+1)-1/m-1 not m^h. Thus the correct answer would be 10^4-1/10-1=9999/9=1111
Deleteq .21 answer is wrong because the no of keys in a b-tree with order -m and depth d is m^(d+1) -1
ReplyDeleteex; the no of keys is 10 ^ 4 -1 =9999 keys (not no of nodes)
the no of different trees with n-nodes is 2^n-n where as the no of different binary trees is 1/(n+1)(2n c n)
ReplyDelete