Welcome to Data Structure Quiz, Advanced Level !!

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

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