GATE CSE 2015 SET-1
Q21.
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?Q22.
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?Q23.
The output of the following C program is__________. void f1(int a, int b) { int c; c=a; a=b; b=c; } void f2(int *a, int *b) { int c; c=*a; *a=*b; *b=c; } int main(){ int a=4, b=5, c=6; f1(a,b); f2(&b, &c); printf("%d",c-a-b); }Q24.
Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider that a value 35 is inserted into this heap. After insertion, the new heap isQ25.
The least number of temporary variables required to create a three-address code in static single assignment form for the expression q + r / 3 + s - t * 5 + u * v /w is _______________.Q26.
A variable x is said to be live at a statement S_{i} in a program if the following three conditions hold simultaneously: i. There exists a statement S_{j} that uses x ii. There is a path from S_{i} to S_{j} in the flow graph corresponding to the program iii. The path has no intervening assignment to x including at S_{i} and S_{j} The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph areQ27.
An algorithm performs (log N)^{1/2} find operations, N insert operations, (log N)^{1/2} delete operations, and (log N)^{1/2} decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?Q28.
Consider the following 2x2 matrix A where two elements are unknown and are marked by a and b. The eigenvalues of this matrix are -1 and 7. What are the values of a and b? A=\begin{pmatrix} 1 & 4\\ b&a \end{pmatrix}.Q29.
In the LU decomposition of the matrix \begin{bmatrix} 2 & 2\\ 4&9 \end{bmatrix}, if the diagonal elements of U are both 1, then the lower diagonal entry l_{22} of L is________.Q30.
Suppose L={p,q,r,s,t} is a lattice represented by the following Hasse diagram: For any x,y\in L not necessarily distinct, x\vee y and x\wedge y are join and meet of x,y respectively. Let L^{3}=\{(x,y,z):x,y,z\in L\} be the set of all ordered triplets of the elements of L. Let P_{r} be the probability that an element (x,y,z)\in L^{3} chosen equiprobably satisfies x\vee (y \wedge z)=(x\vee y)\wedge (x\vee z) . Then