1

### 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}}$
2

### 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)$
3
Numerical

### GATE CSE 2015 Set 2

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

4

### GATE CSE 2015 Set 2

Which one of the following hash functions on integers will distribute keys most uniformly over $10$ buckets numbered $0$ to $9$ for $𝑖$ ranging from $0$ to $2020$?
A
$h\left( i \right) = {i^2}\,mod\,\,10$
B
$h\left( i \right) = {i^3}\,mod\,\,10$
C
$h\left( i \right) = \left( {11 * {i^2}} \right)\,\bmod \,10$
D
$h\left( i \right) = \left( {12 * i} \right)\,\bmod \,10$

### 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