Question 1

If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?

 A Suffix (L) = {y ∈ Σ* such that xy ∈ L} B {wwR │w ∈ L} C Prefix (L) = {x ∈ Σ*│∃y ∈ Σ* such that xy ∈ L} D L ∙ LR = {xy │ x ∈ L, yR ∈ L}
Theory-of-Computation       GATE 2019
Question 1 Explanation:
wwR cannot be recognized without using stack, so it cannot be regular.
 Question 2

The chip select logic for a certain DRAM chip in a memory system design is shown below. Assume that the memory system has 16 address lines denoted by A15 to A0. What is the range of addresses (in hexadecimal) of the memory system that can get enabled by the chip select (CS) signal? A C800 to C8FF B C800 to CFFF C DA00 to DFFF D CA00 to CAFF
Computer-Organization       GATE 2019
Question 2 Explanation:
Total address space from A0 - A15 = 215
The chip select address for given figure:
A4 - A15 = 25
So, total addressable loactions = 216/25 = 211
211 = 2048 or location 0 to 2047
∴ CFFF - C800 = 2047
 Question 3
 A 1 B Limit does not exist C 53/12 D 108/7
Engineering-Mathematics       GATE 2019
Question 3 Explanation: Question 4

Which of the following protocol pairs can be used to send and retrieve e-mails (in that order)?

 A SMTP, MIME B SMTP, POP3 C IMAP, POP3 D IMAP, SMTP
Computer-Networks       GATE 2019
Question 4 Explanation:
SMTP & POP3 are the protocols which are responsible for the email communication, SMTP is responsible for outgoing mail & POP3 is responsible for retrieving mail.
POP3: Post Office Protocol (Responsible for retrieve email)
SMTP: Simple Mail Transfer Protocol (Responsible for send Email)
IMAP: Internet Message Access protocol (Responsible for store and view)
MIME: Multi purpose Internet Mail Extensions (For media)
 Question 5

Which one of the following statements is NOT correct about the B+ tree data structure used for creating an index of a relational database table?

 A Each leaf node has a pointer to the next leaf node B Non-leaf nodes have pointers to data records C B+ Tree is a height-balanced tree D Key values in each node are kept in sorted order
Database-Management-System       GATE 2019
Question 5 Explanation:
(Memory based question)
In B+ trees non-leaf nodes do not have pointers to data records.
 Question 6
Consider the following C program:
```        #include <stdio.h>
int main ()  {
int arr [] = {1,2,3,4,5,6,7,8,9,0,1,2,5}, *ip = arr+4;
printf ("%d\n", ip);
return 0;
}
```

The number that will be displayed on execution of the program is _____.

 A 5 B 6 C 7 D 8
Programming-for-Output-Problems       GATE 2019
Question 6 Explanation: We know that arr is a pointer to arr[ ] & hence arr+4 is pointer to 4th index of array (starting from 0 to 4).
Now *ip is a pointer of int type pointing to memory location108, which is part of arr.
Hence, when we will print ip it will be equivalent to *(ip+1).
Address of ip will be incremented by 1 & value inside 110 will be printed.
 Question 7

A certain processor uses a fully associative cache of size 16 kB. The cache block size is 16 bytes. Assume that the main memory is byte addressable and uses a 32-bit address. How many bits are required for the Tag and the Index fields resectively in the addresses generated by the processor?

 A 28 bits and 0 bits B 24 bits and 4 bits C 24 bits and 0 bits D 28 bits and 4 bits
Computer-Organization       GATE 2019
Question 7 Explanation:
Since, it is said for fully associative cache so No index bits is there. So, now for tag bits,
Total bits - Offset bits = 32 - 4 = 28
So, tag bits = 28, Index bits = 0
 Question 8

Consider the following two statements about database transaction schedules:

```I. Strict two-phase locking protocol generates conflict serializable schedules that are also recoverable.
II. Timestamp-ordering concurrency control protocol with Thomas Write Rule can generate view serializable schedules that are not conflict serializable.
```
Which of the above statements is/are TRUE?
 A Both I and II B Neither I nor II C II only D I only
Database-Management-System       GATE 2019
Question 8 Explanation:
(Memory-based question)
In strict 2PL, a transaction T does not release any of its exclusive (write) locks until after it commits or aborts.
Hence, no other transaction can read or write an item that is written by T unless T has committed, leading to a strict schedule for recoverability.
(Ref: Fundamentals of Database Systems by Elmasri and Navathe, 7e Pg. No. 789)
By ignoring the write, Thomas write rule allows schedules that are not conflict serializable but are nevertheless correct.
Those non-conflict-serializable schedules allowed satisfy the definition of view serializable schedules.
(Ref: Database System Concepts by Silberschatch, Korth and Sudarshan, 6e Pg No. 686)
 Question 9
Consider the grammar given below:
```S → Aa
A → BD
B → b | ε
D → d | ε
```
Let a, b, d, and \$ be indexed as follows: Compute the FOLLOW set of the non-terminal B and write the index values for the symbols in the FOLLOW set in the descending order. (For example, if the FOLLOW set is {a, b, d, \$}, then the answer should be 3210)

 A 30 B 31 C 10 D 21
Compiler-Design       GATE 2019
Question 9 Explanation:
Follow(B) = First(D) Union Follow(A)
{Follow(B) = Follow(A) when D is epsilon}
Follow(B) = {d} Union {a} = {a,d}
 Question 10

Let G be an arbitrary group. Consider the following relations on G:

```      R1: ∀a,b ∈ G, aR1b if and only if ∃g ∈ G such that a = g-1bg
R2: ∀a,b ∈ G, aR2b if and only if a = b-1
```
Which of the above is/are equivalence relation/relations?
 A R2 only B R1 and R2 C Neither R1 and R2 D R1 only
Engineering-Mathematics       GATE 2019
Question 10 Explanation:
A relation between the elements of a set is symmetric, reflexive and transitive then such relation is called as equivalence relation.
Consider Statement R1:
Reflexive:
aR1a
⇒ a = g-1ag
Left multiply both sides by g
⇒ ga = gg-1ag
Right multiply both sides by g-1
⇒ gag-1 = gg-1agg-1
⇒ gag-1 = a [∴ The relation is reflexive]
Symmetric:
If aR1b, then ∃g ∈ G such that gag-1 = b then a = g-1bg, which is Correct.
⇒ So, given relation is symmetric.
Transitive:
The given relation is Transitive.
So, the given relation R1 is equivalence.
R2:
The given relation is not reflexive. So, which is not equivalence relation. Such that a ≠ a-1. So, only R1 is true.
 Question 11
In 16-bit 2's complement representation, the decimal number -28 is:
 A 1111 1111 1110 0100 B 1111 1111 0001 1100 C 0000 0000 1110 0100 D 1000 0000 1110 0100
Digital-Logic-Design       GATE 2019
Question 11 Explanation:
+28 = 0000 0000 0001 1100

1’s complement = 1111 1111 1110 0011
2’s complement = 1’s complement + 1

2’s complement = 1111 1111 1110 0100
= (-28)
 Question 12

Two numbers are chosen independently and uniformly at random from the set {1, 2, ..., 13}. The probability (rounded off to 3 decimal places) that their 4-bit (unsigned) binary representations have the same most significant bit is ______.

 A 0.502 B 0.461 C 0.402 D 0.561
Digital-Logic-Design       GATE 2019
Question 12 Explanation:
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110
7 - 0111
8 - 1000
9 - 1001
10 - 1010
11 - 1011
12 - 1100
13 - 1101
The probability that their 4-bit binary representations have the same most significant bit is
= P(MSB is 0) + P(MSB is 1)
= (7×7)/(13×13) + (6×6)/(13×13)
= (49+36)/169
= 85/169
= 0.502
 Question 13
Which one of the following kinds of derivation is used by LR parsers?
 A Leftmost in reverse B Rightmost in reverse C Leftmost D Rightmost
Compiler-Design       GATE 2019
Question 13 Explanation:
LR parsers have Rightmost derivation in reverse.
 Question 14

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum . Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

 A 19 B 39 C 29 D 09
Algorithms       GATE 2019
Question 14 Explanation:
First understand the subsequence is an array is
Ex: {A,B,C,D}
B, BC,BD,BCD,
C,CD,
D }
Step-1: Array of elements A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0 ]
Step-2: As per the given question, if they want to find maximum subsequence means
{6,3,13,4,4,12}
= 42
Step-3: But according to given recurrence relation, the sequence should be continuous. {6,3,13,4,4,12}.
This is not continuous subsequence.
Step-4: The continuous sequence is {6, 3, -1, -2, 13, 4, -9, -1, 4, 12}
Total is {29}
Note: We can't get more than 29 maximum subsequence sum.
 Question 15

Consider three concurrent processes P1, P2 and P3 as shown below, which access a shared variable D that has been initialized to 100. The process are executed on a uniprocessor system running a time-shared operating system. If the minimum and maximum possible values of D after the three processes have completed execution are X and Y respectively, then the value of Y–X is _______.

 A 10 B 40 C 60 D 80
Operating-Systems       GATE 2019
Question 15 Explanation: P1 executes D=D+20, D=120.
P3 executes D=D+10, D=130.
Now, P2 has D=100, executes
D = D-50 = 100-50 = 50
P2 writes D=50 final value. This is minimum.
Next,
P2 reads D=100, executes D = D-50, before that assume P1 & P3 has read D=100.
P2 makes D=50 & writes it.
P1 executes (D=100), D=D+20 & P3 executes D=D+10 gives maximum value D=130.
So, Y - X = 130 - 50 =80.
 Question 16

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _____.

 A 0.08 B 0.01 C 1 D 8
Algorithms       GATE 2019
Question 16 Explanation:
Step-1: Given, 25 distinct elements are to be sorted using quicksort.
Step-2: Pivot element = uniformly random.
Step-3: Worst case position in the pivot element is either first (or) last.
Step-4: So total 2 possibilities among 25 distinct elements
= 2/25
= 0.08
 Question 17

Let X be a square matrix. Consider the following two statements on X.

```I. X is invertible.
II. Determinant of X is non-zero.
```
Which one of the following is TRUE?
 A I implies II; II does not imply I. B II implies I; I does not imply II. C I and II are equivalent statements. D I does not imply II; II does not imply I.
Engineering-Mathematics       GATE 2019
Question 17 Explanation:
X is invertible means, that X is non-singular matrix.
That means we can also say that determinant of X is non-zero.
 Question 18

For Σ = {a,b}, let us consider the regular language L = {x|x = a2+3k or x = b10+12k, k ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

 A 3 B 9 C 5 D 24
Theory-of-Computation       GATE 2019
Question 18 Explanation:
Pumping Lemma for Regular Languages:
For any language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u,v, w ∈ Σ*, such that x = uvw, and
(1) |uv| ≤ n
(2) |v| ≥ 1
(3) for all i ≥ 0: uviw ∈ L
We have to find "n" which satisfies for all the strings in L.
Considering strings derived by b10+12k.
The minimum string in L = "bbbbbbbbbb" but this string b10 cannot be broken in uvw.
So, pumping length 3, 9 and 5 cannot be the correct answer.
So, the minimum pumping length, such that any string in L can be divided into three parts "uvw" must be greater than 10 .
 Question 19

Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to

 A n! B 1 C (n-1)! D Engineering-Mathematics       GATE 2019
Question 19 Explanation:
A Hamiltonian cycle is a closed loop on a graph where every node (vertex) is visited exactly once.
The total number of hamiltonian cycles in a complete graph are
(n-1)!/2, where n is number of vertices.
 Question 20

Consider Z = X - Y, where X, Y and Z are all in sign-magnitude form. X and Y are each represented in n bits. To avoid overflow, the representation of Z would require a minimum of:

 A n bits B n + 2 bits C n - 1 bits D n + 1 bits
Digital-Logic-Design       GATE 2019
Question 20 Explanation:
In case of addition of two numbers with the same sign, there is a chance of overflow.
To store overflow/carry bit there should be extra space to accommodate it.
Hence, Z should be n+1 bits.
 Question 21
The value of 351 mod 5 is ______.
 A 3 B 5 C 2 D 1
Computer-Networks       GATE 2019
Question 21 Explanation:
351 mod 5
⇒ 31 = 3 ⇒ 3 mod 5 = 3
32 ⇒ 9 mod 5 = 4
33 ⇒ 27 mod 5 = 2
34 ⇒ 81 mod 5 = 1
35 ⇒ 243 mod 5 = 3
For every four numbers sequence is repeating.
So, (51 % 4) = 3
⇒ 33 = 27
⇒ 27 mod 5 = 2
 Question 22
Which one of the following is NOT a valid identity?
 A (x + y) ⊕ z = x ⊕ (y + z) B (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) C x ⊕ y = x + y, if xy = 0 D x ⊕ y = (xy + x'y')'
Digital-Logic-Design       GATE 2019
Question 22 Explanation:
Let x=1, y=1, z=0.
(x+y) ⊕ z = (1+1)⊕ 0 = 1 ⊕ 0 = 1
x ⊕ (y+z) = 1⊕(1+0) = 1 ⊕ 1 = 0
So,
(x+y) ⊕ z ≠ x ⊕ (y+z)
 Question 23
Consider the following C program:
```         #include <stdio.h>
int jumble (int x, int y)  {
x = 2 * x + y ;
return x ;
}
int main ( )  {
int x=2, y=5 ;
y = jumble (y, x) ;
x = jumble (y, x) ;
printf ("%d \n", x) ;
return 0 ;
}
```
The value printed by the program is ______.
 A 26 B 67 C 25 D 13
Programming-for-Output-Problems       GATE 2019
Question 23 Explanation:
////////////////////////////////////Program
#include
int jumble(int x, int y)
{
printf("Inside jumble : 2*%d + %d\n", x,y);
x = 2*x +y;
return x;
}
int main()
{
int x=2, y=5;
printf("Initial x=%d, y=%d\n",x,y);
printf("1st jumble call:jumble(%d,%d)\n",y,x);
y = jumble(y,x);
printf("Value of y after 1st jumble = %d\n", y);
printf("2nd jumble call: jumble(%d,%d)\n", y,x);
x = jumble(y,x);
printf("Value of x after 2nd jumble = %d\n", x);
printf("Final : %d\n", x);
return 0;
}
////////////////////////////////////OUTPUT
Initial x=2, y=5
1st jumble call: jumble(5,2)
Inside jumble : 2*5 + 2
Value of y after 1st jumble = 12
2nd jumble call: jumble(12,2)
Inside jumble : 2*12 + 2
Value of x after 2nd jumble = 26
Final : 26
 Question 24

The following C program is executed on a Unix/Linux system:

```            #include <unistd.h>
int main ()
{
int i ;
for (i=0; i<10; i++)
if (i%2 == 0) fork ( ) ;
return 0 ;
}
```
The total number of child processes created is _____.
 A 26 B 33 C 31 D 28
Operating-Systems       GATE 2019
Question 24 Explanation:
Fork( ) statement is executed when 'i' is even. Thus the above code is equivalent to
#include
int main( )
{
int i;
fork( );
fork( );
fork( );
fork( );
fork( );
}
n - fork statements will have 2n-1 child.
Hence, n = 5 ⇒ We have 31 child processes.
 Question 25

Let U = {1,2,...,n}. Let A = {(x,X)|x ∈ X, X ⊆ U}. Consider the following two statements on |A|.

``` ```
Which of the above statements is/are TRUE?
 A Only II B Only I C Neither I nor II D Both I and II
Engineering-Mathematics       GATE 2019
Question 25 Explanation:
Let us consider U = {1, 2}
and given A = {(x, X), x∈X and X⊆U}
Possible sets for U = {Φ, {1}, {2}, {1, 2}}
if x=1 then no. of possible sets = 2
x=2 then no. of possible sets = 2
⇒ No. of possible sets for A = (no. of sets at x=1) + (no. of sets at x=2) = 2 + 2 = 4
Consider statement (i) & (ii) and put n=2 Statement (i) is true Statement (i) and (ii) both are true. Answer: (C)
 Question 26

Consider the following relations P(X,Y,Z), Q(X,Y,T) and R(Y,V). How many tuples will be returned by the following relational algebra query?

```          ∏x(σ(P.Y=R.Y ∧ R.V=V2)(P × R)) - ∏x(σ(Q.Y=R.Y ∧ Q.T>2)(Q × R))
```
 A 0 B 1 C 2 D 3
Database-Management-System       GATE 2019
Question 26 Explanation:
σ(P.Y=R.Y ∧ R.V=V2)(P × R) x(P.Y=R.Y ∧ R.V=V2)(P × R)) σ(Q.Y=R.Y ∧ Q.T>2)(Q × R) x(Q.Y=R.Y ∧ Q.T>2)(Q × R)) x(P.Y=R.Y ∧ R.V=V2)(P × R)) - ∏x(Q.Y=R.Y ∧ Q.T>2)(Q × R)) Question 27

What is the minimum number of 2-input NOR gates required to implement a 4-variable function 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.

 A 2 B 4 C 7 D 1 E 3(Option not given)
Digital-Logic-Design       GATE 2019
Question 27 Explanation:
f = Σ(0, 2, 5, 7, 8, 10, 13, 15)  Question 28

Consider three machines M, N, and P with IP addresses 100.10.5.2, 100.10.5.5, and 100.10.5.6 respectively. The subnet mask is set to 255.255.255.252 for all the three machines. Which one of the following is true?

 A M, N, and P all belong to the same subnet B Only M and N belong to the same subnet C M, N, and P belong to three different subnets D Only N and P belong to the same subnet
Computer-Networks       GATE 2019
Question 28 Explanation:
Take each IP and do bitwise AND with the given Subnet Mask. If we get the same network ID for the given IP'S then it will belong to the same subnet. Therefore, N and P belong to the same subnet.
 Question 29

Consider three 4-variable functions f1, f2 and f3, which are expressed in sum-of-minterms as

```f1 = Σ(0, 2, 5, 8, 14),  f2 = Σ(2, 3, 6, 8, 14, 15),  f3 = Σ(2, 7, 11, 14)
```

For the following circuit with one AND gate and one XOR gate, the output function f can be expressed as: A Σ (2, 14) B Σ (7, 8, 11) C Σ (2, 7, 8, 11, 14) D Σ (0, 2, 3, 5, 6, 7, 8, 11, 14, 15)
Digital-Logic-Design       GATE 2019
Question 29 Explanation:
f1*f2 = ∑(2,8,14)
f3 = ∑(2,7,11,14)
f1*f2 ⊕ f3 = ∑(2,8,14) ⊕ ∑(2,7,11,14)
= ∑(8,7,11) (Note: Choose the terms which are not common)
 Question 30
Consider the augmented grammar given below:
```    S' → S
S → 〈L〉 | id
L → L,S | S
```

Let I0 = CLOSURE ({[S' → ·S]}). The number of items in the set GOTO (I0 , 〈 ) is: _____.

 A 4 B 5 C 6 D 7
Compiler-Design       GATE 2019
Question 30 Explanation:
I0 = CLOSURE ({[S' → ·S]}) Hence, the set GOTO (I0 , 〈 ) has 5 items.
 Question 31
Consider the following statements:
```  I. The smallest element in a max-heap is always at a leaf node
II. The second largest element in a max-heap is always a child of the root node
III. A max-heap can be constructed from a binary search tree in Θ(n) time
IV. A binary search tree can be constructed from a max-heap in Θ(n) time
```
Which of the above statements are TRUE?
 A I, II and III B II, III and IV C I, III and IV D I, II and IV
Algorithms       GATE 2019
Question 31 Explanation:
i) TRUE: The smallest element in heap is always a leaf node but depends upon the graph, it may be left or right side of the graph.
(ii) TRUE: The second smallest element in a heap is always a child of root node. (iii) TRUE: Converting from binary search tree to max heap will take O(n) time as well as O(n) space complexity.
(iv) FALSE: We can’t convert max heap to binary search tree in O(n) time.
 Question 32

In an RSA cryptosystem, the value of the public modulus parameter n is 3007. If it is also known that Φ(n) = 2880, where Φ() denotes Euler's Totient Function, then the prime factor of n which is greater than 50 is ______.

 A 107 B 97 C 45 D 92
Computer-Networks       GATE 2019
Question 32 Explanation:
It can be solved by Hit and trial method in less time.
n = 3007, fi(n) = 2880 → fi(n) = (p – 1) (q – 1),
where p, q are prime factor of n.
The unit place of n is 7, it is a prime number and factor will be
1.7=7
11*17
21*37
31*47
….
31*97 =>3007
n = 3007 => 31*97
Therefore, 31 & 97 are the two prime numbers, which is satisfying the condition and 97 is greater than 50.
So, 97 is the correct answer.
Other methods:
When ϕ(n) is given when n=pq where p and q are prime numbers, then we have
ϕ(n) = (p−1)(q−1) = pq−(p+q)+1
But pq=n,
therefore, ϕ(n) = n−(p+q)+1 and p+q = n+1−ϕ(n).
Now, p and q are the roots of the equation,
x2 − (p+q)x + pq = (x-p)(x-q)
Substituting for p+q and pq in the above equation
x2 - (n+1-ϕ(n))x + n
 Question 33

A relational database contains two tables Student and Performance as shown below: The primary key of the Student table is Roll_no. For the Performance table, the columns Roll_no. and Subject_code together from the primary key. Consider the SQL query given below:

```       SELECT S.Student_name, sum (P.Marks)
FROM Student S, Performance P
WHERE P.Marks > 84
GROUP BY S.Student_name;
```

The number of rows returned by the above SQL query is _____.

 A 0 B 9 C 7 D 5
Database-Management-System       GATE 2019
Question 33 Explanation:
(Executed under Oracle Express Edition)
SQL> SELECT S.Student_name,sum(P.Marks)
2 FROM Student S,Performance P
3 WHERE P.Marks>84
4 GROUP BY S.Student_name; Question 34

Assume that in a certain computer, the virtual addresses are 64 bits long and the physical addresses are 48 bits long. The memory is word addressable. The page size is 8 kB and the word size is 4 bytes. The Translation Look-aside Buffer (TLB) in the address translation path has 128 valid entries. At most how many distinct virtual addresses can be translated without any TLB miss?

 A 8×220 B 4×220 C 16×210 D 256×210
Operating-Systems       GATE 2019
Question 34 Explanation:
A TLB has 128 valid entries.
So, it can refer to 27 pages.
Each page size is 8 kB & word is 4 bytes. Question 35

Consider the following four processes with arrival times (in milliseconds) and their length of CPU bursts (in milliseconds) as shown below: These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is _____.

 A 2 B 7 C 1 D 4
Operating-Systems       GATE 2019
Question 35 Explanation:
This is the Gantt chart till time = 4 units At this point P4 arrives with burst 'Z' & P3 is in queue with burst 3.
P1 & P2 have executed with P1 incurred delay 1unit & P2 0units.
Hence, Avg = 0+1+x/4 =1
⇒ x=3, the next delay should be 3. It would happen if assume Z=2.
It executes and completes at 6.
P3 will wait totally for 3units.
Hence, Avg=1. Z=2
 Question 36

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) _____.

 A 5.54 B 1.34 C 4.25 D 3.82
Data-Structures       GATE 2019
Question 36 Explanation:
There can be 8 paths between any 2 uniformly & independently chosen leaf nodes.
A node can be chosen twice and the path from that node to itself will be zero.
∴ Path 1 = 0
Similarly,
Path 2 = 2
Path 3 = 4
Path 4 = 4
Path 5 = 6
Path 6 = 6
Path 7 = 6
Path 8 = 6
∴ Expected value = Σ Path length × Probability of selecting path
= 2×1/8 + 4×2/8 + 6×4/8 + 0×1/8
= 1/4 + 1/1 + 3/1 + 0
= 4 + 1/4
= 17/4
= 4.25
 Question 37

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 _____.

 A 3 B 7 C 1 D 5
Computer-Networks       GATE 2019
Question 37 Explanation:
In 8 port Ethernet switch one port for the network connection and remaining 7 port for the machine.
Therefore the total required number of the switches = Ceil (15 /7) = 3 Question 38

There are n unsorted arrays: A1, A2, ..., An. Assume that n is odd. Each of A1, A2, ..., An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, ..., An is

 A O(n) B O(n log n) C Ω(n2 log n) D O(n2)
Algorithms       GATE 2019
Question 38 Explanation:
Finding the median in an unsorted array is O(n).
But it is similar to quicksort but in quicksort, partitioning will take extra time.
→ Find the median will be (i+j)/2
1. If n is odd, the value is Ceil((i+j)/2)
2. If n is even, the value is floor((i+j)/2)
-> Here, total number of arrays are
⇒ O(n)*O(n)
⇒ O(n2)
Note:
They are clearly saying that all are distinct elements.
There is no common elements between any two arrays.
 Question 39

Suppose Y is distributed uniformly in the open interval (1,6). The probability that the polynomial 3x2 + 6xY + 3Y + 6 has only real roots is (rounded off to 1 decimal place) _____.

 A 0.3 B 0.9 C 0.1 D 0.8
Engineering-Mathematics       GATE 2019
Question 39 Explanation:
Given polynomial equation is
3x2 + 6xY + 3Y + 6
= 3x2 + (6Y)x + (3Y + 6)
whch is in the form: ax2 + bx + c
For real roots: b2 - 4ac ≥ 0
⇒ (6Y)2 - 4(3)(3Y + 6) ≥ 0
⇒ 36Y2 - 36Y - 72 ≥ 0
⇒ Y2 - Y - 2 ≥ 0
⇒ (Y+1)(Y-2) ≥ 0
Y = -1 (or) 2
The given interval is (1,6).
So, we need to consider the range (2,6).
The probability = (1/(6-1)) * (6-2) = 1/5 * 4 = 0.8
 Question 40
Consider the following C program:
```       #include <stdio.h>
int main()
{
int a[] = {2, 4, 6, 8, 10} ;
int i, sum = 0, *b = a + 4 ;
for (i = 0; i < 5; i++)
sum = sum + (*b - i) - *(b - i) ;
printf ("%d\n", sum) ;
return 0 ;
}
```
The output of the above C program is _____.
 A 3 B 7 C 11 D 10
Programming-for-Output-Problems       GATE 2019
Question 40 Explanation:
///////////////////////////////////PROGRAM
#include
int main()
{
int a[] = {2,4,6,8,10};
int i, sum = 0, *b = a+4;
for(i=0; i<5; i++)
{ printf("*b, (*b-i): %d , %d\n",*b, (*b-i) );
printf("*(b-i): %d\n",*(b-i) );
printf("sum = %d + %d - %d\n",sum, (*b-i),*(b-i));
sum = sum + (*b-i) - *(b-i);
printf("sum = %d\n", sum);
}
printf("%d\n", sum);
return 0;
}
//////////////////////////////OUTPUT
*b, (*b-i): 10 , 10
*(b-i): 10
sum = 0 + 10 - 10
sum = 0
*b, (*b-i): 10 , 9
*(b-i): 8
sum = 0 + 9 - 8
sum = 1
*b, (*b-i): 10 , 8
*(b-i): 6
sum = 1 + 8 - 6
sum = 3
*b, (*b-i): 10 , 7
*(b-i): 4
sum = 3 + 7 - 4
sum = 6
*b, (*b-i): 10 , 6
*(b-i): 2
sum = 6 + 6 - 2
sum = 10
10
 Question 41

Let the set of functional dependencies F = {QR → S, R → P, S → Q} hold on a relation schema X = (PQRS). X is not in BCNF. Suppose X is decomposed into two schemas Y and Z, where Y = (PR) and Z = (QRS).

Consider the two statements given below.
```    I. Both Y and Z are in BCNF
II. Decomposition of X into Y and Z is dependency preserving and lossless
```
Which of the above statements is/are correct?
 A I only B Neither I nor II C II only D Both I and II
Database-Management-System       GATE 2019
Question 41 Explanation:
Y = (PR)
R → P
R+ = RP
* In R → P, 'R' is a super key. So, Y is in BCNF.
Z = (QRS)
QR → S
S → Q
CK's = QR, RS
* In, S → Q, 'S' is not a super key. So, Z is not in BCNF.
* Y is in BCNF and Z is not in BCNF.
* 'R' is common attribute in the relations Y and Z and R is candidate key for Y. So, the decomposition is lossless.
* The FD, R → P is applicable on Y and QR → S, S → Q are applicablein 2.
So, the decomposition is dependency preserving.
* Hence, Statement II is correct.
 Question 42
Consider the first order predicate formula φ:
∀x[(∀z z|x ⇒ ((z = x) ∨ (z = 1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒ ((w = z) ∨ (z = 1)))]

Here 'a|b' denotes that 'a divides b', where a and b are integers. Consider the following sets:

```     S1.  {1, 2, 3, ..., 100}
S2.  Set of all positive integers
S3.  Set of all integers
```
Which of the above sets satisfy φ?
 A S1 and S3 B S1, S2 and S3 C S2 and S3 D S1 and S2
Engineering-Mathematics       GATE 2019
Question 42 Explanation:
The first order logic gives the meaning that if z is a prime number then there exists another prime number in the set which is larger than it.
One of the case: If -7 is a number which is prime (either divided by -7 or 1 only). then there exists some number like -3 which is larger than -7 also satisfy the property ( either divided by -3 or 1 only).
So, S3 is correct
It's true for all integers too
 Question 43

A certain processor deploys a single-level cache. The cache block size is 8 words and the word size is 4 bytes. The memory system uses a 60-MHz clock. To service a cache miss, the memory controller first takes 1 cycle to accept the starting address of the block, it then takes 3 cycles to fetch all the eight words of the block, and finally transmits the words of the requested block at the rate of 1 word per cycle. The maximum bandwidth for the memory system when the program running on the processor issues a series of read operations is ______ × 106 bytes/sec.

 A 160 B 145 C 172 D 124
Computer-Organization       GATE 2019
Question 43 Explanation: Cache block = 8 words
Word size = 4 bytes
Cache block size = 32 bytes
Clock = 60 MHz
⇒ T = 1/clock = 1/60×106 seconds
Cache miss
= 1 cycle(Address) + 3 cycles (8 words) + 1word/cycle ×8 (transfer)
= 12 cycles
= 12/60×106
Total bandwidth = total data/total time = 32 bytes/(12/60×106) = 160 × 106 bytes/second
 Question 44
Consider the following sets:
```    S1.  Set of all recursively enumerable languages over the alphabet {0,1}
S2.  Set of all syntactically valid C programs
S3.  Set of all languages over the alphabet {0,1}
S4.  Set of all non-regular languages over the alphabet {0,1}
```
Which of the above sets are uncountable?
 A S2 and S3 B S3 and S4 C S1 and S4 D S1 and S2
Theory-of-Computation       GATE 2019
Question 44 Explanation:
S1 is countable, set of all recursively enumerable languages means set of all Turing machines and we can enumerate TM and have one to one correspondence between natural number.
S2 is countable, since a valid C program represents a valid algorithm and every algorithm corresponds to a Turing Machine, so S2 is equivalent to set of all Turing Machines.
S3 is is uncountable, it is proved by diagonalization method.
S4 is uncountable, as set of non-regular languages will have languages which is set of all languages over alphabet {0,1} i.e., S3.
 Question 45

Consider the following grammar and the semantic actions to support the inheriteatd type declaration attributes. Let X1, X2, X3, X4, X5 and X6 be the placeholders for the non-terminals D, T, L or L1 in the following table: Which one of the following are the appropriate choices for X1, X2, X3 and X4?

 A X1 = L, X2 = L, X3 = L1, X4 = T B X1 = L, X2 = T, X3 = L1, X4 = L C X1 = T, X2 = L, X3 = L1, X4 = T D X1 = T, X2 = L, X3 = T, X4 = L1
Compiler-Design       GATE 2019
Question 45 Explanation:
Since The production
L → L1, id {X3.type = X4.type } , this production has L and L1, hence X3 and X4 cannot be T.
So option 1, 3 and 4 cannot be correct.
 Question 46

Which one of the following languages over Σ = {a,b} is NOT context-free?

 A {wwR |w ∈ {a,b}*} B {wanwRbn |w ∈ {a,b}*, n ≥ 0} C {anbi | i ∈ {n, 3n, 5n}, n ≥ 0} D {wanbnwR |w ∈ {a,b}*, n ≥ 0}
Theory-of-Computation       GATE 2019
Question 46 Explanation:
{wanwRbn |w ∈ {a,b}*, n ≥ 0} cannot be CFL.
This is similar to language
L = {anbmcndm | n, m > 0}
Suppose we push “w” then an and then wR, now we cannot match bn with an, because in top of stack we have wR.
 Question 47
Consider the following C program:
```             #include <stdio.h>
int r()  {
static int num=7 ;
return num-- ;
}
int main ()  {
for (r(); r (); r())
printf ("%d", r());
return 0 ;
}
```

Which one of the following values will be displayed on execution of the programs?

 A 41 B 63 C 52 D 630
Programming-for-Output-Problems       GATE 2019
Question 47 Explanation:
///////////////////////////PROGRAM
#include
int r()
{
int x;
static int num=7;
x =num--;
printf("num--: %d\n",x);
return x;
}
int main()
{
for(r(); r(); r())
{
printf("%d\n", r());
}
return 0;
}
//////////////////////////////OUTPUT
num--: 7
num--: 6
num--: 5
5
num--: 4
num--: 3
num--: 2
2
num--: 1
num--: 0
 Question 48

Suppose that in an IP-over-Ethernet network, a machine X wishes to find the MAC address of another machine Y in its subnet. Which one of the following techniques can be used for this?

 A X sends an ARP request packet to the local gateway's IP address which then finds the MAC address of Y and sends to X B X sends an ARP request packet with broadcast IP address in its local subnet C X sends an ARP request packet to the local gateway's MAC address which then finds the MAC address of Y and sends to X D X sends an ARP request packet with broadcast MAC address in its local subnet
Computer-Networks       GATE 2019
Question 48 Explanation:
Address Resolution Protocol (ARP) is a protocol for mapping an Internet Protocol address (IP address) to a physical machine address (MAC) that is recognized in the local network.
Since both are present in the same subnet thus an ARP request packet can be sent as broadcast MAC address, all will see but the only destination will reply as a unicast reply.
Video Reference :
http://eclassesbyravindra.com/mod/page/view.php?id=147
 Question 49
Consider the following matrix: The absolute value of the product of Eigen values of R is ______.
 A 12 B 17 C 10 D 8
Engineering-Mathematics       GATE 2019
Question 49 Explanation: Question 50
Consider the following C function.
```               void convert (int n) {
if (n < 0)
printf ("%d", n);
else {
convert (n/2);
printf ("%d", n%2);
}
}
```

Which one of the following will happen when the function convert is called with any positive integer n as argument?

 A It will print the binary representation of n in the reverse order and terminate B It will not print anything and will not terminate C It will print the binary representation of n and terminate D It will print the binary representation of n but will not terminate
Programming-for-Output-Problems       GATE 2019
Question 50 Explanation:
////////////////OUTPUT
Sequence of function calls
Convert(6)
Convert(3)
Convert(1)
Convert(0)
:
Convert(0)
:
:
It will not terminate and never produce any output.
Note:
There is no instruction which stops the loop.
 Question 51

The index node (inode) of a Unix-like file system has 12 direct, one single-indirect and one double-indirect pointers. The disk block size is 4 kB, and the disk block address is 32-bits long. The maximum possible file size is (rounded off to 1 decimal place) ______ GB.

 A 7 B 9 C 2 D 4
Operating-Systems       GATE 2019
Question 51 Explanation:
No. of Disk block pointers = 4kB/32bits = 1k
Max. file size
= (12 × 1k + 1k × 1k) × 4kB ≈ (1024 × 12 + 1024 × 1024) × 4 × 1024 bytes
≈ 4GB
 Question 52

Consider the following snapshot of a system running n concurrent processes. Process i is holding Xi instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Yi additional instances of R while holding the Xi instances it already has. Of the n processes, there are exactly two processes p and q such that Yp = Yq = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?

 A Min (Xp, Xq) ≥ Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q} B Xp + Xq < Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q} C Min (Xp, Xq) ≤ Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q} D Xp + Xq < Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
Operating-Systems       GATE 2019
Question 52 Explanation:
{P1, P2, ..., Pn}
Pi holds Xi instances.
Pi can request additional Yi instances.
Given two process p & q such that their additional requests are zero.
Yp = Yq = 0
{Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q} means that out of 'n' processes, we are left with (n-2) process (except p&q), i.e., Yk indicates additional request of all the processes (n-2) except p & q.
For p & q to complete first, accordingly
Xp + Xq < Min {Yk}
Option D is correct.
There are exactly two process p and q which do not need any additional instances of resources.
So, p and q will complete their execution and will release Xp and Xq instances of resources.
Now to guarantee that no other process apart from p and q can complete execution, the no. of instances of resources available must be less than the minimum no. of instances of resources required by any other process, i.e.,
Xp + Xq < Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
 Question 53

Let Σ be the set of all bijections from {1, ..., 5} to {1, ..., 5}, where id denotes the identity function i.e. id(j) = j,∀j. Let º denote composition on functions. For a string x = x1 x2 ... xn ∈ Σn, n ≥ 0. Let π(x) = x1 º x2 º ... º xn.

Consider the language L = {x ∈ Σ* | π(x) = id}. The minimum number of  states in any DFA accepting L is ______.

 A 120 B 136 C 125 D 132
GATE 2019
 Question 54
Consider the following C program:
```       #include <stdio.h>
int main ()  {
float sum = 0.0, j = 1.0, i = 2.0;
while (i/j > 0.0625) {
j = j + j;
sum = sum + i/j;
printf ("%f \n", sum);
}
return 0;
}
```

The number of times the variable sum will be printed, when the above program is executed , is ______.

 A 5 B 2 C 7 D 10
Programming-for-Output-Problems       GATE 2019
Question 54 Explanation:
///////////////////////////////// PROGRAM
#include
int main()
{
float sum= 0.0, j=1.0, i=2.0;
while(i/j > 0.0625)
{
j = j+j;
sum = sum+i/j;
printf("%f\n",sum);
}
return 0;
}
//////////////////////////////////OUTPUT
1.000000
1.500000
1.750000
1.875000
1.937500
 Question 55
Let G be any connected, weighted, undirected graph.
```I. G  has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G  has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut.
```
Which of the above statements is/are TRUE?
 A I only B II only C Both I and II D Neither I nor II
Algorithms       GATE 2019
Question 55 Explanation:
Given G be a connected, weighted and undirected graph,
I. TRUE: G Graph is unique, no two edges of the graph is same. Step-1: Using Kruskal's algorithm, arrange each weights in ascending order.
17, 18, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30
Step-2: Step-3: 17 + 18 + 20 + 21 + 22 + 23 + 26 = 147
Step-4: Here, all the elements are distinct. So, the possible MCST is 1.
II. TRUE: As per the above graph, if we are cut the edge, that should the be the minimum edge.
Because we are already given, all minimum edge weights if graph is distinct.
 Question 56

Consider the following table Match the algorithm to design paradigms they are based on:

 A (P)↔(ii), Q↔(iii), (R)↔(i) B (P)↔(iii), Q↔(i), (R)↔(ii) C (P)↔(ii), Q↔(i), (R)↔(iii) D (P)↔(i), Q↔(ii), (R)↔(iii)
Algorithms       Gate 2017 set-01
Question 56 Explanation:
(P) Kruskal’s and Prim’s algorithms for finding Minimum Spanning Tree(MST). To find MST we are using greedy technique.
(Q) QuickSort is a Divide and Conquer algorithm.
(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.
Some important points regarding Greedy Vs Dynamic Programming
Greedy: →
It always gives polynomial time complexity
→ It is not an optimal
→ It always selects only either minimum or maximum among all possibilities
→ Ex: Dijkstra’s algorithm for SSSP, Optimal Merge Pattern, Huffman coding, Fractional knapsack problem, etc..,
Dynamic Programming:
→ It gives either polynomial or exponential time complexity.
→ It gives always an optimal result.
→ It checks all possibilities of a problem.
→ Ex: Longest Common sequence, Matrix chain Multiplication, Travelling sales Problem, etc..,
 Question 57
Which one of the following is NOT logically equivalent to ¬∃x(∀y(α) ∧ ∀z(β))?
 A ∀x(∃z(¬β)→∀y(α)) B ∀x(∀z(β)→∃y(¬α)) C ∀x(∀y(α)→∃z(¬β)) D ∀x(∃y(¬α)→∃z(¬β))
Gate 2013
Question 57 Explanation:
Option A:
∀x(∃z(¬β) → ∀y(α))
⇒ ∀x(¬∃z(¬β) ∨ ∀y(α))
⇒ ∀x(∀z(β)∨y(α))
⇒ ¬∃x¬(∀z(β)∨∀y(α))
⇒ ¬∃x(¬∀z(β)∧¬∀y(α))
A is Not equivalent to the given.
Option B:
∀x(∀z(β)→∃y(¬α))
⇒ ∀x(¬∀z(β)∨∃y(¬α))
⇒ ¬∃x¬(¬∀z(β)∨∃y(¬α))
⇒ ¬∃x(∀z(β)∨∀y(α))
B is Matching and equivalent to given.
Option C:
∀x(∀y(α)→∃z(¬β))
⇒ ∀x(¬∀y(α)∨∃z(¬β))
⇒ ¬∃x¬(¬∀y(α)∨∃z(¬β))
⇒ ¬∃x(∀y(α)∧z(β))
C is equivalent to the given.
Option D:
∀x(∃y(¬α)→∃z(¬β))
⇒ ∀x(¬∃y(¬α)∨∃z(β))
⇒ ∀x(∀y(α)∨∃z(β))
⇒ ¬∃x¬(∀y(α)∨∃z(β))
⇒ ¬∃x(¬∀y(α)∧¬∃z(β))
⇒ ¬∃x(¬∀y(α)∧∀z(¬β))
So D is Not equivalent to the given.
 Question 58
A company needs to develop a strategy for software product development for which it has a choice of two programming languages L1 and L2. The number of lines of code (LOC) developed using L2 is estimated to be twice the LOC developed with Ll. The product will have to be maintained for five years. Various parameters for the company are given in the table below. Total cost of the project includes cost of development and maintenance. What is the LOC for L1 for which the cost of the project using L1 is equal to the cost of the project using L2?
 A 4000 B 5000 C 4333 D 4667
Gate 2011
Question 58 Explanation:
Note: Out of syllabus.
 Question 59
A company needs to develop digital signal processing software for one of its newest inventions. The software is expected to have 40000 lines of code. The company needs to determine the effort in person-months needed to develop this software using the basic COCOMO model. The multiplicative factor for this model is given as 2.8 for the software development on embedded systems, while the exponentiation factor is given as 1.20. What is the estimated effort in person-months?
 A 234.25 B 932.5 C 287.8 D 122.4
Gate 2011
Question 59 Explanation:
Note: Out of syllabus.
 Question 60
HTML (Hyper Text Markup Language) has language elements which permit certain actions other than describing the structure of the web document. Which one of the following actions is NOT supported by pure HTML (without any server or client side scripting) pages?
 A Embed web objects from different sites into the same page B Refresh the page automatically after a specified interval C Automatically redirect to another page upon download D Display the client time as part of the page
Gate 2011
Question 60 Explanation:
Note: Out of syllabus.
 Question 61
Which of the following is NOT desired in a good Software Requirement Specifications (SRS) document?
 A Functional Requirements B Non-Functional Requirements C Goals of Implementation D Algorithms for Software Implementation
Gate 2011
Question 61 Explanation:
Note: Out of syllabus.
 Question 62
The following is the comment written for a C function
```/* This function computes the roots of a quadratic equation
a.x^2 + b.x + c = . The function stores two real roots
in *root1 and *root2 and returns the status of validity
of roots. It handles four different kinds of cases.
(i) When coefficient a is zero irrespective of discriminant
(ii) When discreminant is positive
(iii) When discriminant is zero
(iv) When discriminant is negative.
Only in case (ii) and (iii) the stored roots are valid.
Otherwise 0 is stored in roots. The function returns
0 when the roots are valid and -1 otherwise.
The function also ensures root1 >= root2
int get_QuadRoots( float a, float b, float c,
float *root1, float *root2);
*/

```

A software test engineer is assigned the job of doing black box testing. He comes up with the following test cases, many of which are redundant. Which one of the following option provide the set of non-redundant tests using equivalence class partitioning approach from input perspective for black box testing?
 A T1, T2, T3, T6 B T1, T3, T4, T5 C T2, T4, T5, T6 D T2, T3, T4, T5
Gate 2011
Question 62 Explanation:
Note: Out of syllabus.
T1 and T2 checking same condition a = 0 hence, any one of T1 and T2 is redundant.
T3, T4: in both case discriminant (D) = b2 – 4ac = 0. Hence any one of it is
T5 : D > 0
T6 : D < 0
 Question 63
The cyclomatic complexity of each of the modules A and B shown below is 10. What is the cyclomatic complexity of the sequential integration shown on the right hand side? A 19 B 21 C 20 D 10
2010
Question 63 Explanation:
Note: Out of syllabus.
 Question 64
What is the appropriate pairing of items in the two columns listing various activities encountered in a software life cycle?
```P. Requirements Capture	 1.Module Development and Integration
Q. Design	         2.Domain Analysis
R. Implementation	 3.Structural and Behavioral Modeling
S. Maintenance	         4.Performance Tuning```
 A P-3, Q-2, R-4, S-1 B P-2, Q-3, R-1, S-4 C P-3, Q-2, R-1, S-4 D P-2, Q-3, R-4, S-1
2010
Question 64 Explanation:
Note: Out of syllabus.
 Question 65
The following program is to be tested for statement coverage:
```begin
if (a== b) {S1; exit;}
else if (c== d) {S2;]
else {S3; exit;}
S4;
end```
The test cases T1, T2, T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables a, b, c and d. The exact values are not given. T1 : a, b, c and d are all equal T2 : a, b, c and d are all distinct T3 : a = b and c != d T4 : a != b and c = d Which of the test suites given below ensures coverage of statements S1, S2, S3 and S4?
 A T1, T2, T3 B T2, T4 C T3, T4 D T1, T2, T4
2010
Question 65 Explanation:
T1 covers S1
T2 covers S3
T4 covers S2, S4.
 Question 66
The coupling between different modules of a software is categorized as follows: I.  Content coupling           II. Common coupling III. Control coupling                IV .Stamp coupling V. Data coupling Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows
 A I-II-III-IV-V B V-IV-III-II-I C I-III-V-II-IV D IV-II-V-III-I
2009
Question 66 Explanation:
Note: Out of syllabus. [Software Engineering]
 Question 67
Consider the HTML table definition given below: < table border=1> <tr> <td rowspan=2> ab </td> <td colspan=2> cd </td> </tr> <tr> <td> ef </td> <td rowspan=2> gh </td> </tr> <tr> <td colspan=2> ik </td> </tr> </table> The number of rows in each column and the number of columns in each row are:
 A 〈2, 2, 3〉 and 〈2, 3, 2〉 B 〈2, 2, 3〉 and 〈2, 2, 3〉 C 〈2, 3, 2〉 and 〈2, 3, 2〉 D 〈2, 3, 2〉 and 〈2, 2, 3〉
2009
Question 67 Explanation:
Note: Out of syllabus. [Web Technologies]
 Question 68
Which of the following statements are TRUE? I.The context diagram should depict the system as a single bubble. II.External entities should be identified clearly at all levels of DFDs. III. Control information should not be represented in a DFD. IV. A data store can be connected either to another data store or to an external entity.
 A II and III B II and III C I and III D I, II and III
2009
Question 68 Explanation:
Note: Out of Syllabus. [Software Engineering]
 Question 69
Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE? I.The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph II.The cyclomatic complexity of a module is the number of decisions in the module plus one, where a decision is effectively any conditional statement in the module III.The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.
 A I and II B II and III C I and III D I, II and III
2009
Question 69 Explanation:
Note: Out of syllabus. [Software Engineering]
 Question 70
Find if the following statements in the context of software testing are TRUE or FALSE. (S1) Statement coverage cannot guarantee execution of loops in a program under test. (S2) Use of independent path testing criterion guarantees execution of each loop in a program under test more than once.
 A True, True B True, False C False, True D False, False
Gate 2008-IT
Question 70 Explanation:
Note: Out of syllabus.
 Question 71
Which of the following is TRUE only of XML but NOT HTML?
 A It is derived from SGML B It describes content and layout C It allows user defined tags D It is restricted only to be used with web browsers
Gate 2008-IT
Question 71 Explanation:
Note: Out of syllabus.
 Question 72
Which of the following are NOT considered when computing function points for a software project?
• (O1) External inputs and outputs
• (O2) Programming language to be used for the implementation
• (O3) User interactions
• (O4) External interfaces
• (O5) Number of programmers in the software project
• (O6) Files used by the system

 A 02, 03 B 01, 05 C 04, 06 D 02, 05
Gate 2008-IT
Question 72 Explanation:
Note: Out of syllabus.
 Question 73
A software project plan has identified ten tasks with each having dependencies as given in the following table: Task        Depends On T1                 - T2                T1 T3                T1 T4                T1 T5                T2 T6                T3 T7                T3, T4 T8               T4 T9               T5, T7, T8 T10             T6, T9 Answer the following questions: (Q1) What is the maximum number of tasks that can be done concurrently? (Q2) What is the minimum time required to complete the project, assuming that each task requires one time unit and there is no restriction on the number of tasks that can be done in parallel ?
 A 5, 5 B 4, 5 C 5, 4 D 4, 4
Gate 2008-IT
Question 73 Explanation:
Note: Out of syllabus.
 Question 74
A software engineer is required to implement two sets of algorithms for a single set of matrix operations in an object oriented programming language; the two sets of algo­rithms are to provide precisions of 10-3and 10-6, respectively. She decides to implement two classes, Low Precision Matrix and High Precision Matrix, providing precisions 10-3and 10-6 respectively. Which one of the following is the best alternative for the imple­mentation?
• (S1)  The two classes should be kept independent.
• (S2)  Low Precision Matrix should be derived from High Precision Matrix.
• (S3)  High Precision Matrix should be derived from Low Precision Matrix.
• (S4)  One class should be derived from the other; the hierarchy is immaterial.
 A S1 B S2 C S3 D S4
Gate 2008-IT
Question 74 Explanation:
Note: Out of syllabus.
 Question 75
Which of the following requirement specifications can be validated? (S1) If the system fails during any operation, there should not be any loss of data (S2) The system must provide reasonable performance even under maximum load conditions (S3) The software executable must be deployable under MS Windows 95, 2000 and XP (S4) User interface windows must fit on a standard monitor's screen
 A S4 and S3 B S4 and S2 C S3 and S1 D S2 and S1
Gate 2008-IT
Question 75 Explanation:
Note: Out of syllabus.
 Question 76
Consider the table employee(empId, name, department, salary) and the two queries Q1 ,Q2 below. Assuming that department 5 has more than one employee, and we want to find the employees who get higher salary than anyone in the department 5, which one of the statements is TRUE for any arbitrary employee table?
```Q1 : Select e.empId
From employee e
Where not exists
(Select * From employee s where s.department = “5” and
s.salary >=e.salary)
Q2 : Select e.empId
From employee e
Where e.salary > Any
(Select distinct salary From employee s Where s.department = “5”)```
 A Q1 is the correct query B Q2 is the correct query C Both Q1 and Q2 produce the same answer D Neither Q1 nor Q2 is the correct query
Gate-2007
Question 76 Explanation:
The required output is find the employees who get higher salary than anyone in the department “5”.
Query 1: Results the empId's which have higher salary than anyone in the department 5.
Query 2: Results the empId's which have higher salary than atleast one employee of department 5.
 Question 77
In the Spiral model of software development, the primary determinant in selecting activities in each iteration is
 A Iteration size B Cost C Adopted process such as Rational Unified Process or Extreme Programming D Risk
Gate 2007-IT
Question 77 Explanation:
Note: Out of syllabus.
 Question 78
Which of the following systems is a most likely candidate example of a pipe and filter architecture ?
 A Expert system B DB repository C Aircraft flight controller D Signal processing
Gate 2007-IT
Question 78 Explanation:
Note: Out of syllabus.
 Question 79
Given below are HTML lines, With reference to the HTML lines given above, consider the following statements. 1. Clicking on the point <80, 75> does not have any effect. 2. The web browser can identify the area applicable to the mouse-click within the image and the subsequent action to be taken without additional responses from the web server. 3. The dots in the cgi-bin URL will be resolved by the web browser before it is sent to the web server 4. The "fd.html" request when sent to the web server will result in a GET request. Exactly how many of the statements given above are correct?
 A 0 B 1 C 2 D 3
Gate 2007-IT
Question 79 Explanation:
Note: Out of syllabus.
 Question 80
Consider the XML document fragment given below: Consider the XPath expression: *[not (self ) : : TOC] What would be the result of the given XPath expression when the current node is Book?
 A The Title and Content elements B The Content and TOC elements C The Title and TOC elements D The Title, Content and TOC elements
Gate 2007-IT
Question 80 Explanation:
Note: Out of syllabus.
 Question 81
The following table shoes the time between failures for a software system The reliability of the system for one hour of operation assuming an exponential model is
 A 0.45 B 0.63 C 0.84 D 0.95
Gate 2007-IT
Question 81 Explanation: The probability or reliability that the product will work for a defined period of time without failure is given by Question 83
In the simplified flowchart given below, the shaded boxes represent code that is executed during a test case. The Branch coverage is
 A 3/4 B 2/3 C 1/2 D 3/8
Gate 2007-IT
Question 83 Explanation:
Note: Out of syllabus.
 Question 84

Consider the CPM activity chart where an arc connecting two milestones is labeled with a task identifier and the time taken in days. For example in order to go from A to B, task T1 takes 180 days. A dashed line depicts an additional dependency that is equivalent to a zero time task. The set of activities that lie on the critical path are

 A T1, T2, T8, T10 B T1, T3, T8, T10 C T1, T2, T3, T4, T5, T6, T7, T8, T9, T10 D T1, T4, T5, T7, T8, T10
Gate 2007-IT
Question 84 Explanation:
Note: Out of syllabus.
 Question 85
Consider the following pseudo-code:
``` IF ((A > B) AND (C > D)) THEN
A = A + 1
B = B + 1
ENDIF
```
The cyclomatic complexity of the pseudo-code is
 A 2 B 3 C 4 D 5
Gate 2007-IT
Question 85 Explanation:
Note: Out of syllabus.
 Question 86
The contents of the text file t1 txt containing four lines are as follows : a1 b1 a2 b2 a3 b2 a4 b1 The contents of the text file t2 txt containing five lines are as follows : a1 c1 a2 c2 a3 c3 a4 c3 a5 c4 Consider the following Bourne shell script :
``` awk - F '  '  ' {Print \$1, \$2} ' t1.txt |
while read a b ; do
awk -v aV = \$ a - v by = \$b  - F ' '
aV = = \$1 (print aV, bV, \$2 ) ' t2.txt
done
```
Which one of the following strings will NOT be present in the output generated when the above script in run? (Note that the given strings may be substrings of a printed line.)
 A "b1 c1" B "b2 c3" C "b1 c2" D "b1 c3"
Gate 2007-IT
Question 86 Explanation:
Note: Out of syllabus.
 Question 87
The cyclomatic complexity of the flow graph of a program provides
 A an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at most once B a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at most once C an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once D a lower bound for the number of tests that must be conducted to ensure that all statements have been executed at least once
Gate 2006-IT
Question 87 Explanation:
Note: Out of syllabus.
 Question 88
With respect to software testing, consider a flow graph G with one connected component. Let E be the number of edges, N be the number of nodes, and P be the number of predicate nodes of G. Consider the following four expressions:
1. E - N + P
2. E - N + 2
3. P +  2
4. P + 1
The cyclomatic complexity of G is given by
 A 1 or 3 B 2 or 3 C 2 or 4 D 1 or 4
Gate 2006-IT
Question 88 Explanation:
Note: Out of syllabus.
 Question 89

A software program consists of two modules M1 and M2 that can fail independently, but never simultaneously. The program is considered to have failed if any of these modules fails. Both the modules are ‘repairable’ and so the program starts working again as soon as the repair is done. Assume that the mean time to failure (MTTF) of M1is T1 with a mean time to repair (MTTR) of R1. The MTTF of M2 is T2 with an MTTR of R2. What is the availability of the overall program given that the failure and repair times are all exponentially distributed random variables?

 A B C D Gate 2006-IT
Question 89 Explanation:
Note: Out of syllabus.
 Question 90
Consider the following structure chart diagram. The boxes have function names embedded in them, while the variables are indicated along the arcs. Given below are a set of statements relevant to the above diagram. I. F3 and F6 can be in the same module. II. F4 and F6 can be in the same module. III. A4 is both an output and a control variable. IV. It is incorrect to pass A1 as data and use it as a control variable. Which combination of these statements is TRUE?
 A III and IV B I and IV C II and IV D I, II and IV
Gate 2006-IT
Question 90 Explanation:
Note: Out of syllabus.
 Question 91
Consider the following XML DTD describing course information in a university:
```<!ELEMENT Univ (Course+, Prof+)>
<!ELEMENT Course (Title, Eval*)>
<!ATTLIST Course Number ID #REQUIRED Instructor IDREF #IMPLIED>
<!ELEMENT Title (#PCDATA)>
<!ELEMENT Eval (#PCDATA)>
<!ATTLIST Eval Score CDATA #REQUIRED>
<!ELEMENT Prof EMPTY>
<!ATTLIST Prof Name ID #REQUIRED Teaches IDREF #IMPLIED>
```
What is returned by the following XQuery? let \$as := / /@Score for \$c in /Univ/Course[Eval] let \$cs := \$c/Eval?@Score where min(\$cs) > avg(\$as) return \$c
 A The professor with the lowest course evaluation B Professors who have all their course evaluations above the university average C The course with the lowest evaluation D Courses with all evaluations above the university average
Gate 2006-IT
Question 91 Explanation:
Note: Out of syllabus.
 Question 92
Consider the following program module:
```void swap(float* A1, float* A2)
{
float temp;
if (*A1 = = *A2) return;
temp = *A1;
*A1 = *A2;
*A2 = temp;
return;
}
```
The program volume for the above module using Halstead's method is
 A 60 B 63 C 66 D 69
Gate 2006-IT
Question 92 Explanation:
Note: Out of syllabus.
 Question 93
```void swap(float* A1, float* A2)
{
float temp;
if (*A1 = = *A2) return;
temp = *A1;
*A1 = *A2;
*A2 = temp;
return;
}
```
The program effort for the above module using Halstead's method is
 A 315 B 330 C 393 D 403
Gate 2006-IT
Question 93 Explanation:
Note: Out of syllabus.
 Question 94
A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, and pessimistic estimates of the phase completion times in days, for Pl, P2, P3 and P4 are, respectively, (11, 15, 25), (7, 8, 15), (8, 9, 22), and (3, 8, 19). The critical path for the above project and the slack of P2 are, respectively,
 A P1-P2-P4, 1 day B P1-P3-P4, 1 day C P1-P3-P4, 2 days D P1-P2-P4, 2 days
Gate 2006-IT
Question 94 Explanation:
Note: Out of syllabus.
 Question 95
A software project has four phases P1, P2, P3 and P4. Of these phases, P1 Is the first one and needs to be completed before any other phase can commence. Phases P2 and P3 can be executed in parallel. Phase P4 cannot commence until both P2 and P3 are completed. The optimistic, most likely, and pessimistic estimates of the phase completion times in days, for Pl, P2, P3 and P4 are, respectively, (11, 15, 25), (7, 8, 15), (8, 9, 22), and (3, 8, 19). The costs (in Rupees per day) of crashing the expected phase completion times for the four phases, respectively, are 100, 2000, 50, and 1000. Assume that the expected phase completion times of the phases cannot be crashed below their respective most likely completion times. The minimum and the maximum amounts (in Rupees) that can be spent on crashing so that ALL paths are critical are, respectively.
 A 100 and 1000 B 100 and 1200 C 150 and 1200 D 200 and 2000
Gate 2006-IT
Question 95 Explanation:
Note: Out of syllabus.
 Question 96
A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?
 A 6 B 4 C 3 D 2
Gate 2005-IT
Question 96 Explanation:
2, -3, 2, -1, 2
f(Ø)=0 and f(push(S,i) = max(f(S),0) + i;
Initially stack is empty and for empty stack 0 is given.
f(push(0,2)) = max(f(Ø),0) + 2 = max(Ø,0) + 2 = 2
f(push(2,-3)) = max(2,0) + (-3) = 2 - 3 = -1
f(push(-1,2)) = max(-1,0) + 2 = 0 + 2 = 2
f(push(2,-1)) = max(2,0)+ (-1) = 2 - 1 = 1
f(push(1,2)) = max(1,0) + 2 = 1 + 2 = 3
So, 3 will be the answer.
∴ Option C is correct.
 Question 97
Amongst the ACID properties of a transaction, the 'Durability' property requires that the changes made to the database by a successful transaction persist
 A Except in case of an Operating System crash B Except in case of a Disk crash C Except in case of a power failure D Always, even if there is a failure of any kind
Gate 2005-IT
Question 97 Explanation:
Durability gurantees that once a transition has been committed, it will remain committed even in the case of a system failure.
 Question 98

In a data link protocol, the frame delimiter flag is given by 0111. Assuming that bit stuffing is employed, the transmitter sends the data sequence 01110110 as

 A 01101011 B 011010110 C 011101100 D 0110101100
Gate 2004-IT
Question 98 Explanation:
In the data link layer, bits stuffing is employed then bit stuffing is done using the flag delimiter. If there is a flag of n bits then we will compare the data sequence with the flag and for every n-1 bits matched found, a bit 0 is stuffed in the data sequence.
Thus using the above logic,
Delimiter flag: 0111
Data sequence: 01110110
So, for a flag of 4 bits we will compare data sequence with a pattern of 3 bits, i.e., 011.
0 1 1 0 1 0 1 1 0 0
In the above pattern the underlined bits are found matched. Hence, 0 in italics is stuffed. Thus resulting in the data sequence as 0110101100 which is option (D).
 Question 99
The root directory of a disk should be placed
 A at a fixed address in main memory B at a fixed location on the disk C anywhere on the disk D at a fixed location on the system disk E anywhere on the system disk
Algorithms       Gate-1993
Question 99 Explanation:
Root directory can points to the various user directories. Then they will be stored in a way that user can't be easily modify them. Then they should be at fixed location on the disk.
There are 99 questions to complete.