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. 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 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?

Theta(logn)

Omega(n)

Theta(loglogn)

Theta(sqrt(n))

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

3

4

6

9

Question 6. 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 7. 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 8. 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 9. 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 10. A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl < top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for "stack full" is

(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2 + 1)

top1 + top2 = MAXSIZE

(top1= MAXSIZE/2) or (top2 = MAXSIZE)

top1= top2 -1