Welcome to Data Structure Quiz, Intermediate Level !!

Question 1. 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 2. 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 3. 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 4. 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 5. How many distinct binary search trees can be created out of 4 distinct keys?

5

14

24

42

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. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity by

Dijkstra's algorithm starting from S.

Warshall's algorithm

Performing a DFS starting from S.

Performing a BFS starting from S.

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