Tree

Question 1
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a  
A
Hamiltonian cycle
B
grid
C
hypercube
D
tree
       Data-Structures       Tree       Gate 2006-IT
Question 1 Explanation: 
MST:
If all edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is minimum spanning tree.
Question 2
   
A
A heap can be used but not a balanced binary search tree
B
A balanced binary search tree can be used but not a heap
C
Both balanced binary search tree and heap can be used
D
Neither balanced binary search tree nor heap can be used
       Data-Structures       Tree       Gate-2003
Question 2 Explanation: 
→ In heap deletion takes O(log n).
Insertion of an element takes O(n).
→ In balanced primary tree deletion takes O(log n).
Insertion also takes O(log n).
Question 3
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
A
B
C
D
       Data-Structures       Tree       Gate-2002
Question 3 Explanation: 

Question 4
A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?
A
B
C
D
       Data-Structures       Tree       Gate-2002
Question 4 Explanation: 
Number of nodes in the left subtree is atleast half and atmost the num begin right sub tree.
No. of nodes in left sub tree = 2 right sub tree
No. of nodes in left sub tree = (n-1/3)
No. of nodes in right sub tree = 2(n-1/3)

Height of the tree = log3/2 n
There are 4 questions to complete.