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

1

5

4

3

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

queue

stack

tree

list