Welcome to Data Structure Quiz, Advanced Level !!

Question 1. A set X can be represented by an array x[n] as follows:
array pic
Consider the following algorithm in which x,y and z are Boolean arrays of size n:
algorithm zzz(x[] , y[], z []) 
    int i; 
    for (i=O; i<n;   ++i) 
    z[i] = (x[i] ^ ~y[i]) U (~x[i] ^ y[i]) 

The set Z computed by the algorithm is:

(X Intersection Y)

(X Union Y)

(X-Y) Intersection (Y-X)

(X-Y) Union (Y-X)

Question 2. A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.
Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?

1, 3, 5, 6, 8, 9

9, 6, 3, 1, 8, 5

9, 3, 6, 8, 5, 1

9, 5, 6, 8, 3, 1

Question 3. In the following C function, let n >= m.
int gcd(n,m) 
      if (n%m ==0) return m;  
      n = n%m; 
      return gcd(m,n); 

How many recursive calls are made by this function?





Question 4. Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

T(n) <= 2T(n/5) + n

T(n) <= T(n/5) + T(4n/5) + n

T(n) <= 2T(4n/5) + n

T(n) <= 2T(n/2) + n

Question 5. 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 6. The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is





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

10, 8, 7, 5, 3, 2, 1

10, 8, 7, 2, 3, 1, 5

10, 8, 7, 1, 2, 3, 5

10, 8, 7, 3, 2, 1, 5

Question 8. Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?

f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)

f3, f2, f4, f1

f3, f2, f1, f4

f2, f3, f1, f4

f2, f3, f4, f1

Question 9. 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 10. Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 < k <= n:
  reverse (s, 1, k);
  reverse (s, k + 1, n);
  reverse (s, 1, n);

Rotates s left by k positions

Leaves s unchanged

Reverses all elements of s

none of the above