GATE CSE 2005
Q1.
Consider the following data path of a CPU. ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation - the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR. The instruction "call Rn, sub" is a two word instruction. Assuming that PC is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is Rn < = PC + 1; PC < = M[PC]; The minimum number of CPU clock cycles needed during the execution cycle of this instruction is:Q2.
Consider a three word machine instruction ADD A[R0], @B The first operand (destination) "A[R0]" uses indexed addressing mode with R0 as the index register. The second operand (source) "@B" uses indirect addressing mode. A and B are memory addresses residing at the second and the third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During execution of ADD instruction, the two operands are added and stored in the destination (first operand). The number of memory cycles needed during the execution cycle of the instruction is:Q3.
Match each of the high level language statements given on the left hand side with the most natural Addressing Modes from those listed on the right hand side. 1 A[1] = B[J]; a Indirect addressing 2 while [*A++]; b Indexed, addressing 3 int temp = *x; c AutoincrementQ4.
Consider the following data path of a CPU. ALU, the bus and all the registers in the data path are of identical size. All operations including incrementation of the PC and the GPRs are to be carried out in the ALU. Two clock cycles are needed for memory read operation - the first one for loading address in the MAR and the next one for loading data from the memory bus into the MDR. The instruction "add R0, R1" has the register transfer interpretation R0<=R0+R1. The minimum number of clock cycles needed for execution cycle of this instruction is.Q5.
A program P reads in 500 integers in the range [0,100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?Q7.
Postorder traversal of a given binary search tree, T produces the following sequence of keys 10, 9, 23, 22, 27, 25, 15, 50, 95, 60, 40, 29 Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?Q8.
Consider the following C-function: double foo (int n) { int i; double sum; if (n = = 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo (i); return sum; } } Suppose we modify the above function foo() and store the values of foo (i), 0\leq i \lt n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:Q9.
The Asymptotic Notation of computing the transitive closure of a binary relation on a set of n elements is known to be:Q10.
Consider the following C-function: double foo (int n) { int i; double sum; if (n = = 0) return 1.0; else { sum = 0.0; for (i = 0; i < n; i++) sum += foo (i); return sum; } } The Asymptotic Notation of space complexity of the above function is: