Home | About Indiatry | Login | Register

    • ( 1 ) Predict the output of following C++ program
      #include
      using namespace std;
      class Base
      {
      public:
      virtual void show() { cout<<" In Base \n"; }
      };
      class Derived: public Base
      {
      public:
      void show() { cout<<"In Derived \n"; }
      };
      int main(void)
      {
      Base *bp = new Derived;
      bp->Base::show(); // Note the use of scope resolution here
      return 0;
      }

    • 1) In Base
    • 2) In Derived
    • 3) Compiler Error
    • 4) Runtime Error
    • Discussion in forum
      Answer : 1) In Base
      Solution : A base class function can be accessed with scope resolution operator even if the function is virtual.








      discussion


      Answer : 1) In Base

    • ( 2 ) B+ trees are preferred to binary trees in databases because

    • 1) Disk capacities are greater than memory capacities
    • 2) Disk access is much slower than memory access
    • 3) Disk data transfer rates are much less than memory data transfer rates
    • 4) Disks are more reliable than memory
    • Discussion in forum
      Answer : 2) Disk access is much slower than memory access
      Solution : Disk access is slow and B+ Tree provide search in less number of disk hits. This is primarily because unlike binary seach trees, B+ trees have very high fanout (typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree








      discussion


      Answer : 2) Disk access is much slower than memory access

    • ( 3 ) What is the worst case possible height of Red-Black tree? Assume base of Log as 2 in all options

    • 1) 2Log(n+1)
    • 2) 1.44 Logn
    • 3) 4Logn
    • 4) None of these
    • Discussion in forum
      Answer : 1) 2Log(n+1)
      Solution :








      discussion


      Answer : 1) 2Log(n+1)

    • ( 4 ) The order of a leaf node in a tree B+ ? is the maximum number of (value, data record pointer) pairs it can hold. Given that the block size is 1K bytes, data record pointer is 7 bytes long, the value field is 9 bytes long and a block pointer is 6 bytes long, what is the order of the leaf node?

    • 1) 63
    • 2) 64
    • 3) 67
    • 4) 68
    • Discussion in forum
      Answer : 1) 63
      Solution : Disk Block size = 1024 bytes
      Data Record Pointer size, r = 7 bytes
      Value size, V = 9 bytes
      Disk Block ptr, P = 6 bytes
      Let order of leaf be m. A leaf node in B+ tree contains at most m record pointers, at most m values, and one disk block pointer. r*m + V*m + p <= 1024 16m <= 1018 m =< 63








      discussion


      Answer : 1) 63

    • ( 5 ) Which of the following is true about Red Black Trees?

    • 1) The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf
    • 2) At least one children of every black node is red
    • 3) Root may be red
    • 4) A leaf node may be red
    • Discussion in forum
      Answer : 1) The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf
      Solution :








      discussion


      Answer : 1) The path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf

    • ( 6 ) In a complete k-ary tree, every internal node has exactly k children or no child. The number of leaves in such a tree with n internal nodes is:

    • 1) nk
    • 2) (n - 1) k+ 1
    • 3) n( k - 1) + 1
    • 4) n(k - 1)
    • Discussion in forum
      Answer : 3) n( k - 1) + 1
      Solution :








      discussion


      Answer : 3) n( k - 1) + 1

    • ( 7 ) A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be

    • 1) log2n
    • 2) n
    • 3) 2n + 1
    • 4) 2n - 1
    • Discussion in forum
      Answer : 4) 2n - 1
      Solution : For a right skewed binary tree, number of nodes will be 2n - 1. For example, in below binary tree, node 'A' will be stored at index 1, 'B' at index 3, 'C' at index 7 and 'D' at index 15.
      A
      \
       \
        B
        \
         \
         C
          \
          \
           D








      discussion


      Answer : 4) 2n - 1

    • ( 8 ) 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?

    • 1) O(Logn)
    • 2) O(n)
    • 3) O(nLogn)
    • 4) None of these
    • Discussion in forum
      Answer : 2) O(n)
      Solution :








      discussion


      Answer : 2) O(n)

    • ( 9 ) Consider B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is

    • 1) 49
    • 2) 50
    • 3) 51
    • 4) 52
    • Discussion in forum
      Answer : 2) 50
      Solution : Let m be the order of B+ tree
      m(8)+(m-1)12 <= 1024
      [Note that record pointer is not needed in non-leaf nodes]
      m <= 51
      Since maximum order is 51, maximum number of keys is 50.








      discussion


      Answer : 2) 50

    • ( 10 ) A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program is

    • 1) θ(n)
    • 2) θ(nLogn)
    • 3) θ(n2)
    • 4) θ(n2log n)
    • Discussion in forum
      Answer : 2) θ(nLogn)
      Solution : The recurrence relation for the recursive function is
      T(N) = 2 * T(N/2) + n/2
      Where N is the total no. of nodes in the tree.
      T(N) = 2 * (2*T(N/2) + n/2) + n/2
      = 4 * T(N/2) + 3(n/2)
      Solve this till T(1) i.e. till we reach the root.
      T(N) = c * T(N / 2i) + (2*i - 1) * (n/2)
      Where i = lg(N)
      = lg((2n - 1) / 2)
      O(c * T(N / 2i) + (2*i - 1) * (n/2)) reduces to
      O((2*i - 1) * (n/2))
      O((2*( lg((2n - 1) / 2)) - 1) * (n/2)) ...sub the value of i.
      O(n * ln(n))








      discussion


      Answer : 2) θ(nLogn)





Top