Welcome to Data Structure Quiz, Intermediate Level !!

Question 1. 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 2. The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:




(2n +1)/3

Question 3. How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2, ... V n} of n vertices





Question 4. 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;
      value = value +  GetValue(ptr->leftChild)
                   +  GetValue(ptr->rightChild);

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 5. Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which of the following is true ?

T(n) = O(n^2)

T(n) = Theta(n^2)

T(n) = Omega(n^2)

T(n) = O(nLogn)

Question 6. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

Solves it in linear time using a left to right pass of the array

Solves it in linear time using a right to left pass of the array

Solves it using divide and conquer in time O(nlogn)

Solves it in time O(n^2)

Question 7. What is the time complexity of the following recursive function:
int DoSomething (int n) 
     if (n <= 2) 
         return 1; 
         return (DoSomething (floor(sqrt(n))) +  n); 





Question 8. Consider the following C code segment:
int IsPrime(n) 
    int i,n; 
    for(i=2;i<=sqrt(n); i++  ) 
         if(n%i == 0) 
               printf("Not Prime\n"); 
               return 0;
    return 1; 

Let T(n) denotes the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

T(n) = O(sqrt(n)) and T(n) = Omega(sqrt(n))

T(n) = O(sqrt(n)) and T(n) = Omega(1)

T(n) = O(n) and T(n) = Omega(sqrt(n))

none of the above

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





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