Welcome to Data Structure Quiz, Entry Level !!

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

Question 2. In a binary max heap containing n numbers, the smallest element can be found in time

0(n)

O(logn)

0(loglogn)

0(1)

Question 3. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

O(nlogn)

O(n)

O(logn)

O(1)

Question 4. Which of the following sorting algorithms has the lowest worst-case complexity?

Merge sort

Bubble sort

Quick sort

Selection sort

Question 5. The most appropriate matching for the following pairs
X: depth first search 1: heap
Y: breadth-first search 2: queue
Z: sorting 3: stack

X - 1 Y - 2 Z - 3

X - 3 Y - 1 Z - 2

X - 3 Y - 2 Z - 1

X - 2 Y - 3 Z - 1

Question 6. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

O(n)

O(nlogn)

O(n^2)

O(n^2logn)

Question 7. The maximum number of binary trees that can be formed with three unlabeled nodes is:

1

5

4

3

Question 8. 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 9. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?
Queue

rear node

front node

not possible with a single pointer

node next to front

Question 10. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

7 5 1 0 3 2 4 6 8 9

0 2 4 3 1 6 5 9 8 7

0 1 2 3 4 5 6 7 8 9

9 8 6 4 2 3 0 1 5 7