Welcome to Data Structure Quiz, Advanced Level !!

Question 1. Which one of the following is a key factor for preferring B-trees to binary search trees for indexing database relations?

Database relations have a large number of records

Database relations are sorted on the primary key

B-trees require less memory than binary search trees

Data transfer form disks is in blocks.

Question 2. 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 3. 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 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. 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 6. 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 7. 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 8. Consider the following functions:
f(n) = 2^n
g(n) = n!
h(n) = n^logn
Which of the following statements about the asymptotic behavior of f(n), g(n), and h(n) is true?

f(n) = O(g(n)); g(n) = O(h(n))

f(n) = Omega(g(n)); g(n) = O(h(n))

g(n) = O(f(n)); h(n) = O(f(n))

h(n) = O(f(n)); g(n) = Omega(f(n))

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