Welcome to Data Structure Quiz, Entry Level !!

Question 1. 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 2. In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

log 2 n

n/2

log 2 n - 1

n

Question 3. 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 4. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?

s + m

s - m

m * s

m / s

Question 5. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

2

3

4

6

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

Quick sort

Insertion sort

Selection sort

Heap sort

Question 7. 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 8. Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

n(X + Y)

3Y + 2X

n(X + Y)-X

Y + 2X

Question 9. 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 10. The maximum number of binary trees that can be formed with three unlabeled nodes is:

1

5

4

3