Welcome to Data Structure Quiz, Advanced Level !!

Question 1. 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 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. 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 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. 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 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. 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 8. 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 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. 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