Welcome to Data Structure Quiz, Randomly Selected !!

Question 1. 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 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. Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:
1) Choose an i uniformly at random from 1..n;
2) If A[i] = x then Stop else Goto 1;
Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?

n

n - 1

2n

n/2

Question 4. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

n

n^2

nlogn

n(log^2)n

Question 5. What is the number of swaps required to sort n elements using selection sort, in the worst case?

O(n)

O(nlogn)

O(n^2)

O(n^2 log n)

Question 6. 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 7. Given the following input (4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199) and the hash function x mod 10, which of the following statements are true?
i. 9679, 1989, 4199 hash to the same value
ii. 1471, 6171 has to the same value
iii. All elements hash to the same value
iv. Each element hashes to a different value

i only

ii only

i and ii only

iii or iv

Question 8. We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

0

1

n!

(1/(n + 1)).2nCn

Question 9. A program P reads in 500 integers in the range [0..100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

An array of 50 numbers

An array of 100 numbers

An array of 500 numbers

A dynamically allocated array of 550 numbers

Question 10. The time complexity of the following C function is (assume n > 0
int recursive (mt n)
{
   if (n == 1)
     return (1);
   else
     return (recursive (n-1) +  recursive (n-1));
}

0(n)

0(nlogn)

0(n^2)

0(2^n)