Welcome to Data Structure Quiz, Intermediate Level !!

Question 1. 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 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. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

O(n)

O(nlogn)

O(log*n)

O(n^2)

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. 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 6. To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Queue

Stack

Heap

B-Tree

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