Welcome to Data Structure Quiz, Entry Level !!

Question 1. Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely
i) preorder and postorder
ii) inorder and postorder
iii) preorder and inorder
iv) level order and postorder

(i) only

(ii), (iii)

(iii) only

(iv) only

Question 2. 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 3. 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 4. 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 5. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?




none of the above

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. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time





Question 8. The problem 3-SAT and 2-SAT are

both in P

both NP complete

NP-complete and in P respectively

undecidable and NP-complete respectively

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. Level order traversal of a rooted tree can be done by starting from the root and performing

preorder traversal

in-order traversal

depth first search

breadth first search