# CS GATE 2009 (Test 4)

Tag: cs gate 2009
Q.1
A subsequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0. The values of l(i, j) could be obtained by dynamic programming based on the correct recursive definition of l(i, j) of the form given above, using an array L[M, N], where M = m + 1 and N = n + 1, such that L[i, j] = l(i, j). Which of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i, j)?
A. All elements of L should be initialized to 0 for the values of l(i, j) to be properly computed
B. The values of l(i, j) may be computed in a row major order or column major order of L[M, N]
C. The values of l(i, j) cannot be computed in either row major order or column major order of L[M, N]
D. L[p, q] needs to be computed before L [r, s] if either p < r or q < s
Explaination / Solution:
No Explaination.

Workspace
Report
Q.2
How many 32K × 1 RAM chips are needed to provide a memory capacity of 256 K-bytes =
A. 8
B. 32
C. 64
D. 128
Explaination / Solution:
No Explaination.

Workspace
Report
Q.3
Consider a 4 stage pipeline processor. The number of cycle needed by the four instructions I1,I2,I3,I4 in stages S1, S2, S3, S4 is shown below: What is the number of cycles needed to execute the following loop? for (i=1 to 2) {I1; I2; I3; I4 ;}
A. 16
B. 23
C. 28
D. 30
Explaination / Solution:
No Explaination.

Workspace
Report
Q.4
A multilevel page table is preferred in comparison to a single level page table for translating virtual address to physical address because
A. It reduces the memory access time to read or write a memory location
B. It helps to reduce the size of page table needed to implement the virtual address space of a process
C. It is required by the translation look a side buffer
D. It helps to reduce the number of page faults in page replacement algorithms.
Explaination / Solution:
No Explaination.

Workspace
Report
Q.5
What is the minimum number of gates required to implement the Boolean function (AB + C) if we have to use only 2-input NOR gates?
A. 2
B. 3
C. 4
D. 5
Explaination / Solution:
No Explaination.

Workspace
Report
Q.6
Which one of the following is NOT necessarily a property of a Group?
A. Commutativity
B. Associativity
C. Existence of inverse for every element
D. Existence of identity
Explaination / Solution:
No Explaination.

Workspace
Report
Q.7
Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one the following is TRUE?
A. R is symmetric but NOT antisymmetric.
B. R is NOT symmetric but antisymmetric
C. R is both symmetric and antisymmetric
D. R is neither symmetric nor antisymmetric
Explaination / Solution:
No Explaination.

Workspace
Report
Q.8
(1217)8 is equivalent to
A. (1217)16
B. (028F)16
C. (2297)10
D. (0B17)16
Explaination / Solution:
No Explaination.

Workspace
Report
Q.9
An unbalanced dice (with 6 faces, numbered from 1 to 6) is thrown. The probability that the face value is odd is 90% of the probability that the face value is even. The probability of getting any even numbered face is the same. If the probability that the face is even given that it is greater than 3 is 0.75, which one of the following options is closest to the probability that the face value exceeds 3?
A. 0.453
B. 0.468
C. 0.485
D. 0.492
Explaination / Solution:
No Explaination.

Workspace
Report
Q.10
.For the composition table of a cyclic group shown below Which one of the following choices is correct?
A. a, b are generators
B. b, c are generators
C. c, d are generators
D. d, a are generators