Welcome to Data Structure Quiz, Advanced Level !!

Question 1. Consider the following recurrence:
recurrence
Which one of the following is true?

T(n) = Theta(loglogn)

T(n) = Theta(logn)

T(n) = Theta(sqrt(n))

T(n) = Theta(n)

Question 2. 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 3. 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 4. Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4)mod7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that '_' denotes an empty location in the table.

8, _, _, _, _, _, 10

1, 8, 10, _, _, _, 3

1, _, _, _, _, _,3

1, 10, 8, _, _, _, 3

Question 5. An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 , .. vn. Two nodes vi , vj are connected if and only if 0 < |i - j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below
Graph
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

1/12(11n^2 - 5n)

n^2 - n + 1

6n - 11

2n + 1

Question 6. Consider the following C program that attempts to locate an element x in an array Y[] using binary search. The program is erroneous.
f(int Y[10], int x) { 
	int i, j, k; 
	i = 0; j = 9; 
	do { 
		k = (i +  j) /2; 
		if( Y[k] < x) i = k; else j = k; 
	} while(Y[k] != x && i < j); 
	if(Y[k] == x) printf ("x is in the array") ; 
	else printf ("x is not in the array") ; 
}

On which of the following contents of Y and x does the program fail?

Y is [1 2 3 4 5 6 7 8 9 10] and x < 10

Y is [1 3 5 7 9 11 13 15 17 19] and x < 1

Y is [2 2 2 2 2 2 2 2 2 2] and x > 2

Y is [2 4 6 8 10 12 14 16 18 20] and 2 > ?x < 20 and x is even

Question 7. 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:

3

4

6

9

Question 8. In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:

nk

(n - 1) k + 1

n( k - 1) + 1

n(k - 1)

Question 9. 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
Graph

MNOPQR

NQMPOR

QMNPRO

QMNPOR

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