CS GATE 2011 - Online Test

Q1. Which of the following is NOT desired in a good Software Requirement Specifications (SRS) document?
Answer : Option D
Explaination / Solution:
No Explaination.


Q2. The minimum number of D flip-flops needed to design a mod-258 counter is
Answer : Option A
Explaination / Solution:

2≥ 258 ⇒ n = 9 

Q3. The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
Answer : Option A
Explaination / Solution:

Lexical Analysis is implemented by finite automata

Q4. Consider a relational table with a single record for each registered student with the following attributes. 1. Registration_Number: Unique registration number for each registered student 2. UID: Unique Identity number, unique at the national level for each citizen 3. BankAccount_Number: Unique account number at the bank. A student can have multiple accounts or joint accounts. This attributes stores the primary account number 4. Name: Name of the Student 5. Hostel_Room: Room number of the hostel Which of the following options is INCORRECT?
Answer : Option A
Explaination / Solution:

In case two students hold joint account then BankAccount_Num will not uniquely determine other attributes.

Q5. Consider an instruction pipeline with four stages (S1, S2, S3 and S4) each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Delays for the stages and for the pipeline registers are as given in the figure.

What is the approximate speed up of the pipeline in steady state under ideal conditions when compared to the corresponding non-pipeline implementation? 
Answer : Option B
Explaination / Solution:

(5 + 6 + 11 + 8) / (11 + 1) = 30 / 12 = 2.5

Q6. Consider the following recursive C function that takes two arguments 
unsigned int foo unsigned int n, unsigned int r {
if (n > 0) return (n%r) + foo (n / r, r ));
else return 0;
}
What is the return value of the function foo when it is called as foo (513, 2)? 
Answer : Option D
Explaination / Solution:



Q7. An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 : n - 1] is given below.
Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array
Initialize Ln-1 =1
For all i such that 0 ≤ i ≤ n − 2
 
Finally the length of the longest monotonically increasing sequence is max (L0L1,....,Ln-1). Which of the following statements is TRUE?
Answer : Option A
Explaination / Solution:
No Explaination.


Q8. Consider a relational table r with sufficient number of records, having attributes A1, A2,…, An and let 1 ≤ p ≤ n. Two queries Q1 and Q2 are given below.

The database can be configured to do ordered indexing on Ap or hashing on Ap
Which of the following statements is TRUE? 
Answer : Option C
Explaination / Solution:
No Explaination.


Q9. An 8KB direct mapped write-back cache is organized as multiple blocks, each of size 32-bytes. The processor generates 32-bit addresses. The cache controller maintains the tag information for each cache block comprising of the following. 1 Valid bit 1 Modified bit As many bits as the minimum needed to identify the memory block mapped in the cache. What is the total size of memory needed at the cache controller to store metadata (tags) for the cache?
Answer : Option D
Explaination / Solution:


Required answer =256 × (19 + 2) = 5376 bits

Q10. Consider the following recursive C function that takes two arguments 
unsigned int foo unsigned int n, unsigned int r {
if (n > 0) return (n%r) + foo (n / r, r ));
else return 0;
}
What is the return value of the function foo when it is called as foo (345, 10) ?
Answer : Option B
Explaination / Solution: