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. 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 3. 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 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. 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 6. The following C function takes a simply-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.
typedef struct node
{
  int value;
  struct node *next;
}Node;

Node *move_to_front(Node *head)
{
  Node *p, *q;
  if ((head == NULL: || (head->next == NULL))
    return head;
  q = NULL; p = head;
  while (p-> next !=NULL)
  {
    q = p;
    p = p->next;
  }
  _______________________________
  return head;
}

Choose the correct alternative to replace the blank line.

q = NULL; p->next = head; head = p;

q->next = NULL; head = p; p->next = head;

head = p; p->next = q; q->next = NULL;

q->next = NULL; p->next = head; head = p;

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