# GATE Numerical Answer Questions

Question 1

**If p,q,r,s are distinct integers such that:**

f (p,q, r,s)=max (p,q, r,s)

g(p,q, r,s)=min(p,q, r,s)

h(p,q, r,s)=remainder of (p*q)/(r *s) if (p*q)> (r *s) or remainder of (r *s) / (p*q)

if (r*s) > (p*q)

Also a function fgh (p,q,r,s) = f(p,q,r,s) × g(p,q,r,s) × h(p,q,r,s)

Also the same operations are valid with two variable functions of the form f(p,q)

What is the value of fg (h(2,5,7,3), 4,6,8)?

f (p,q, r,s)=max (p,q, r,s)

g(p,q, r,s)=min(p,q, r,s)

h(p,q, r,s)=remainder of (p*q)/(r *s) if (p*q)> (r *s) or remainder of (r *s) / (p*q)

if (r*s) > (p*q)

Also a function fgh (p,q,r,s) = f(p,q,r,s) × g(p,q,r,s) × h(p,q,r,s)

Also the same operations are valid with two variable functions of the form f(p,q)

What is the value of fg (h(2,5,7,3), 4,6,8)?

.

Correct answer is =1

Question 2

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

.

Correct answer is =19

Solution :

Let the number of vertices of a binary tree with „p? leaves be n then the tree has

(i) p vertices (i.e., leaves) of degree 1

(ii) one vertex (i.e.., root of T) of degree 2

(iii) 'n - p -1' (i.e., interval) vertices of degree 3

(iv) n -1edges

By Handshaking theorem,

p*1+1*2+(n-p-1)*3=2(n-1)

=> n=2p-1

=39 as p=20

n-p=19 vertices have exactly two children

Question 3

**Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit. Suppose while running a program, it was observed that 80% of the processors read requests result in a cache hit. The average and access time in nanoseconds is _______.**

.

Correct answer is =14

Solution :

Average read access time =[(0.8)(5)+(0.2)(50)] ns.

=4+10 =14ns

Question 4

**With reference to the B+ tree index of order 1 shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query: “Get all records with a search key greater than or equal to 7 and less than 15” is _________**

.

Correct answer is =6

Question 5

**The larger of the two eigenvalues of the matrix is ____________.**

.

Question 6

**The cardinality of the power set of {0, 1, 2,.......10} is _________**

.

Correct answer is =2048

Solution :

cardinality of the power set of {0, 1, 2, … , 10} is 11

^{2}i.e.., 2048

Question 7

**A link has a transmission speed of 106 bits/sec. It uses data packets of size 1000 bytes each. Assume that the acknowledgement has negligible transmission delay, and that its propagation delay is the same as the data propagation delay. Also assume that the processing delays at the nodes are negligible. The efficiency of the stop-and-wait protocol in this setup is exactly 25%. The value of the one-way propagation delay (in milliseconds) is __________**

.

Correct answer is =12

Solution :

Given, B =10

^{6}bps

L=1000 bytes

n=25%

T

_{p}= ?

In stop-and-wait, efficiency = 1/(1+2a)

=> 1/4 = 1/(1+2a) => 1+2a =4

2a=3; a=3/2

T

_{x}= L/B = (8*10

^{3})/10

^{6}=8ms

T

_{p}/t

_{x}= 3/2 ; 2T

_{p}= 3T

_{x}

2T

_{p}=24ms

T

_{p}=12ms

Question 8

**The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence (0,0, 1, 1, 2, 2, 3, 3, 0, 0,…….) is ___________.**

.

Correct answer is =2

Solution :

Here number of distinct states are 4. So, minimum number of flip-flop required is = 2.

Question 9

**A computer system implements a 40-bit virtual address, page size of 8 kilobytes, and a 128- entry translation look-aside buffer (TLB) organized into 32 sets each having four ways. Assume that the TLB tag does not store any process id. The minimum length of the TLB tag in bits is _________.**

.

Correct answer is =22

Solution :

tag =22bit ,set offset=5bit , word offset = 13bit.

Question 10

**Consider the following C function.**

int fun(int n) {

int x=1,k;

if(n==1) return x;

for(k=1;k x=x+fun(k) * fun(n-k);

return xl

}

The return value of fun (5) is _______

int fun(int n) {

int x=1,k;

if(n==1) return x;

for(k=1;k

return xl

}

The return value of fun (5) is _______

.

Correct answer is =51

Question 11

**The number of divisors of 2100 is _______.**

.

Correct answer is =36

Solution :

Let N =2100

2

^{2}* 3*5

^{2}* 7 (i.e.,product of primes)

Then the number of division of 2100 is

(2+1).(1+1)e. 36.(2+1).(1+1) i.e. (3)(2)(3)(2) i.e. 36

Question 12

**Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50*10**

^{6}bytes/sec. if the average seek time of the disk is twice the average rotational delay and the controller?s transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512-byte sector of the disk is _____________..

Correct answer is =6.1

Solution :

60sec -> 15000 rotations

60/15000 = 4ms <- 1 rotation

Average rotational delay = 1/2 *4=2ms

As per question, average seek time= 2* Avg.rotational delay = 2*2 =4ms

Disk transfer time : 1sec ->50 * 10

^{6}=> 0.01ms = 512/(50 *10

^{6}) <- 512 bytes

As per Question, controller?s transfer time is = 10 * 0.01 ms = 0.1ms

Avg time = 4ms +0.1ms+2ms = 6.1ms

Question 13

**The number of min-terms after minimizing the following Boolean expression is _______.**

[D'+AB'+A'C+AC'D+A'C'D]'

[D'+AB'+A'C+AC'D+A'C'D]'

.

Correct answer is =1

Solution :

Given function is F(A,B,C,D) : According to the function k-map is

Question 14

**The number of onto function (surjective function) from set X = {1,2,3,4}to set Y ={a,b,c} is ______.**

.

Correct answer is =36

Question 15

**The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0+1)**

^{*}(10 ) is _________________.

Correct answer is =3

Solution :

(0+1)

^{*}(10 )

Question 16

**A computer system implements 8 kilobyte pages and a +32-bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the translation. If the maximum size of the page table of a process is 24 megabytes, the length of the virtual address supported by the system is _________ bits.**

.

Correct answer is =36

Solution :

Given Page size = 8kb

PAS = 32 – bit

No.of frames 2 frames=PAS/PS = 2

^{32}/2

^{13}= 2

^{19}frames

So, it is given that each page table entry contains a valid bit, a dirty bit, 3 permission bits. =>5 bits are reserved.

It means one entry requires 19 + 5 = 24 bits

Page Table size = n × e

24*2

^{20}*3 = n*24

n=(24*2

^{20}*8)/24 = 2

^{23}pages.

Length of the virtual address = 23+13=36 bits

Question 17

**A young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞ , and hence there cannot be any entry to the right of , or below a ∞ . The following Young tableau consists of unique entries.**

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞ ). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is _________

1 | 2 | 5 | 14 |

3 | 4 | 6 | 23 |

10 | 12 | 18 | 25 |

31 | ∞ | ∞ | ∞ |

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled in with a ∞ ). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is _________

.

Correct answer is =5

Question 18

**A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is 1.2 microseconds. A 4-bit ripple-carry binary adder is implemented by using four full adders. The total propagation time of this 4-bit binary adder in microseconds is ____________.**

.

Correct answer is =19.2

Solution :

Here sum and carry delay is same= 4.8 ?sec

so T

_{total}= ( 4 * 4.8 ) micro sec

= 19.2 micro sec

Question 19

**Consider the sequence of machine instruction given below:**

MUL R5,R0,R1

DIV R6,R2,R3

ADD R7,R5,R6

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 __________

MUL R5,R0,R1

DIV R6,R2,R3

ADD R7,R5,R6

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 __________

.

Correct answer is =13

Solution :

I=> Instruction fetch

O=>Operand Fetch

P=>Perform operation

W = >write back the result

Question 20

**Perform the following operations on the matrix**

(i) Add the third row to the second row

(ii) Subtract the third column from the first column.

The determinant of the resultant matrix is __________.

(i) Add the third row to the second row

(ii) Subtract the third column from the first column.

The determinant of the resultant matrix is __________.

.

Correct answer is =0

Solution :

Determinant is unaltered by the operations (i) and (ii)

=> Determinant of the resultant matrix = Determinant of the given matrix

Question 21

**Let X and Y denote the sets containing 2and 20 distinct objects respectively and F denote the set of all possible functions defined from X to Y. let f be randomly chosen from F .The probability of f being one-to-one is _______.**

.

Correct answer is =0.95

Solution :

|X| =2 , |Y| =20

Number of functions from X to Y is 20

^{2}i.e., 400 and number of one-one functions from X to Y is 20P2 i.e 20 * 19 =380

Probability of a function f being one-one is 380/400 = 0.95

Question 22

**Consider the C program below.**

#include

Int *A, stkTop;

Int stkFunc (int opcode, int val)

{

Static int size =0, stkTop=0;

Switch (opcode) {

Case -1 : Size = val; break;

Case 0 : if (stkTop < size) A (stktop++] = val; break;

Default : if (stktop) return A [--stkTop];

}

return -1; }

int main ( )

{

int B[20] ; A = B; stkTop = -1;

stkFunc (-1, 10);

stkFunc (0, 5);

stkFunc (0, 10);

printf (“%d\n”, stkFunc(1, 0) + stkfunc(1, 0);

}

The value printed by the above program is _____________.

#include

Int *A, stkTop;

Int stkFunc (int opcode, int val)

{

Static int size =0, stkTop=0;

Switch (opcode) {

Case -1 : Size = val; break;

Case 0 : if (stkTop < size) A (stktop++] = val; break;

Default : if (stktop) return A [--stkTop];

}

return -1; }

int main ( )

{

int B[20] ; A = B; stkTop = -1;

stkFunc (-1, 10);

stkFunc (0, 5);

stkFunc (0, 10);

printf (“%d\n”, stkFunc(1, 0) + stkfunc(1, 0);

}

The value printed by the above program is _____________.

.

Correct answer is =-2

Solution :

StkFunc(1,0) returns -1 both the times. So – 2 will be printed

**MY REPORT**

TOTAL = 22 | |||

ANSWERED = | |||

CORRECT / TOTAL = | /22 | ||

POSITIVE SCORE = | |||

NEGATIVE SCORE = | |||

FINAL SCORE = |