Welcome to Data Structure Quiz, Entry Level !!

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

Quick sort

Insertion sort

Selection sort

Heap sort

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. 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 4. The most appropriate matching for the following pairs
X: depth first search 1: heap
Y: breadth-first search 2: queue
Z: sorting 3: stack

X - 1 Y - 2 Z - 3

X - 3 Y - 1 Z - 2

X - 3 Y - 2 Z - 1

X - 2 Y - 3 Z - 1

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

queue

stack

tree

list

Question 6. 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 7. 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 8. 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 9. 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 10. What is the worst-case time for serial search finding a single item in an array?

Constant time

Logarithmic time

Linear time

Quadratic time