## GATE 2017 [Set-2]

 Question 1

The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is

 A 136251 B 736251 C 571247 D 136252
Digital-Logic-Design       Number-Systems       Video-Explanation
Question 1 Explanation:
X = (BCA9)16
Each hexadecimal digit is equal to a 4-bit binary number. So convert
X = (BCA9)16 to binary Divide the binary data into groups 3 bits each because each octal digit is represented by 3-bit binary number.
X = (001 011 110 010 101 001)2
Note: Two zeroes added at host significant position to make number bits of a multiple of 3 (16 + 2 = 18)
X = (136251)8
 Question 2

Match the following: A P→(ii), Q→(iv), R→(i), S→(iii) B P→(ii), Q→(i), R→(iv), S→(iii) C P→(ii), Q→(iv), R→(iii), S→(i) D P→(iii), Q→(iv), R→(i), S→(ii)
Programming       Match-the-Following       Video-Explanation
Question 2 Explanation:
Static char var:
⇾ A variable located in Data Section of memory P→(ii), Q→(iv), R→(i), S→(iii)
 Question 3

Match the algorithms with their time complexities:

```      Algorithm                                     Time complexity
(P) Towers of Hanoi with n disks                       (i) Θ(n2)
(Q) Binary search given n stored numbers              (ii) Θ(n log⁡ n)
(R) Heap sort given n numbers at the worst case      (iii) Θ(2n)
(S) Addition of two n×n matrices                      (iv) Θ(log⁡ n)
```
 A P→(iii), Q→(iv), R→(i), S→(ii) B P→(iv), Q→(iii), R→(i), S→(ii) C P→(iii), Q→(iv), R→(ii), S→(i) D P→(iv), Q→(iii), R→(ii), S→(i)
Algorithms       Match-the-Following       Video-Explanation
Question 3 Explanation:
In this problem, we have to find Average case of different algorithms
→ Tower of Hanoi with n disks takes θ(2n) time
It is a mathematical game or puzzle.
It consists of three rods and a number of disks of different sizes, which can slide onto any rod.
The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
3. No disk may be placed on top of a smaller disk.
With 3 disks, the puzzle can be solved in 7 moves.
The minimal number of moves required to solve a Tower of Hanoi puzzle is 2n-1, where n is the number of disks.
→ Binary Search given n sorted numbers takes Ɵ(log2 n)
→ Heap sort given n numbers of the worst case takes Ɵ(n log n)
→ Addition of two n×n matrices takes Ɵ(n2)
 Question 4

Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? A I, II and IV only B I and III only C II and IV only D I only
Theory-of-Computation       Context-Free-Language       Video-Explanation
Question 4 Explanation:
Since CFL is closed under UNION so L1 ∪ L2 is CFL, is a true statement.
CFL is not closed under complementation.
So L1 compliment may or may not be CFL. Hence is Context free, is a false statement.
L1 – R means and Regular language is closed under compliment, so is also a regular language, so we have now L1 ∩ R .
Regular language is closed with intersection with any language, i.e. L∩R is same type as L.
So L1∩R is context free.
CFL is not closed under INTERSECTION, so L1 ∩ L2 may or may not be CFL and hence IVth is false.
 Question 5

Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: A P→(ii), Q→(iii), R→(iv), S→(i) B P→(ii), Q→(i), R→(iii), S→(iv) C P→(iii), Q→(iv), R→(i), S→(ii) D P→(i), Q→(iv), R→(ii), S→(iii)
Compiler-Design       Compilers       Video-Explanation
Question 5 Explanation:
Character stream is input to lexical analyzer which produces tokens as output. So Q → (iv).
Token stream is forwarded as input to Syntax analyzer which produces syntax tree as output. So, S → (ii).
Syntax tree is the input for the semantic analyzer, So P → (iii).
Intermediate representation is input for Code generator. So R → (i).
 Question 6

Which of the following statements about parser is/are CORRECT?

I. Canonical LR is more powerful than SLR.

II. SLR is more powerful than LALR.

III. SLR is more powerful than Canonical LR.

 A I only B II only C III only D II and III only
Compiler-Design       Parsers       Video-Explanation
Question 6 Explanation:
Canonical LR is more powerful than SLR as every grammar which can be parsed by SLR parser, can also be parsed by CLR parser.
The power in increasing order is:
LR(0) < SLR < LALR < CLR
Hence only I is true.
 Question 7

Which of the following is/are shared by all the threads in a process?

I. Program counter

II. Stack

IV. Registers

 A I and II only B III only C IV only D III and IV only
Question 7 Explanation:
A process, in the simplest terms, is an executing program.
One or more threads run in the context of the process.
A thread is the basic unit to which the operating system allocates processor time.
A thread can execute any part of the process code, including parts currently being executed by another thread.
Each thread has its own stack, register and PC.
So here address space that is shared by all thread for a single process.
 Question 8

In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed?

I. Contiguous

III. Indexed

 A I and III only B II only C III only D II and III only
Operating-Systems       File-Allocation-Methods       Video-Explanation
Question 8 Explanation:
→ Contiguous Allocation:
i) Both sequential and direct access is possible.
ii) Extremely fast.
i) Suffers from both internal and external fragmentation.
ii) Increasing file size is difficult, because it depends on the availability of contiguous memory at a particular instance.
i) Flexible in terms of size.
ii) Does not suffers from external fragmentation.
i) Allocation is slower.
ii) Does not support random or direct access.
iii) Pointers require some extra overhead.
→ Indexed allocation:
i) Support direct access, so provides fast access to the file blocks.
ii) No external fragmentation.
i) The pointer overhead for indexed allocation is greater than linked allocation.
ii) Inefficient in terms of memory utilization.
 Question 9

Consider the following statements about the routing protocols, Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) in an IPv4 network.

• I: RIP uses distance vector routing
• II: RIP packets are sent using UDP
• III: OSPF packets are sent using TCP
IV: OSPF operation is based on link-state routing

Which of the statements above are CORRECT?

 A I and IV only B I, II and III only C I, II and IV only D II, III and IV only
Computer-Networks       Routing       Video-Explanation
Question 9 Explanation:
I: RIP uses distance vector routing. “TRUE”
RIP is one of the oldest DVR protocol which employ the hop count as a routing metric.
II: RIP packets are sent using UDP. “TRUE”
RIP uses the UDP as its transport protocol, and is assigned the reserved port no 520.
III: OSPF packets are sent using TCP. “FASLE”
OSPF encapsulates its data directly into IP Packets and does not use either TCP or UDP.
IV: OSPF operation is based on link state routing. “TRUE”
OSPF is a routing protocol which uses link state routing (LSR) and works within a single autonomous system.
 Question 10

If f(x) = Rsin(πx/2) + S, f'(1/2) = √2 and , then the constants R and S are, respectively.

 A B C D Engineering-Mathematics       Calculus       Video-Explanation
Question 10 Explanation:  Question 11

Let p, q, r denote the statements “It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by

 A (¬p ∧ r) ∧ (¬r → (p ∧ q)) B (¬p ∧ r) ∧ ((p ∧ q) → ¬r) C (¬p ∧ r) ∨ ((p ∧ q) → ¬r) D (¬p ∧ r) ∨ (r → (p ∧ q))
Engineering-Mathematics       Prepositional-Logic       Video-Explanation
Question 11 Explanation:
p: It is raining
q: It is cold
r: It is pleasant
“If it is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold.”
We can divide the statement into two parts with “Conjunction”. i.e., ¬r→(p∧q) ⇾(2)
From (1) & (2), the given statement can be represented as Question 12

Given the following binary number in 32-bit (single precision) IEEE-754 format:

00111110011011010000000000000000

The decimal value closest to this floating-point number is

 A 1.45 × 101 B 1.45 × 10-1 C 2.27 × 10-1 D 2.27 × 101
Digital-Logic-Design       Number-Systems       Video-Explanation
Question 12 Explanation: For single-precision floating-point representation decimal value is equal to (-1)5 × 1.M × 2(E-127)
S = 0
E = (01111100)2 = (124).
So E – 127 = - 3
1.M = 1.11011010…0
= 20 + 2(-1) + 2(-1) + 2(-4) + 2(-5) + 2(-7)
= 1+0.5+0.25+0.06+0.03+0.007
≈ 1.847
(-1)5 × 1.M × 2(E-127)
= -10 × 1.847 × 2-3
≈ 0.231
≈ 2.3 × 10-1
 Question 13
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.
 A I only B II only C Both I and II D Neither I nor II
Question 13 Explanation:
1. Next pointer of front node points to the rear node.
2. Next pointer of rear points to the front node. So if we consider circular linked list the next of 44 is 11.
If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.
For delete O(1), for insert O(n).
It is clearly known that next pointer of rear node points to the front node.
Hence, only II is true.
 Question 14

Consider the following function implemented in C:

```void printxy (int x, int y)   {
int *ptr;
x = 0;
ptr = &x;
y = *ptr;
*ptr = 1;
printf("%d,%d",x,y);
}
```

The output of invoking printxy(1, 1) is

 A 0, 0 B 0, 1 C 1, 0 D 1, 1
Programming       Programming       Video-Explanation
Question 14 Explanation:
printxy (int x, int y)
{
int *ptr;
x = 0;
ptr = &x;
y = *ptr;
*ptr = 1; }
printxy (1, 1) Question 15

The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below? A MNOPQR B NQMPOR C QMNROP D POQNMR
Data-Structures       BFS       Video-Explanation
Question 15 Explanation:
The possible order of visiting the nodes in Breadth First Search Algorithm, implementing using Queue Data Structure is (Do it by option Elimination)
(a) MNOPQR – MNO is not the proper order R must come in between.
(b) NQMPOR – QMP is not the order O is the child of N.
(C) QMNROP – M is not the child of Q, so QMN is false.
(D) POQNMR – P → OQ → NMR is the correct sequence. Hence Option (D).
 Question 16

Identify the language generated by the following grammar, where S is the start variable.

```                                     S → XY
X → aX|a
Y → aYb|ϵ
```
 A {am bn │ m ≥ n, n > 0} B {am bn │ m ≥ n, n ≥ 0} C {am bn │ m > n, n ≥ 0} D {am bn │ m > n, n > 0}
Theory-of-Computation       Finite-Automata       Video-Explanation
Question 16 Explanation:
The production X→ aX | a can generate any number of a’s ≥ 1 and the production Y→ aYb | ϵ will generate equal number of a’s and b’s.
So the production S→XY can generate any number of a’s (≥1) in the beginning (due to X) and then Y will generate equal number of a’s and b’s.
So, the number of a’s will always be greater than number of b’s and number of b’s must be greater than or equal to 0 (as Y → ϵ, so number of b’s can be zero also).
Hence the language is {am bn│m>n,n≥0}.
There are 16 questions to complete.

Register Now