Loading

SET 1


  Question 1

Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?
1. 3, 5, 7, 8, 15, 19, 25
2. 5, 8, 9, 12, 10, 15, 25
3. 2, 7, 10, 8, 14, 16, 20
4. 4, 6, 7, 9, 18, 20, 25


A : 1 and 4 only
B : 2 and 3 only
C : 2 and 4 only
D : 2 only


  •  
    .

     Correct answer is :A

     Solution :
      Inorder traversal of binary search tree gives ascending orders.

  •   Question 2

    The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height 5 are

    A : 63 and 6, respectively
    B : 63 and 5, respectively
    C : 32 and 6, respectively
    D : 31 and 5, respectively


  •  
    .

     Correct answer is :A

     Solution :
      Maximum no. of nodes in a binary tree with height h 1 h = 2h+1-1 = 64-1 63.
    Minimum no. of nodes with height h is h+1(in every only one node will be there). h=5

  •   Question 3

    Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4.
    Now consider that a value 35 is inserted into this heap. After insertion, the new heap is




    A : 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
    B : 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
    C : 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
    D : 40, 35, 20, 10, 15, 16, 17, 8, 4, 30


  •  
    .

     Correct answer is :B


  •   Question 4

    A binary tree T has 20 leaves. The number of nodes in T having two children is _________.



  •  
    .

     Correct answer is :19

     Solution :
      Let the number of vertices of a binary tree with p? leaves be n then the tree has
    (i) p vertices (i.e., leaves) of degree 1
    (ii) one vertex (i.e.., root of T) of degree 2
    (iii) 'n - p -1' (i.e., interval) vertices of degree 3
    (iv) n -1edges
    By Handshaking theorem,
    p*1+1*2+(n-p-1)*3=2(n-1)
    => n=2p-1
    =39 as p=20
    n-p=19 vertices have exactly two children

  •   Question 5

    Consider a complete binary tree where the left and the right subtrees of the root are maxheaps. The lower bound for the number of operations to convert the tree to a heap is

    A : Ω (log n)
    B : Ω (n)
    C : Ω (n log n)
    D : Ω (n 2)


  •  
    .

     Correct answer is :A


  •   Question 6

    Consider the following array of elements.
    <89,19,50,17,12,15,2,5,7,11,6,9,100>
    The minimum number of interchanges needed to convert it into a max-heap is


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


  •  
    .

     Correct answer is :D

     Solution :
      1st swap is : 100 and 15
    2nd swap is : 100 and 50
    3rd swap is : 100 and 89


  •   Question 7

    While inserting the elements 71,65,84,69,67,83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

    A : 65
    B : 67
    C : 69
    D : 83


  •  
    .

     Correct answer is :B



  •   Question 8

    The result evaluating the postfix expression 10 5 + 60 6 / *8 - is

    A : 284
    B : 213
    C : 142
    D : 71


  •  
    .

     Correct answer is :C



  •   Question 9

    Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are ____ .



  •  
    .

     Correct answer is :199

     Solution :
      Let the number of leaf nodes of a binary tree with n vertices be p then the tree has
    (i) p vertices of degree 1
    (ii) one vertex (i.e. root of T) of degree 2.
    (iii) 'n - p - 1' vertices of degree 3
    (iv) 'n - 1' edges
    By Handshaking theorem,
    p1+1 2 + (n - p - 1)3 = 2(n - 1)
    n=2p-1
    =399 as p =200
    Number of nodes having exactly two children are n - p i.e., 199

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