Welcome to Data Structure Quiz, Randomly Selected !!

Question 1. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

d e b f g c a

e d b g f c a

e d b f g c a

d e f g b c a

Question 2. Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which of the following is true ?

T(n) = O(n^2)

T(n) = Theta(n^2)

T(n) = Omega(n^2)

T(n) = O(nLogn)

Question 3. How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2, ... V n} of n vertices





Question 4. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is





Question 5. Which one of the following in place sorting algorithms needs the minimum number of swaps?

Quick sort

Insertion sort

Selection sort

Heap sort

Question 6. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

Solves it in linear time using a left to right pass of the array

Solves it in linear time using a right to left pass of the array

Solves it using divide and conquer in time O(nlogn)

Solves it in time O(n^2)

Question 7. The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

2^h -1

2^(h-1) - 1

2^(h + 1) -1

2*(h + 1)

Question 8. Consider the following 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 9. 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 10. What is the worst-case time for serial search finding a single item in an array?

Constant time

Logarithmic time

Linear time

Quadratic time