GATE CSE 2014 SET-1
Q22.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?Q23.
Consider a hash table with 9 slots. The hash function is h(k)=k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, areQ24.
Consider the 4-to-1 multiplexer with two lines S1 and S0 given below. The minimal sum of-products form of the Boolean expression for the output F of the multiplexer isQ26.
The value of the dot product of the eigenvectors corresponding to any pair of different eigenvalues of a 4-by-4 symmetric positive definite matrix isQ27.
Consider the following system of equations: 3x + 2y = 1 4x + 7z = 1 x + y + z = 3 x - 2y + 7z = 0 The number of solutions for this system isQ28.
Consider the following pseudo code. What is the total number of multiplications to be performed? D= 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D * 3Q29.
Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) { int Y = 0; int Z; int i, j, k; for(i = 0; i < size; i++) Y = Y + E[i]; for(i = 0; i < size; i++) for(j = i; j < size; j++) { Z = 0; for(k = i; k <= j; k++) Z= Z + E[k]; if (Z > Y) Y = Z; } return Y; } The value returned by the function MyX is theQ30.
A function f(x) is continuous in the interval [0,2]. It is known that f(0)=f(2)=-1 and f(1)=1. Which one of the following statements must be true?