GATE Solved Paper 2017-19 - GATE 2018

51. Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops.


The number of states in the state transition diagram of the circuit that have a transition back to the same state on some value of “in” is __________.

Note – Numerical Type question

  • Option : A
  • Explanation :

    State Table:
    P.SInputFF inputN.S 
    Q1Q0xD1 = xD1 = Q1Q1Q0Out = Q0
    00000000
    00110100
    01000000
    01110100
    10001011
    10111111
    11001011
    11111111
    State Transition Diagram:

    self-loop states are 00 and 11.
    Hence answer is 2.
Cancel reply
Cancel reply

54. A processor has 16 integer registers (R0, R1, …… R15) and 64 floating point registers (F0, F1, ……, F63). It uses a 2-byte instruction format. There are four categories of instructions. Type-1, Type-2, Type-3 and Type-Type-1 category consists of four instructions, each with 3 integer register operands (3Rs). Type-2 category consists of eight instructions, each with 2 floating point register operands (2Fs). Type-3 category consists of fourteen instructions, each with one integer register operand and one floating point register operand (1R + 1F). Type-4 category consists of N instructions, each with a floating point register operand (1F). The maximum value of N is _________.

  • Option : A
  • Explanation :
    Given, size of instruction format is 2 byte (= 16 bits), therefore number of instruction encoding = 216
    Also, total number of bits in integer operand = log2(16 integer registers) = 4
    Total number of bits in floating point operand = log2(64 floating point registers) = 6
    So, number of encoding consumed:

    By type 1 instructions = 4×23×4 = 214
    By type 2 instructions = 8×22×6 = 215
    By type 3 instructions = 14×2(4+6) = 14336

    Now, number of encoding left for type 4 instructions = 216 − (214 + 215 + 14336) = 2048
    Therefore, total number of different instructions of type 4 instructions = 2048 /64 = 32 Please note that there is difference between number of different instructions and number of different encoding, a single instruction can have different encodings when the address part differs. So, answer is 32.
Cancel reply
Cancel reply

55. Consider the following undirected graph G:

Choose a value of x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ___________.

Note – Numerical Type question

  • Option : A
  • Explanation :
    ü Edges with weights 1 and 3 will be selected first,
    ü Now bottom edge with weight 4 will not be selected as will cause cycle on MST,
    ü both corner vertices have two-two choices to select the vertices, so these corner edges with weights 4 and 5 will resultant 2*2 = 4 MSTs.
    So, total number of MSTs are 2*2 = 4, which is answer.
    Option (A) is correct.
Cancel reply
Cancel reply