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?





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





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





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:




(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^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.