PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2018

56 Consider the minterm list form of a Boolean function F given below.

F(P, Q, R, S) = Σm(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)

Here, m denotes a minterm and d denotes a don’t care term. The number of essential prime implicants of the function F is ______ .

Note: Numerical Type question.

F(P, Q, R, S) = Σm(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)

Number of EPI = 3

57 The instruction pipeline of a RISC processor has the following stages. Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. assume that there are no data hazards and no control hazards. The number of clock cycles required for completion of execution of the sequence of instructions is ____________.

Note – Numerical Type question

Given, total number of instructions (n) = 100
Number of stages (k) = 5
Since, if n instructions take c cycle, so (c-1) stalls will occur for these instructions.
Therefore, the number of clock cycles required = Total number of cycles required in general case + Extra cycles required (here, in PO stage)
= (n + k – 1) + Extra cycles
= (100 + 5 -1) + 40*(3-1)+35*(2-1)+20*(1-1)
= (100 + 4) + 40*2+35*1+20*0
= 104 + 115
= 219 cycles

58 Let G be a graph with 100! Vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G and z denote the number of connected components in G.
Then, y + 10z = _________.

Note – Numerical Type question

The graph has 100! Vertices which each vertex labeled by one of the 100! Permutation.
take a vertex whose labeling is say 1,2,3,4, …..,100.
Now it will be connected to all vertices where exactly 2 of the adjacent numbers all swapped.
The two swapped numbers could be (1, 2), (2, 3), (3, 4) …. etc. upto (99, 100) which makes for 99 edges for each such vertex.
So the graph is a regular graph with each vertex connected to 99 other vertices.
So y = 99
The number of connected components = z = 1 since we can go from any vertex to any other vertex by only swapping 2 adjacent number at a time, many times i.e. there is a path from any vertex to any other vertex.
Graph is connected.
So z = 1
So y + 10z = 99 + 10 x 1 = 109

59 Given a language L, define Lⁱ as follows:

L⁰ = {ε}

Lⁱ = L^i-1∙L for all i>0
The order of a language L is defined as the smallest k such that L^k=L^k+1. Consider the language L₁ (over alphabet 0) accepted by the following automaton.

The order of is ___________.

Note – Numerical Type question

We need to find smallest value of k which satisfies
L₁^k = L₁^k+1

L₁ = ε + (00)
Try k = 0; L₁⁰ = L₁¹
ε = L₁ which is false.
So order is not 0.
Try k = 1: L₁¹ = L₁²
L₁² = L₁ Now, L₁² =(ε + 0(00)*)(ε + 0(00)*)
= ε + 0(00)* + 00(00)* = 0*
Clearly L₁² ≠ L₁
So order is not 1.
Try k = 2: L₁² = L₁³
Now, L₁³ = L₁².L₁
= 0*(ε + 0(00)*) = 0*
Clearly L₁³ = L₁²=0*
(so, order of L₁ is 2)

60 The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _______.

Note – Numerical Type question

T(N) =(N-1)Ck * T(k) * T(N-k-1), where k = number of nodes on left subtree
T(1) = 1
T(2) = 1
T(3) = 2
T(4) = 3C2 * T(2) * T(1) = 3
T(5) = 4C3 * T(3) * T(1) = 8
T(6) = 5C3 * T(3) * T(2) = 20
T(7) = 5C3 * T(3) * T(3) = 80

PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2018

Follow Us :