Welcome to Data Structure Quiz, Entry Level !!

Question 1. Consider the following nested representation of binary trees: (X Y Z) indicates Y and Z are the left and right sub stress, respectively, of node X. Note that Y and Z may be NULL, or further nested. Which of the following represents a valid binary tree?

(1 2 (4 5 6 7))

(1 (2 3 4) 5 6) 7)

(1 (2 3 4)(5 6 7))

(1 (2 3 NULL) (4 5))

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

1

5

4

3

Question 4. 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 5. 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 6. 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 7. The best data structure to check whether an arithmetic expression has balanced parentheses is a

queue

stack

tree

list

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

LASTIN = LASTPOST

LASTIN = LASTPRE

LASTPRE = LASTPOST

none of the above

Question 9. 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 10. A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X[i], the left child, if any, is stored in X[2i] and the right child, if any, in X[2i + 1]. To be able to store any binary tree on n vertices the minimum size of X should be.

log2n

n

2n + 1

2^n - 1