Loading

SET 5


  Question 1

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

A : 2h-1
B : 2h-1-1
C : 2h+1-1
D : 2h+1


  •  
    .

     Correct answer is :C

     Solution :
      Maximum number of nodes will be there for a complete tree. Number of nodes in a complete tree of height h = 1 + 2 + 2^2 + 2*3 + .... 2^h = 2^(h+1) - 1

  •   Question 2

    The maximum number of binary trees that can be formed with three unlabeled nodes is:

    A : 1
    B : 5
    C : 4
    D : 3


  •  
    .

     Correct answer is :B

     Solution :
     
                 O
              /     
            O        O
               (i)
    
                O             
              /                             
           O                 
         /                      
       O                         
            (ii)
    
             O
           / 
         O
            
              O
           (iii)
    
      O                      
                                 
           O                     
                                
               O                                                

  •   Question 3

    The following postfix expression with single digit operands is evaluated using a stack:
    8 2 3 ^ / 2 3 * + 5 1 * -
    Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:


    A : 6,1
    B : 5,7
    C : 3,2
    D : 1,5


  •  
    .

     Correct answer is :A


  •   Question 4

    The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

    A : d e b f g c a
    B : e d b g f c a
    C : e d b f g c a
    D : d e f g b c a


  •  
    .

     Correct answer is :A

     Solution :
     
    Below is the given tree.
                                  a 
                               /    
                            /          
                          b             c
                       /             /   
                     /             /       
                   d         e    f          g


  •   Question 5

    A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

    A : 3
    B : 4
    C : 5
    D : 6


  •  
    .

     Correct answer is :C

     Solution :
      For an n-ary tree where each node has n children or no children, following relation holds
    L = (n-1)*I + 1
    Where L is the number of leaf nodes and I is the number of internal nodes.
    Let us find out the value of n for the given data.
    L = 41 , I = 10
    41 = 10*(n-1) + 1
    (n-1) = 4
    n = 5

  •   Question 6

    Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

    A : θ (logn)
    B : θ (loglogn)
    C : θ (n)
    D : θ (n logn)


  •  
    .

     Correct answer is :B

     Solution :
      The height of a Max Heap is ?(logn). If we perform binary search for finding the correct position then we need to do ?(LogLogn) comparisons.

  •   Question 7

    You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2, ..., n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

    A : O(log n)
    B : O(n)
    C : O(n log n)
    D : none of the above, as the tree cannot be uniquely determined


  •  
    .

     Correct answer is :B


  • MY REPORT
    TOTAL = 7
    ANSWERED =
    CORRECT / TOTAL = /7
    POSITIVE SCORE =
    NEGATIVE SCORE =
    FINAL SCORE =