Welcome to Data Structure Quiz, Intermediate Level !!

Question 1. The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

O(n)

O(nlogn)

O(n^2)

O(n^3)

Question 2. Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode
{
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;
};

int GetValue(struct CellNode *ptr)
{
  int value = 0;
  if (ptr != NULL)
  {
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
   else
      value = value +  GetValue(ptr->leftChild)
                   +  GetValue(ptr->rightChild);
  }
  return(value);
}

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

the number of nodes in the tree

the number of internal nodes in the tree

the number of leaf nodes in the tree

the height of the tree

Question 3. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

n/2

(n-1)/3

(n-1)/2

(2n +1)/3

Question 4. How many distinct binary search trees can be created out of 4 distinct keys?

5

14

24

42

Question 5. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

O(n)

O(nlogn)

O(log*n)

O(n^2)

Question 6. A program P reads in 500 integers in the range [0..100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

An array of 50 numbers

An array of 100 numbers

An array of 500 numbers

A dynamically allocated array of 550 numbers

Question 7. The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:

d e b f g c a

e d b g f c a

e d b f g c a

d e f g b c a

Question 8. Consider the following algorithm for searching for a given number x in an unsorted array A[1..n] having n distinct values:
1) Choose an i uniformly at random from 1..n;
2) If A[i] = x then Stop else Goto 1;
Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?

n

n - 1

2n

n/2

Question 9. What is the number of swaps required to sort n elements using selection sort, in the worst case?

O(n)

O(nlogn)

O(n^2)

O(n^2 log n)

Question 10. Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

25,12,16,13,10,8,14

25,14,13,16,10,8,12

25,14,16,13,10,8,12

25,14,12,13,10,8,16