Welcome to Data Structure Quiz, Intermediate Level !!

Question 1. We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

0

1

n!

(1/(n + 1)).2nCn

Question 2. The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?

1,2,3,4,5,6,7

2,1,4,3,6,5,7

1,3,2,5,4,7,6

2,3,4,5,6,7,1

Question 3. 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 4. Consider the function f defined below.
struct item
{
  int data;
  struct item * next;
}; 

int f(struct item *p)
{
  return (
          (p == NULL) ||
          (p->next == NULL) ||
          (( P->data <= p->next->data) && f(p->next))
         );
}

For a given linked list p, the function f returns 1 if and only if

the list is empty or has exactly one element

the elements in the list are sorted in non-decreasing order of data value

the elements in the list are sorted in non-increasing order of data value

not all elements in the list have the same data value.

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

O(n)

O(nlogn)

O(logn)

O(loglogn)

Question 6. What is the maximum height of any AVL tree with 7 nodes? Assume that the height of a tree with a single node is 0.

2

3

4

5

Question 7. Let X be a problem that belongs to the class NP. Then which one of the following is TRUE?

There is no polynomial time algorithm for X.

If X can be solved deterministically in polynomial time, then P = NP.

If X is NP-hard, then it is NP-complete.

X may be undecidable.

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

n(n-l)/2

2^n

n!

2^(n(n-1)/2)

Question 9. 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 10. 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