Welcome to Data Structure Quiz, Randomly Selected !!

Question 1. Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?





Question 2. Consider the polynomial p(x) = a0 + a1x + a2x^2 a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:





Question 3. What is the time complexity of the following recursive function:
int DoSomething (int n) 
     if (n <= 2) 
         return 1; 
         return (DoSomething (floor(sqrt(n))) +  n); 





Question 4. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

At least 2n - c comparisons, for some constant c, are needed.

At most 1.5n - 2 comparisons are needed.

At least nLog2n comparisons are needed.

none of the above

Question 5. An undirected graph G has n nodes. Its adjacency matrix is given by an n * n square matrix whose (i) diagonal elements are 0's and (ii) non-diagonal elements are 1's. which one of the following is TRUE?

Graph G has no minimum spanning tree (MST)

Graph G has a unique MST of cost n-1

Graph G has multiple distinct MSTs, each of cost n-1

Graph G has multiple spanning trees of different costs

Question 6. Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

(1 2 (4 5 6 7))

(1 (2 3 4) 5 6) 7)

(1 (2 3 4)(5 6 7))

(1 (2 3 NULL) (4 5))

Question 7. Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;

int GetValue(struct CellNode *ptr)
  int value = 0;
  if (ptr != NULL)
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
      value = value +  GetValue(ptr->leftChild)
                   +  GetValue(ptr->rightChild);

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

the number of nodes in the tree

the number of internal nodes in the tree

the number of leaf nodes in the tree

the height of the tree

Question 8. Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:
1) Choose an i uniformly at random from 1..n;
2) If A[i] = x then Stop else Goto 1;
Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?


n - 1



Question 9. The running time of the following algorithm
Procedure A(n)
If n <= 2 return(1) else return A(sqrt(n));
is best described by


O(log n)

O(1og log n)


Question 10. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?