Loading

SET 2


  Question 1

Consider rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of sub trees having exactly 4 nodes is O(na log n b). Then the value of a + 10b is_______



  •  
    .

     Correct answer is :1

     Solution :
      int print_subtrees_size_4(node *n)
    {
    int size=0;
    if(node==null)
    return 0;
    size=print_subtrees_size_4(node->left)+print_subtrees_size_4(node->right)+1;
    if(size==4)
    printf("this is a subtree of size 4");
    return size;
    }
    The above function on taking input the root of a binary tree prints all the subtrees of size 4 in O(n) time

  •   Question 2

    A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

    A : 10, 8, 7, 3, 2, 1, 5
    B : 10, 8, 7, 2, 3, 1, 5
    C : 10, 8, 7, 1, 2, 3, 5
    D : 10, 8, 7, 5, 3, 2, 1


  •  
    .

     Correct answer is :A


  •   Question 3

    Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.



  •  
    .

     Correct answer is :358

     Solution :
      The implementation of optimal algorithm for merging sequences is as follows. In it total number of comparisons is (44-1)+(94-1)+(65-1)+(159-1) = 358


  •   Question 4

    Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the expression represented by the tree is ___.





  •  
    .

     Correct answer is :6


  •   Question 5

    Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

    A : A queue cannot be implemented using this stack.
    B : A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of
    C : A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a
    D : A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.


  •  
    .

     Correct answer is :C

     Solution :
      Option (a) is false because queue can be implemented by using the modified stack as by reversing the stack. LIFO will become FIFO. Implementation of ENQUEUE & DEQUEUE takes four sequence of instructions as follows:
    1 .ENQUEUE : Reverse , Push , Reverse and DEQUEUE : Pop.
    2.Enqueue: Push and Dequeue: Reverse, POP, Reverse

  •   Question 6

    Consider the following rooted tree with the vertex labelled P as the root
    The order in which the nodes are visited during an in-order traversal of the tree is




    A : SQPTRWUV
    B : SQPTUWRV
    C : SQPTWUVR
    D : SQPTRUWV


  •  
    .

     Correct answer is :A

     Solution :
      The In order Traversal of Ternary Tree is done as follows:
    Left -> Root ->Middle -> Right
    So the nodes are visited in SQPTRWUV order.

  •   Question 7

    Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
    
    typedef struct treeNode* treeptr;
    struct treeNode
    {
        treeptr leftMostChild, rightSibling;
    };
    int DoSomething (treeptr tree)
    {
        int value=0;
        if (tree != NULL)
        {
            if (tree->leftMostChild == NULL)
                value = 1;
            else
                value = DoSomething(tree->leftMostChild);
            value = value + DoSomething(tree->rightSibling);
        }
        return(value);
    }
    
    


    A : number of internal nodes in the tree.
    B : height of the tree.
    C : number of nodes without a right sibling in the tree.
    D : number of leaf nodes in the tree.


  •  
    .

     Correct answer is :D

     Solution :
      The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.
    Here, that condition is if (tree->leftMostchild == Null)
    Which means if there is no left most child of the tree (or the sub-tree or the current nodeas called in recursion)
    Which means there is no child to that particular node (since if there is no left most child, there is no child at all).
    Which means the node under consideration is a leaf node

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