Let T be a depth first search tree in an undirected graph G. Vertices u and n are leaves of this tree T.

The degrees of both u and n in G are at least 2. Which one of the following statements is true?

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 the median is selected as pivot?

A set X can be represented by an array x [n] as follows:

x$\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & otherwise \end{cases}$ Consider the following algorithm in which x, y and z are boolean arrays of size n. algorithm zzz (x [ ], y[ ], z [ ] ) { int i; for (i = 0 ; i< n; ++i) z[i] = (x[i] Ù ~y[i]) Ú (~x[i] Ù y[i]) }

The set Z computed by the algorithm is

The order of the following recurrence: $T(n) = 2T([\sqrt{n}]) + 1$
is

Consider the following code written in a pass-by-reference language like FORTRAN and these statements about the code.

S1: The compiler will generate code to allocate a temporary nameless cell, initialize it to 13, and pass the address of the cell swap S2: On execution the code will generate a runtime error on line L1 S3: On execution the code will generate a runtime error on line L2 S4: The program will print 13 and 8 S5: The program will print 13 and - 2 Exactly the following set of statement(s) is correct:

Given two arrays of numbers a₁,..........., a_n and b₁,............, b_n where each number is 0 or 1, the fastest algorithm to find the largest span (i, j ) such that a_i + a_i+1 + .........+ a_j = b_i + b_{i + 1} +...........+ b_j or report that there is not such span,

The maximum number of binary trees that can be formed with three unlabeled nodes is:

The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is:

Which of the following sorting algorithms has the lowest worst-case complexity?

The in order and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively The post order traversal of the binary tree is:

Consider a hash table of size seven, with starting index zero, and a hash function (3x + 4) mod 7. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10 is inserted into the table using closed hashing? Note that − denotes an empty location in the table.

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

A complete n-ary tree is a tree in which each node has n children or no children. Let I be the number of internal nodes and L be the number of leaves in a complete n-ary tree. If L = 41, and I = 10, what is the value of n?

What is the time complexity of the following recursive function?

Int Do Something (int n) {
return 1;
else
return (Do Something (floor sqrt (n))) + n);

Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight w . Which of the following is FALSE?

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

In the following C function, let n ^$\ge$ m.

Int gcd (n,m) { 
  if (n% m ==0) return m;
  n = n %m;
  return gcd (m, n);
}

How many recursive calls are made by this function?

An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?

Consider the following C code segment:

int Is Prime (n) 
{
int i, n;
for (i = 2; i <= sqrt (n) ; i ++)
 if (n% i == 0) { 
   print f (“ Not Prime  n”);
   return 0; 
  } 
  return 1;
}

Let T (n) denote the number of times the for loop is executed by the program on input n. Which of the following is TRUE?

Suppose the letters a, b, c, d, e, f have probabilities $ \dfrac{1}{2},\dfrac{1}{4},\dfrac{1}{8},\dfrac{1}{16},\dfrac{1}{32},\dfrac{1}{32}$ respectively.

Which of the following is the Huffman code for the letter a, b, c, d, e, f?