Welcome to Data Structure Quiz, Randomly Selected !!

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. 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 3. Consider a B+ - tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?

1

2

3

4

Question 4. The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
Graph

MNOPQR

NQMPOR

QMNPRO

QMNPOR

Question 5. The most appropriate matching for the following pairs
X: depth first search 1: heap
Y: breadth-first search 2: queue
Z: sorting 3: stack

X - 1 Y - 2 Z - 3

X - 3 Y - 1 Z - 2

X - 3 Y - 2 Z - 1

X - 2 Y - 3 Z - 1

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. The maximum number of binary trees that can be formed with three unlabeled nodes is:

1

5

4

3

Question 8. An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

Solves it in linear time using a left to right pass of the array

Solves it in linear time using a right to left pass of the array

Solves it using divide and conquer in time O(nlogn)

Solves it in time O(n^2)

Question 9. Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

n(X + Y)

3Y + 2X

n(X + Y)-X

Y + 2X

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