PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2019

56 Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ___________.

Note – Numerical Type question

No. of pairs with path length 0=8.0=8.
No. of pairs with path length 1=0.1=0.
No. of pairs with path length 2=8.2=8.
No. of pairs with path length 3=0.3=0.
No. of pairs with path length 4=16.4=16.
No. of pairs with path length 5=0.5=0.
No. of pairs with path length 6=32.6=32.
Total number of possible pairs =8×8=64=8×8=64
So, expected path length,E(x),
=0×864+2×864+4×1664+6×3264=27264=4.25

57 Suppose Y is distributed uniformly in the open interval (1, 6). The probability that the polynomial 3x² + 6xy + 3Y + 6 has only real roots is (rounded off to 1 decimal place) ________.

Note – Numerical Type question

It is given that, Polynomial 3x² + 6xY + 3Y + 6 has only real roots
b² – 4ax ≥ 0
(6Y)² – 4(3) (3Y+ 6) ≥ 0
Y² – Y - 2 ≥ 0<
>Y ∈ (–∞, – 1] ∩ [2, ∞)
⇒ Y ∈ [2, 6)
Since y is uniformly distributed in (1, 6)
Probability distributed function,
Gate2019 cs

58 Let Σ be the set of all bijections from {1,…,5} to {1,…,5}, where 𝑖𝑑 denotes the identity function, i.e. id(j) =j,∀j. Let ∘ denote composition on functions. For a string 𝑥 = 𝑥₁ 𝑥₂ ⋯ 𝑥_n ∈ Σsup>1, 𝑛 ≥ 0, let (𝑥) = 𝑥₁ ∘ 𝑥₂ ∘ ⋯ ∘ 𝑥_n.
Consider the language 𝐿 = {𝑥 ∈ Σ∗| (𝑥) = 𝑖𝑑}. The minimum number of states in any DFA accepting L is _________.

Note – Numerical Type question

The DFA for accepting L will have 5! = 120 states, since we need one state for every possible permutation function on 5 elements. The starting state will be “id” state, named as Gate2017 cs

and from there
n! arrows will go the n! states each named with a distinct permutation of the set {1, 2, 3, 4, 5}. Since composition of permutation function is closed every arrow has to go to some permutation and hence some state.
Since the language only has those strings where π(x) = id only the starting state (“id” state) will be the final state. Sample machine with only 2 states is shown below
Gate2017 cs

59 Consider that 15 machines need to be connected in a LAN using 8-port Ethernet switches. Assume that these switches do not have any separate uplink ports. The minimum number of switches needed is__________.

Note – Numerical Type question

If a switch has 8 ports then it means it can connect maximum 8 host. and 2 switch can connect 16 hosts independently. but we need one port for both of them to connect with each other. so now one- one port is used from both the switches for connecting then total port available free on both the switch is 7. so maximum 14 host can be connected but for the 15th host we need another switch.
3 switches of ethernet are required to connect 15 computers.
Hence, 3 is correct answer.

60 What is the minimum number of 2-input NOR gates required to implement a 4-variable function expressed in sum-of-minterms form as f = Σ (0, 2, 5, 7, 8, 10, 13, 15)? Assume that all the inputs and their complements are available.

Note – Numerical Type question

f = Σ_m(0, 2, 5, 7, 8, 10, 13, 15)
f = Π_M(1, 3, 4, 6, 9, 11, 12, 14)
Gate 2019cs

f can be implemented using 3 NOR gates.
So, option (A) is correct

Roll_no.	Student_name
1	Amit
2	Priya
3	Vinit
4	Rohan
5	Smita

Roll_no	Subject_code	Marks
1	A	86
1	B	95
1	C	90
2	A	89
2	C	92
3	C	80

PREVIOUS YEAR SOLVED PAPERS MCQ - GATE 2019

Follow Us :