Welcome to Data Structure Quiz, Advanced Level !!

Question 1. 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 2. 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 3. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
hash_table
Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

46, 42, 34, 52, 23, 33

34, 42, 23, 52, 33, 46

46, 34, 42, 23, 52, 33

42, 46, 33, 23, 34, 52

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

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

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