Welcome to Data Structure Quiz, Entry Level !!

Question 1. What additional requirement is placed on an array, so that binary search may be used to locate an entry?

The array elements must form a heap.

The array must have at least 2 entries.

The array must be sorted.

The array's size must be a power of two.

Question 2. The running time of the following algorithm
Procedure A(n)
If n <= 2 return(1) else return A(sqrt(n));
is best described by

O(n)

O(log n)

O(1og log n)

O(1)

Question 3. 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 4. 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 5. 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 6. What is the worst-case time for serial search finding a single item in an array?

Constant time

Logarithmic time

Linear time

Quadratic time

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

Question 8. 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 9. 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 10. In a binary max heap containing n numbers, the smallest element can be found in time

0(n)

O(logn)

0(loglogn)

0(1)