xxxvi | GATE 2017 Solved Paper CS: Set – 2
2 16 2 (C) (¬ p ∧ r) ∨ ((p ∧ q) → ¬ r)
(A) and (B) and 0
p p p (D) (¬ p ∧ r) ∨ ( r → (p ∧ q))
4 4 16 Solution: Given statements are
(C) and 0 (D) and
p p p p: It is raining
q: It is cold
πx
Solution: Given f ( x ) = R sin + S r: It is pleasant
2
1 Given compound statement is
1 2R
f ′ = 2 and ∫ f ( x ) dx = “It is not raining and it is pleasant, and it is not pleasant,
2 π
0
only if it is raining and it is cold”.
π π
f 1 ( x) = R cos x is same as,
2 2
“It is not raining and it is pleasant, and if it is not pleasant
1 π π 1 then it is raining and it is cold”.
f = 2 ⇒ R cos × = 2
1
2 2 2 2 Which can be written in symbolic form as (¬p ∧ r) ∧
π π (¬r → (p ∧ q))
⇒ R cos = 2
2 4 Hence, the correct option is (A).
π 1 Question Number: 12 Question Type: MCQ
⇒ R. = 2
2 2 Given the following binary number in 32-bit (single preci-
4 sion) IEEE-754 format:
⇒ R=
π 00111110011011010000000000000000
1
2R The decimal value closest to this floating-point number is
Also, ∫ f ( x ) dx = (A) 1.45 × 101 (B) 1.45 × 10−1
π
0
(C) 2.27 × 10 −1
(D) 2.27 × 101
4
2
1
π π Solution: Given 32-bit IEEE 754 number is
⇒ ∫ R sin x + S dx =
0
2 π 0 0111110 0 11011010000000000000000
1
4 π 8 Sign-bit = 0 ⇒ number is positive
⇒ ∫ π sin 2 x + S dx = π 2
Biased exponent = 22 + 23 + 24 +25 + 26
0
1
=124
π
− cos x ∴ Exponent = 124−127 = −3
4 2 8
⇒ + Sx = 2 Mantissa = 1.1101101
π π π
∴ Number in binary
2
0 = 1.1101101 × 2−3
−8 π −8 8 = 0.0011101101
⇒ 2 cos + S − 2 cos 0 + S × 0 = 2
π 2 π π = 0.2314453125
8 8 ≃ 2.3 × 10−1
⇒ S+ 2 = 2
π π This is approximately equal to choice (C).
⇒S=0
Hence, the correct option is (C).
4
∴ R = and S = 0 Question Number: 13 Question Type: MCQ
π
Hence, the correct option is (C). A circular queue has been implemented using a singly
linked list where each node consists of a value and a single
Question Number: 11 Question Type: MCQ pointer pointing to the next node. We maintain exactly two
Let p. q. r denote the statements “It is raining”, “It is cold”, external pointers FRONT and REAR pointing to the front
and “It is pleasant”, respectively. Then the statement “It is node and the rear node of the queue, respectively. Which of
not raining and it is pleasant, and it is not pleasant only if it the following statements is/are CORRECT for such a circu-
is raining and it is cold” is represented by lar queue, so that insertion and deletion operations can be
(A) (¬ p ∧ r) ∧ (¬ r → (p ∧ q)) performed in O (1) time?
(B) (¬ p ∧ r) ∧ ((p ∧ q) → ¬ r)
GATE 2017 Solved Paper CS: Set – 2 | xxxvii
I. Next pointer of front node points to the rear node. (A) MNOPQR
II. Next pointer of rear node points to the front node. (B) NQMPOR
(A) I only (B) II only (C) QMNROP
(C) Both I and II (D) Neither I nor II (D) POQNMR
Solution: Circular Queue with Linked List: Solution: Given graph
M N O
a b c
FRONT REAR
In above, implementation of circular queue using linked list,
Rear pointer always points Front as it is done always for
every new insertion.
R Q P
FRONT node next pointer points to REAR only when they
are only 2 elements in a queue. Insertion and Deletion can In BFS traversal, it first traverse all the neighbours of start
be done in O(1) time. node and traverse corresponding neighbours iteratively till
Hence, the correct option is (B). all the nodes are visited. Option (D) is the correct BFS tra-
versal of above graph ‘G’.
Question Number: 14 Question Type: MCQ
Hence, the correct option is (D).
Consider the following function implemented in C:
Question Number: 16 Question Type: MCQ
void printxy (int x, int y) {
Identify the language generated by the following grammar,
int ptr;
where S is the start variable.
x = 0;
ptr = &x; S → XY
y = ptr; X → aX|a
ptr = 1; Y → aYb|∈
printf (“%d, %d” x, y);
(A) {ambn| m ≥ n, n > 0} (B) {ambn| m ≥ n, n ≥ 0}
}
(C) {ambn| m >n, n ≥ 0} (D) {ambn| m > n, n > 0}
The output of invoking printxy (1, 1) is
(A) 0, 0 (B) 0, 1 Solution: Given grammar
(C) 1, 0 (D) 1, 1 S → XY
X →aX | a
Solution: x 1 01 y 1 0
Y → aYb | ε
ptr For given grammar, there need to atleast one a. There can
y = *ptr ⇒ y = 0 be zero b’s.
when * ptr = 1 ⇒ only value of x will change, i.e., 1 n≥0
when x and y are printed, it prints 1, 0. Y generals equal number of a’s, and b’s.
Hence, the correct option is (C). X generates one or more a’s so S generates
Question Number: 15 Question Type: MCQ {am bn | m > n, n ≥ 0}
The Breadth First Search (BFS) algorithm has been imple- Hence, the correct option is (C).
mented using the queue data structure. Which one of the
following is a possible order of visiting the nodes in the Question Number: 17 Question Type: MCQ
graph below? An ER model of a database consists of entity types A and
B. These are connected by a relationship R which does not
M N O have its own attribute, Under which one of the following
conditions, can the relational table for R be merged with
that of A?
(A) Relationship R is one-to-many and the participa-
tion of A in R is total.
(B) Relationship R is one-to-many and the participa-
R Q P tion of A in R is partial.
