Welcome to Data Structure Quiz, Entry Level !!

Question 1. The following postfix expression with single digit operands is evaluated using a stack:
              8 2 3 ^ / 2 3 * + 5 1 * - ^
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

6, 1

5, 7

3, 2

1, 5

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. 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. 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

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

queue

stack

tree

list

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

Quick sort

Insertion sort

Selection sort

Heap sort

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

1

5

4

3