Welcome to Data Structure Quiz, Intermediate Level !!

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





Question 4. 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 5. 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 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:





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





Question 9. 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?




(1/(n + 1)).2nCn

Question 10. The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?