Welcome to Data Structure Quiz, Randomly Selected !!

Question 1. In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?





Question 2. Consider the following C program segment where CellNode represents a node in a binary tree:
struct CellNode
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;

int GetValue(struct CellNode *ptr)
  int value = 0;
  if (ptr != NULL)
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
      value = value +  GetValue(ptr->leftChild)
                   +  GetValue(ptr->rightChild);

The value returned by GetValue() when a pointer to the root of a binary tree is passed as its argument is:

the number of nodes in the tree

the number of internal nodes in the tree

the number of leaf nodes in the tree

the height of the tree

Question 3. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of





Question 4. 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 5. 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 6. 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 7. 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 8. In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is:


(n - 1) k + 1

n( k - 1) + 1

n(k - 1)

Question 9. 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 10. In a binary max heap containing n numbers, the smallest element can be found in time