xxxviii | GATE 2017 Solved Paper CS: Set – 2

(C) Relationship R is many-to-one and the participa- 〈3, 8〉 from table T1, the number of additional records that
tion of A in R is total. need to be deleted from table T1 is __________.
(D) Relationship R is many-to-one and the participa- Solution: Based on given description, S is depend on P; Q
tion of A in R is partial. is depend on R.
Solution: After deleting row (3, 8) from T1, set S = NULL at R = 8
in T2.
A m R I B
∴ zero rows will get deleted in T1, other than (3, 8).
Hence, the correct answer is (0).
The relationship R table can be merged with entity A’s table.
If R is many-to-one and A is total Participated in relation Question Number: 20 Question Type: NAT
R. The maximum number of IPv4 router addresses that can be
listed in the record route (RR) option field of an IPv4 header
Hence, the correct option is (C).
is__________.
Question Number: 18 Question Type: MCQ
Solution: In IPV4, maximum number of router addresses
Consider socket API on a Linux machine that supports con- specified will be 9.
nected UDP sockets. A connected UDP socket is a UDP
socket on which connect function has already been called. Hence, the correct answer is (9).
Winch of the following statements is/are CORRECT? Question Number: 21 Question Type: NAT
I. A connected UDP socket can be used to communicate Consider the set X = {a,b,c,d,e} under the partial ordering
with multiple peers simultaneously.
R = {(a, a).(a, b). (a, c), (a, d). (a, e),(b, b), (b, c), (b, e), (c,
II. A process can successfully call connect function again
c). (c, e), (d, d), (d, e), (e, e)}.
for an already connected UDP socket.
(A) I only The Hasse diagram of the partial order (X, R) is shown
(B) II only below.
(C) Both I and II e
(D) Neither I nor II
Solution: A process can use Connection function on a
UDP socket, if the communication is point to point.
Connected UDP simulates like TCP connection (like peer c
to peer connection)
Hence, the correct option is (B).
d
Question Number: 19 Question Type: NAT
Consider the following tables T1 and T2.
b
T1 T2
P Q R S

2 2 2 2
a
3 8 8 3 The minimum number of ordered pairs that need to be
7 3 3 2 added to R to make (X, R) a lattice is __________.
5 8 9 7 Solution: Given poset (X, R) is itself a lattice.
6 9 5 7 So, the minimum number of ordered pairs to be added = 0.

8 5 7 2
Hence, the correct answer is (0).

9 8 Question Number: 22 Question Type: NAT

 1 1 −1 −1 −2 −1
   
In table T1, P is the primary key and Q is the foreign key Let P =  2 −3 4  and Q =  6 12 6  be two
referencing R in table T2 with on-delete cascade and on-    
 3 −2 3   5 10 5 
update cascade. In table T2, R is the primary key and S is    
matrices.
the foreign key referencing P in table Tl with on-delete set
Then the rank of P + Q is __________.
NULL and on-update cascade. In order to delete record
 GATE 2017 Solved Paper CS: Set – 2 | xxxix

 1 1 −1 −1 −2 −1 Question Number: 25 Question Type: NAT

   
Solution: Let P =  2 −3 4  and Q =  6 12 6  The minimum possible number of states of a deterministic
 
 3 −2 3   5 10 5  finite automaton that accepts the regular
   
language L = {w1aw2| w1, w2 ∈ {a, b}*, |w1| = 2, |w2| ≥ 3} is
 0 −1 −2  __________.
 
∴ P + Q = 8 9 10 
  Sulution: Given language
8 8 8 
 
L = {w1aw2 | w1, w2 ∈ {a, b}*,
0 −1 −2 |w1| = 2
Det ( P + Q ) = 8 9 10 = 0 |w2| ≥ 3}
8 8 8 The minimum DFA for L can be
 0 −1 a,b
and determinant of a 2 × 2 sub-matrix   of P + Q is
8 9 
8 ≠ 0.  
a,b a,b a b Dead
∴ Rank of P + Q = 2 siale

Hence, the correct answer is (2). a,b

Question Number: 23 Question Type: NAT

G is an undirected graph with n vertices and 25 edges such
that each vertex of G has degree at least 3. Then the maxi- a,b
mum possible value of n is __________.
Solution: Number of edges of G = n (E) = 25
Given number of vertices of G = n (V) = n a,b

As the degree of each vertex is atleast 3, we have sum of the

degrees of all the vertices will be of the form 3n + k, where
k is a positive integer.
∴ Minimal DFA which accepts L has 8 states. (Including
We know that, sum of the degrees of all the vertices = 2 ×
dead state)
Number of edges
Hence, the correct answer is (8).
⇒ 3 n + k = 2 × 25
⇒ 3 n + k = 50 Question Number: 26 Question Type: MCQ
For, n to be maximum, k should be minimum. P and Q are considering to apply for a job. The probability
1
∴ 3 n + k = 50 and k is minimum only when n = 16. that P applies for the job is , the probability that P applies
4
1
Hence, the correct answer is (16). for the job given that Q applies for the job is and the
2
probability that Q applies for the job given that P applies for
Question Number: 24 Question Type: NAT
1
Consider a quadratic equation x − 13x + 36 = 0 with coeffi-
2 the job is . Then the probability that P does not apply for
3
cients in a base b. The solutions of this equation in the same the job given that Q does not apply for the job is
base b are x = 5 and x = 6. Then b = __________.
4 5
(A) (B)
Solution: 5 6
x2 − 13x +36 = 0 7 11
(C) (D)
5.6 = (36)b 8 12
30 = 3b + 6
Solution: Let A and B denote the events of the persons P
3b = 24
and Q applying for a job respectively.
b=8
1  A 1  B 1
∴ base = 8 ∴ P ( A) = , P   = and P   =

4  B 2  A  3
Hence, the correct answer is (8.0 to 8.0).