1
Numerical

### GATE CSE 2015 Set 2

Consider the sequence of machine instructions given below:

MUL R5, R0, R1
DIV R6, R2, R3
SUB R8, R7, R4

In the above sequence, $R0$ to $R8$ are general purpose registers. In the instructions shown, the first register stores the result of the operation performed on the second and the third registers. This sequence of instructions is to be executed in a pipelined instruction processor with the following $4$ stages: $(1)$ Instruction Fetch and Decode $(IF), (2)$ Operand Fetch $(OF), (3)$ Perform Operation $(PO)$ and $(4)$ Write back the result $(WB).$ The $IF,$ $OF$ and $WB$ stages take $1$ clock cycle each for any instruction. The $PO$ stage takes $1$ clock cycle for $ADD$ or $SUB$ instruction, $3$ clock cycles for $MUL$ instruction and $5$ clock cycles for $DIV$ instruction. The pipelined processor uses operand forwarding from the $PO$ stage to the $OF$ stage. The number of clock cycles taken for the execution of the above sequence of instructions is _______________________ .

2

### GATE CSE 2015 Set 2

Consider a processor with byte-addressable memory. Assume that all registers, including Program Counter $(PC)$ and Program Status Word $(PSW),$ are of size $2$ bytes. A stack in the main memory is implemented from memory location ${\left( {0100} \right)_{16}}$ and it grows upward. The stack pointer $(SP)$ points to the top element of the stack. The current value of $SP$ is ${\left( {016E} \right)_{16}}$. The CALL instruction is of two words, the first word is the op-code and the second word is the starting address of the subroutine (one word $= 2$ bytes). The CALL instruction is implemented as follows:

$\bullet \,\,\,\,\,\,\,\,$ Store the current value of $PC$ in the stack
$\bullet \,\,\,\,\,\,\,\,$ Store the value of $PSW$ register in the stack
$\bullet \,\,\,\,\,\,\,\,$ Load the starting address of the subroutine in $PC$

The content of $PC$ just before the fetch of a CALL instruction is $\left( {5FA0} \right){\,_{16}}.$ After execution of the CALL instruction, the value of the stack pointer is

A
$\left( {016A} \right){\,_{16}}$
B
$\left( {016C} \right){\,_{16}}$
C
$\left( {0170} \right){\,_{16}}$
D
$\left( {0172} \right){\,_{16}}$
3

### GATE CSE 2015 Set 2

Consider a complete binary tree where the left and the right sub-trees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
A
$\Omega \left( {\log \,\,n} \right)$
B
$\Omega \left( n \right)$
C
$\Omega \left( {n\,\,\log \,\,n} \right)$
D
$\Omega \left( {{n^2}} \right)$
4
Numerical

### GATE CSE 2015 Set 2

A binary tree $T$ has $20$ leaves. The number of nodes in $T$ having two children is _______________.

### Paper Analysis of GATE CSE 2015 Set 2

Subject NameTotal Questions
Algorithms5
Compiler Design3
Computer Networks6
Computer Organization4
Data Structures3
Database Management System4
Digital Logic3
Discrete Mathematics12
Operating Systems4
Programming Languages3
Software Engineering3
Theory of Computation4
Web Technologies1