# Computer Science and Information Technology - GATE 2006 Paper Solution

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

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

 (A) $\theta \left(n\right)$ (B) (C) (D) $\theta \left(1\right)$

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 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)$

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

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, inX[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$

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

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) (B) (C) $val\left(j\right)=\theta \left(n\right)$ (D)

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 (D) Solves it in time $\theta \left({n}^{2}\right)$

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)$

Let T be a depth first search tree in a undirected graph 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

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

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)$

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) (B) (C) (D) $T\left(n\right)=\theta \left(n\right)$

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) (C) $\theta \left({n}^{2}\right)$ (D) $\theta \left({n}^{3}\right)$

Given two arrays of numbers a1.......an and ,b1.....bnb where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that ai++aj+1+ ...... ...... ,+aj=bi+bj+1+..........+bj  or report that there is no such span,

 (A) Takes O( 3 n) Ω (2n)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

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

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

 $S\to FR$ $R\to *S|\epsilon$ $F\to id$