Welcome to Data Structure Quiz, Advanced Level !!

Question 1. 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 2. 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 3. 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 4. 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 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. 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 7. 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 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. 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 10. Consider a B+ - tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

1

2

3

4