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. 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 3. Consider the following C function.
float f(float x, int y)
{
  float p, s; int i;
  for (s=1, p=1, i=1; i < y; i++)
  {
    p*= x/i;
    s += p;
  }
  return s;
}

For large values of y, the return value of the function f best approximates

x^y

e^x

ln(1 + x)

x^x

Question 4. The maximum number of binary trees that can be formed with three unlabeled nodes is:

1

5

4

3

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

queue

stack

tree

list

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