Consider the polynomial $P\left(x\right)={a}_{0}+{a}_{1}x+{a}_{2}{x}^{2}+{a}_{2}{x}^{3}$ where ,. ${a}_{i}\ne 0,\forall i$ The minimum num- ber of multiplications needed to evaluate *p* on an input *x* is

(A) 3 | (B) 4 |

(C) 6 | (D) 9 |

##### Answer :

In a binary max heap containing *n* numbers, the smallest element can be found in time

(A) $\theta \left(n\right)$ | (B) $\theta \left(\mathrm{log}n\right)$ |

(C) $\theta \left(\mathrm{log}\mathrm{log}n\right)$ | (D) $\theta \left(1\right)$ |

##### Answer :

Consider a weighted complete graph *G* on the vertex set $\left\{{v}_{1},{v}_{2},...{v}_{n}\right\}$ such that the weight of the edge $\left({v}_{i},{v}_{j}\right)$2 $\left|i-j\right|$ . The weight of a minimum spanning tree of *G* is

(A) $n-1$ | (B) $2n-2$ |

(C) $\left(\frac{n}{2}\right)$ |

##### Answer :

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, then data structure to be used is

(A) Queue | (B) Stack |

(C) Heap | (D) B-Tree |

##### Answer :

A scheme for storing binary trees in an array *X* is as follows. Indexing of *X* starts at 1 instead of 0. The roots is stored at *X*[1]. For a node stored at *X*[1]. , the left child, if any, is stored in* X*[2i] and the right child, if any, in*X*[2i+1]. . To be able to store any binary tree on *n* vertices, the minimum size of *X* should be

(A) ${\mathrm{log}}_{2}n$ | (B) $n$ |

(C)$2n+1$ | (D) $2n$ |

##### Answer :

Which one the following in place sorting algorithms needs the minimum number of swaps?

(A) Quick-sort | (B) Insertion sort |

(C) Selection sort | (D) Heap sort |

##### Answer :

Consider the following C-program fragment in which * i,j*, and *n* are integer variables.

for (i=n,j=0;i/2,j+=i);

Let Val (j) =denote the value stored in the variable *j* after termination of the for loop. Which one of the following is true?

(A) $val\left(j\right)=\theta \left(\mathrm{log}n\right)$ | (B) $val\left(j\right)=\theta \left(\sqrt{n}\right)$ |

(C) $val\left(j\right)=\theta \left(n\right)$ | (D) $val\left(j\right)=\theta \left(n\mathrm{log}n\right)$ |

##### Answer :

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

(A) Solves it in linear time using a left to right pass of the array |

(B) Solves in linear time using a right to left pass |

(C) Solves it is using divide and conquer in time $\theta \left(n\mathrm{log}n\right)$ |

(D) Solves it in time $\theta \left({n}^{2}\right)$ |

##### Answer :

Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

(A)$\left(a-b\right).\left(d-f\right),\left(b-f\right).\left(d-c\right),\left(d-c\right)$ |

(B) $\left(a-b\right).\left(d-f\right),\left(b-c\right).\left(b-f\right),\left(d-e\right)$ |

(C) $\left(d-f\right).\left(a-b\right),\left(d-c\right).\left(d-e\right),\left(d-e\right)$ |

(D) $\left(d-f\right).\left(a-b\right),\left(b-f\right).\left(d-e\right),\left(d-e\right)$ |

##### Answer :

Let *T* be a depth first search tree in a undirected graph *G * Vertices *u* and *v* are leaves of this tree *T* . The degrees of both *u* and v in *G* are at least 2. Which one of the following statements is true?

(A) There must exist a vertex w adjacent to both U and V in G |

(B) There must exist a vertex w whose removal disconnects U and Vin G |

(C) There must be exist a cycle in G containing U and V |

(D) There must exist a cycle in G containing U and all its neighbours in G |

##### Answer :

*A* set *X* can be represented by an array $x\left[n\right]$ as follows

$x\left[i\right]=\left\{\begin{array}{ll}1& ifi\in X\\ 0& otherwise\end{array}\right.$

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])V(-x[i]^y[i])

}

The set *Z* computed by the algorithm is

(A) $\left(X\cup Y\right)$ | (B) $\left(X\cap Y\right)$ |

(C) $\left(X-Y\right)\cap \left(Y-X\right)$ | (D) $\left(X-Y\right)\cup \left(Y-X\right)$ |

##### Answer :

Consider the following is true?

$T\left(n\right)=2T\left(\left[\sqrt{n}\right]\right)+1,T\left(1\right)=1$

Which one of the following is true?

(A) $T\left(n\right)=\theta \left(\mathrm{log}\mathrm{log}n\right)$ | (B) $T\left(n\right)=\theta \left(\mathrm{log}n\right)$ |

(C) $T\left(n\right)=\theta \left(\sqrt{n}\right)$ | (D) $T\left(n\right)=\theta \left(n\right)$ |

##### Answer :

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

(A) $\theta \left(n\right)$ | (B) $\theta \left(n\mathrm{log}n\right)$ |

(C) $\theta \left({n}^{2}\right)$ | (D) $\theta \left({n}^{3}\right)$ |

##### Answer :

Given two arrays of numbers a_{1}.......a_{n }and ,b_{1}.....b_{n}b where each number is 0 or 1, the fastest algorithm to find the largest span (*i, j)* such that a* _{i+}+a_{j+1}*+ ...... ...... ,+a

_{j}=b

*+b*

_{i}*+..........+b*

_{j+1}*or report that there is no such span,*

_{j}
(A) Takes O( 3^{ n}) Ω (2^{n})time if hashing is permitted and |

(B) Takes O( n^{ 3}) .25 and W(n^{ 2.5} ^{ }) time in the key comparison model |

(C) Takes Θ(n) time and space |

(D) Takes O($\sqrt{n}$) time only if the sum of the n2 elements is an even number |

##### Answer :

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

Subroutine swap (ix,iy)

it =ix

L1: ix= iy

L2 : iy= it

end

ia =3

ib= 8

call swap (ia,ib +5)

print*, ia,ib

end

S1: The complier will generate code to allocate a temporary nameless cell, initialize it to 13, and pass the address of the cell to swap |

S2: On execution the code will generate a runtime error on line 1.1 |

S3: On execution the code will generate a runtime error on line 1.2 |

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:

(A) S1 and S2 | (B) S1 and S4 |

(C) S3 | (D) S1 and S5 |

##### Answer :

Consider the following grammar.

$S\to S*E$ |

$S\to E$ |

$E\to F+E$ |

$E\to F$ |

$F\to id$ |

Consider the following *LR* (0) items corresponding to the grammar above.

(i) $S\to S*.E$ |

(ii) $E\to F.+E$ |

(iii) $E\to F+.E$ |

Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?

(A) (i) and (ii) | (B) (ii) and (iii) |

(C) (i) and (iii) | (D) None of these |

##### Answer :

Consider the following grammar

$S\to FR$ |

$R\to *S|\epsilon $ |

$F\to id$ |

In the predictive parser table, *M* , of the grammar the entries* M* [*S,id* ]MSid and *M [ R,$]* respectively

(A) $\left\{S\to FR\right\}and\left\{R\to \epsilon \right\}$ | (B) $\left\{S\to FR\right\}and\left\{\right\}$ |

(C) $\left\{S\to FR\right\}and\left\{R\to *S\right\}$ | (D) $\left\{F\to id\right\}and\left\{R\to \epsilon \right\}$ |