Welcome to Data Structure Quiz, Entry Level !!

Question 1. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

O(n)

O(nlogn)

O(n^2)

O(n^2logn)

Question 2. 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 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 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 5. Which one of the following in place sorting algorithms needs the minimum number of swaps?

Quick sort

Insertion sort

Selection sort

Heap sort

Question 6. The best data structure to check whether an arithmetic expression has balanced parentheses is a

queue

stack

tree

list

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