GATE 2020 Computer Science and Information Technology Previous Year Paper

GATE 2020 Computer Science and Information Technology Previous Year Paper

GENERAL APTITUDE 

Q.1 Raman is confident of speaking English _____ six months. He has been practicing regularly ________ the last three weeks

(a) during, for

(b) for, since

(c) within, for

(d) for, in 

Ans. (c) 

• ‘Within’ is a preposition that is used to express something that occurs inside a particular period of time. 
• ‘for’ is used here because 

(i) Sentence is in ‘present perfect continuous tense’. 

(ii) For is used when we talk about a period of time. 

 

Q.2 Select the word that fits the analogy 

Cook : Cook :: Fly : 

(a) Flighter 

(b) Flew 

(c) Flyer 

(d) Flying 

Ans. (c) 

Flyer: Relation is Verb : Noun 

One who cooks is a cook and one who flies any aircraft is a flyer. 

 

Q.3 This knowledge of the subject was excellent but his class room performance was ____. 

(a) Extremely poor 

(b) Praise worthy 

(c) Desirable 

(d) Good 

Ans. (a) 

‘But’ is used for introducing an idea which contrasts with the statement that has been already said. 

 

Q.4 Mode a and e are toll booths which costs 200 and all other toll both b, c, d, f costs only 100. Minimum cost for each from 1 to 2. (Path was given) 

Ans. (*) 

 

Q.5 Goods services tax (GST) is an indirect tax introduced in India in 2014 that is imposed on the supply of goods and services used and it subsumes all indirect taxes except few. It is a district based tax imposed on goods and services used; it is not imposed at the point of origin from where goods come. GST also has a few components specific to state government, central government and UTs? Which one of the following can be inferred from the given passage? 

(a) GST includes all indirect taxes 

(b) GST is imposed on the product of goods and services 

(c) GST imposed at point of usage of goods and services 

(d) GST does not has a component specific for UT 

Ans. (c) 

 

Q.6 If P = 3, R = 27, T = 243, then Q + S = 

(a) 80 

(b) 110 

(c) 90 

(d) 40 

Ans. (c) 

 

Q.7 The total revenue of a company during 2014-2018 is shown in a bar graph. The total expenditure of the company in each year is 500 million rupees. The aggregate profit/ loss percentage on the total expenditure of the company during 2014-2018 is ______. 

Ans. (20% profit) 

Total expenditure = 2500 million 

Total revenue = 3000 million 

So, profit % = 500/2500 × 100 = 20% 

 

Q.8 The figure below shows an angular ring with outer inner radii b and a. The angular space has been pointed in the form of a blue colour circle touching the outer and inner peripheral gular space. If a maximum n number of circles can be pointed then the unpainted area available in angular space is ________. 

(a) π[(b² – a²) -n (b – a)²]

(b) π[(b² – a²) -n (a/2)²]

(c) π[(a² – b²) -n (b/2)²]

(d) π[(b² – a²) -n (b-a/2)²]

Ans. (d) 

The area of unpainted region will be 

π[(b² – a²) -n (b – a/2)²]

 

Q.9 The straight lines are drawn perpendicular to each other in the XY plane. The angle α and β are acute angles made by line as with x-axis then α + β = ? 

(a) 180° 

(b) 90° 

(c) 60° 

(d) 120° 

Ans. (b) 

 

Q.10 In a decoder with in input lines and n output lines, then 1 KB RAM is given and now find (m + n). 

Ans. (1034) 

We need 2¹⁰ outputs to map 1 kB RAM. 

For this we need 10 × 2¹⁰ decoder. 

Here m = 10 and n = 2¹⁰ 

m + n = 1034 

 

Q.11 Given main memory with single level paging main memory access time 100 ns TLB access time 20 ns. TLB hit ratio 95% page fault rate 10% and when there is page fault in 20% cases it uses write back and retrieve page from secondary memory with 5000 ns access time calculate average access time? With upto 1 decimal place. 

Ans. (*) 

 

Q.12 Consider the following statements: 

I. Daisy chain uses priorities for selecting devices. 

II. When there is vectored interrupt and polling is used for getting an address. 

III. Polling processor uses periodically checks status bit to check if interrupt needs to process. 

IV. DMA access processor and DMA controller can simultaneously access at the same  time. 

(a) I and II only 

(b) I and III only 

(c) I, II and IV only 

(d) I, and IV only 

Ans. (b) 

 

Q.13 A non-pipeline processor having 2.5 GHz clock frequency. Where each instruction takes 5 cycles and when this processor utilizes a same 5 stage pipeline having 2 GHz clock frequency and 30% are memory instruction 60% are ALU instruction and remaining are branch instruction. Given that 5% memory instruction takes 50 stall cycles and 50% branch instruction takes 2 cycles then what will be the speed up when the pipeline processor is used over the non-pipeline processor ________. 

Ans. (2.16) 

 

Q.14 A 16-bit instruction having two type of instruction i.e. R-type and I-type where 16-bit instruction supports 64 registers set. Now I-type of instruction has 1 register field and 4-bit immediate field. R-type instruction supports 2 register address fields and given that there are 8 different I-type instructions then how many different R-types of instruction are possible _______. 

Ans. (14) 

Given, 16 bit instruction and 64 registers 

I type: 

R type: 

1. Primitive instruction 

R-type: 

2. Number of operations possible = 2⁴ = 16 3. Number of tree opcodes = (16 – x) 

Assume x is the number of R-type instructions existed. 4. Number of I-type instruction possible = (16 – x) × 2² 8=64 – 4x 4x = 64 – 8 = 56 

x = 56/4

^{⇒ 14} 

 

Q.15 The number of permutations of the characters LILAC if no characters appears in its the original position if two Ls are indistinguishable is _______. 

Ans. (12) 

Number of derangements. 

Since both L’s are indistinguishable. 

First L’s can be arranged remaining 3 positions in ³C₂ ways. 

[i.e., _ L _ L _ or _ L _ L _ or _ L _ _ L _] 

For each of these cases remaining 3 letters can be deranged in 2 × 2! ways = 4 ways 

[i.e., L L C can lake only 1 or 3 positions → 2 ways. For each of these IA can be arranged in remaining 2 positions in 2 ways]. 

Number of derangements = ³C₂ × 2 × 2! = 12 

 

Q.16 A = {1, 2, 3}. What is the probability of getting reflexive relation on A. By choosing any relation randomly. 

Ans. (0.125) 

 

Q.17 A graph G K_{3, 4} is given. Suppose, a vertex ‘S’ is added which is adjacent to every vertex in K_{3, 4} then the minimum number of edge-color required ________. 

Ans. (7)

Minimum number of edge-colors required = 3 + 4 = 7. 

 

Q.18 Rank(M) is rank of matrix M and det(M) is determinant of matrix M then 

1.Rank(AB) = Rank(A) ⋅ Rank(B)

2.det(AB) = det(A) ⋅ det(B)

3.Rank(A + B) ≤ Rank(A) + Rank(B)

4.det(A + B) ≤ det(A) + det(B)

Which of the above statements is correct?

(a) 2 and 3

(b) 3 and 4

(c) 1 and 2

(d) 1 and 4 

Ans. (a) 

Statement 2 and 3 are correct statements directly based on properties of matrices. 

 

Q.19 A group with 35 elements has subgroups. The maximum size of the proper subgroup is ________. 

Ans. (7) 

Size of group = Ο(G) = 35 

Let H be subgroup of G 

∴ Ο(H)⏐Ο(G) 

Possible orders of H are 1, 5, 7, 35 

Size of largest possible proper subgroup = 7. 

 

Q.20 Which of the following is not valid? 

(a) ∃x (p(x) → w) ≡ ∀x p(x) → w 

(b) ∀x (p(x) → w) ≡ ∀x p(x) → w 

(c) ∃x (p(x) ∧ w) ≡ ∃x p(x) ∧ w 

(d) ∀x (p(x) ∨ w) ≡ ∀x p(x) ∨ w 

Ans. (b) 

∀x (p(x) → w) ≡ ∀x p(x) → w is wrong 

Since ∀x [p(x) → w] 

≡ ∀x [¬p(x) ∨ w] 

≡ ∀x (¬p(x) ∨ w

≡ ¬(∃x p(x)) ∨ w

≡ ∃x p(x) → w 

 

Q.21 Given vertex set (v₁, v₂, v₃, ….. v₁₀₀), the edge weight is ⏐v_i – v_j ⏐ where i ≤ i ≤ j ≤ 100 then the weight of the minimum spanning tree is ________. 

Ans. (99) 

 

Q.22 T(n) = T(n^1/a) + 1, T(b) = 1 find T(n) 

(a) θ(log_b log_an)

(b) θ(log_a log_bn) 

(c) θ(log_abn) 

(d) θ(log₂n) 

Ans. (a) 

 

Q.23 What is the worst case time complexity of inserting n elements in empty linked list in the sorted order? 

(a) n 

(b) n logn 

(c) n² 

(d) n² logn 

Ans. (b) 

Insert element at the beginning of linked list, take Ο(1) 

 

Q.24 In the AVL tree n element are there what is the time complexity of inserting other n² elements? 

(a) n² 

(b) Ο(n² logn) 

(c) Ο(n) 

(d) Ο(n logn) 

Ans. (b) 

AVL with n element: [height balanced [–1, 0, +1] BST] 

logn level due to balanced BST. 

(i) Every insertion of element: 

logn: Find place to insert. 

logn: If property is not satisfied do rotation. 

∴ n² element insertion: 

For 1 element ≡ 2 logn 

So, for n² element ≡ Ο(n² logn) 

 

Q.25 There are n elements in the balanced binary search tree. What is the time complexity to report the k elements in the range [a, b]? 

(a) Ο(logn + k) 

(b) Ο(k logn) 

(c) Ο(k) 

(d) Ο(kn) 

Ans. (a) 

Let a = 16, b = 42 

16: Find the ‘16’ element in the BST = Ο(logn) 

42: Find the ‘42’ element in the BST = Ο(logn) 

[16, 42]: Inorder sorted element between 

16 to 42 {16, 18, 19, 20, 25, 30, 35, 40, 42} ⇒ requires Ο(k) time for k element 

So total time: Ο(2 logn + k) ≡ Ο(logn + k) 

 

Q.26 Binary min-heap has 1023 elements. Find the number of comparisons required to find the maximum element? 

Ans. (511) 

Number of element = [1023/2] = 512

No bubble sort requires 511 comparisons. 

 

Q.27 Let A, B, C be the inputs which give output Z as shown in below figure. The minterms required to represent the output function Z(A, B, C) is ________. 

(a) ∑m(1, 3, 5, 6, 7) 

(b) ∑m(1, 4, 5, 6, 7) 

(c) ∑m(1, 2, 3, 6, 7) 

(d) ∑m(4, 5, 6, 7) 

Ans. (b)

∴ Z(A, B, C) = A + BC 

K-map of the output Z is 

∴ Z(A, B, C) = ∑m(1, 4, 5, 6, 7) 

 

Q.28 You are given accumulator and memory of 32 registers in between then there is a multiplexer the number of select lines in multiplexer. 

Ans. (5)

Number of registers = n = 32 Required multiplexer size is n : 1 i.e. 32 : 1 No of select lines required to the multiplexer = m ∴ m = log₂ n 

m = log₂ 32 m=5 

 

Q.29 

SELECT S.sno, S.sname

FROM Supplier S, catalog C

WHERE S.sno = C.sno AND

cost > (SELECT AVG (cost)

FROM Catalog

WHERE pno = ‘P₄’ GroupBy pno);

Number of rows returned by above query ________.

Ans. (4) 

SELECT S.sno, S.sname

FROM Supplier S, catalog C

WHERE S.sno = C.sno AND

cost > (SELECT AVG (cost)

FROM Catalog

WHERE pno = ‘P₄’ GroupBy pno);

Q.30 Given relation is in 3NF but not in BCNF 

(a) because for non-trivial FD x → A, with x is not super key and A is prime attribute. 

(b) because for non-trivial FD x → A, with x is not super key and A is not prime attribute, x is not a proper subset of key. 

(c) because for non-trivial FD x → A with x is not super key and A is not prime attribute, x is a proper subset of the key. 

(d) None of these 

Ans. (a) 

 

Q.31 For a database we are using B⁺ tree indexing with 1 million records in the database, each record fits in one block. Block size is 8 KB and search key size is 12 bytes, block pointer size is 8 bytes. Minimum number of block access required for database record is ________. 

Ans. (4) 

Total = 3 + 1 = 4 block access 

 

Q.32 Which of the following many-to-one rules of weak-entity set in an ER diagram? 

(a) Oval shape with double/bold borders 

(b) Diamond shape with double/bold borders 

(c) Rectangular shape with double bold/borders 

(d) Oval shape with identifier underlined 

Ans. (b) 

Diamond shape with double/bold borders 

 

Q.33 TCP connection maximum segment size = 2 KB is starting at t = 0 and threshold is 32 KB and calculates sender window size at (t + 60 ms) where (RTT = 6 ms) given 50 KB as maximum segment. 

Ans. (44) 

 

Q.34 A web page has some text and 4 small size images, used non-persistent HTTP connection, then the number of HTTP connections required ________. 

Ans. (5) 

In non persistent HTTP for every object there is a TCP connection required. Hence 1 TCP connection for text and 4 TCP connections for images required. 

 

Q.35

L₁ = {wxyx⏐w, x, y ∈ (0 + 1)⁺} 

L₂ = {xy⏐x, y, ∈ (a + b)*, ⏐x⏐=⏐y⏐, x ≠ y}

(a) L₁ is not regular but L₂ is CFL

(b) L₁ is CFL and L₂ is not CFL

(c) L₁ and L₂ are not CFL

(d) L₁ is regular and L₂ is CFL 

Ans. (d) 

L₁ is regular and L₂ is CFL. 

In L₁ putting x as 0 and 1 we get a subset 

w0y0 + w1y1 = (0 + 1)⁺ 0 (0 + 1)⁺ 0 + (0 + 1)⁺ 1(0 + 1)⁺ 1 

Now by putting x as 00, 01, 10, 11 we can show that above minimal regular expression covers all such things and hence above expression is not a subset but is equal to given language. Since we wrote regular expressions for L₁, it is regular. 

 

Q.36 S → aSB⏐d B → b “aaadbbb” using bottom up parser, how many steps required? 

Ans. (7) 

S → aSB

→ aaSBB [S → aSB]

→ aaaSBBB [S → aSB]

→ aaadBBB [S → d]

→ aaadbBB [B → b]

→ aaadbbB [B → b]

→ aaadbbb [B → b]

Total 7 steps required

 

Q.37 Which of the following regular expressions will contain a set of all binary strings containing an odd number of 1’s?

(a) 1 0* (0* 1 0* 1 0*)* 

(b) 0* (0* 1 0* 1 0*)* 1 0* 

(c) (0* 1 0* 1 0*)* 0* 1 

(d) ((0 + 1)* 1 + (0 + 1)*) 1 0* 

Ans. (b) 

Try to find a counterexample to show the expression incomplete. 

(a) is incorrect because it forces the string to start with “1” and hence cannot generate 

a string like “01”, which has an odd number of ones. 

(c) is incorrect because it forces it to end with “1” and hence cannot generate “10”. 

(d) is same as (0 + 1)*10* which will generate some wrong strings like “110” which 

has an even number of 1’s. It is a superset and hence not correct. 

(b) is same as (0* 1 0* 1 0*)* 1 0* which is correct. 

 

Q.38 Given L = {aⁿ⏐n ≥ 0} ∪ {aⁿbⁿ⏐n ≥ 0}. Tell us where L is 

(a) DCFL 

(b) Non-DCFL 

(c) Context-free language 

(d) CFL but not DCFL 

Ans. (a) 

{aⁿbⁿ⏐n ≥ 0} is a well known DCFL. 

{aⁿ⏐n ≥ 0} is a well known regular language.

So, L = DCFL ∪ Regular = DCFL by closure properly 

DCFL is the strongest correct answer. 

 

Q.39 Given four languages, which of the following are undecidable?

Where <M> denotes encoding of a Turing Machine M 

L₁ = {<M>⏐L(M) = φ} 

L₂ = {<M>⏐L(M) is non recursive} 

L₃ = {< M, w, q >⏐M will visit the state q when M execute on w and take exactly 100 steps]

L₄ = {<M>⏐L(M) accept strings where strings length is at least 20}

Which one of the following are/in undecidable? 

(a) L₁ and L₂ 

(b) L₂ and L₃ 

(c) L₁ and L₄ 

(d) L₁, L₂ and L₃ 

Ans. (d) 

(i) L(M) = φ is emptiness problem of TM, which is undecidable, by Rice’s theorem since 

it is a non-trivial problem. 

(ii) L(M) = non-recursive is also a non-trivial question, since some TM can accept non- recursive language and some may not, so by Rice’s theorem it is undecidable. 

(iii) Rice’s theorem applied and hence L₃ is undecidable. 

(iv) With UTM we can check if M accepts a string by 100 steps. So L₄ decidable L₁, L₂ and L₃ are undecidable. 

 

Q.40 Which of the following is true? 

I. If L₁ ∪ L₂ is regular, then both L₁ and L₂ must be regular. 

II. The class of regular language is closed under infinite union. 

(a) I only 

(b) Both I and II 

(c) II only 

(d) Neither I nor II 

Ans. (d) 

I is false, since {a_nb_n} ∪ {a_nb_n} = ∑* which is regular, but {anbn} not regular. 

II is false, since many infinite languages can be broken into individual strings which will be an infinite union of finite languages. So if regular is closed under infinite union, then all infinite language will become regular, which is untrue. So II is also false. 

 

Q.41 The number of states in a minimal DFA accepting all strings on {a, b}* with number of a’s multiple of 2 but not multiple of 3 is ________. 

Ans. (6) 

L = {w ∈ {a, b}*⏐n_a(w) = multiple of 2 but not 3} 

Let, L₁ = {w ∈ {a, b}*⏐n_a(w) = multiple of 2} 

L₂ = {w ∈ {a, b}*⏐n_a(w) = multiple of 3} 

Given language is L₁ – L₂ = L₁ ∩ L₂c 

We can make a DFA for L₁ with 2 states. 

We can make a DFA for L₂c with 3 states. 

Then use product automata construction to get a DFA for L₁ – L₂ = L₁ ∩ L₂c with 6 states. Since neither of the L₁ or L₂c has a trap state, the resulting product automata also has no trap state. 

So, min DFA has 6 states. 

Alternate solution: 

We can directly design DFA for multiple of 2 but not 3 with 6 states as shown below with 6 states by accepting 2a’s, 4a’s but not 6a’s in trap. 

 

Q.42 Preorder of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Then what would be its post order. 

(a) 11, 12, 10, 16, 19, 18, 20, 15 

(b) 12, 10, 16, 19, 18, 20, 15, 11 

(c) 15, 16, 12, 19, 11, 18, 20, 15

(d) 15, 20, 10, 16, 19, 18, 11, 12 

Ans. (a) 

Post order: 11, 12, 10, 16, 19, 18, 20, 15 

 

Q.43 Consider the codes given below: 

fun 1 (int n)

{

static int i = 0;

if(n > 0)

{

i++;

fun1(n – 1);

}

return (i);

}

fun2 (int n)

{

static int i = 0;

if(n > 0)

{

i = i + fun1(n);

fun2(n – 1);

}

return i;

}

What the program will return when fun2(5) is called ________

Ans. (55) 

 

Q.44 Consider the C program: 

Arr [4] [5] = {{1, 2, 3, 4, 5} 

                    {6, 7, 8, 9, 10} 

                    {11, 12, 13, 14, 15} 

                     {16, 17, 18, 19, 20}} 

printf(“%d”, *(*(a + **a) + 3)) 

The output of the above C program is ________. 

Ans. (19) 

 

Q.45 Consider to semaphore a and b whose initial values are 1 and 0 respectively. Count is the shared variable which is not used in code section P: 

Code section P 

wait (a); 

if (count == n); signal(b); 

signal(a); wait(b); signal(b); 

Code section Q 

What does this code achieve? 

(a) At any time there will be 2 processes in Q. 

(b) All processes will run P and then enter into Q. 

(c) (n – 1) process will run P and then Q. 

(d) All processes run P in a mutually exclusive manner. 

Ans. (a) 

 

Q.46 Assume all the processes arrive at time 0. Find the absolute difference between average Turnaround Time (TAT) in SJF and Round Robin if time quantum 4 ns 

Ans. (5.25) 

Turn Around Time (TAT) = (21 – 0) + (13 – 0) + (2 – 0) + (6 – 0) 

Average TAT = ⁴²/₄ = 10.5 

Turn Around Time (TAT) = (18 – 0) + (21 – 0) + (10 – 0) + (14 – 0) 

= 18 + 21 + 10 + 14 

Average TAT = ⁶³/₄ = 15.75 

Hence, ⏐SJF (TAT) – RR(TAT)⏐ 

= ⏐10.5 – 15.75⏐ = 5.25 

 

Q.47 Consider the following state changes for a preemptive scheduling OS: 

I. Ready to running 

II. Running to ready 

III. Blocked to running 

IV. Blocked to ready Which of the above statement 

(a) I and II only 

(b) I only 

(c) I and III only 

(d) I, II and IV only 

Ans. (d) 

 

Q.48 A new process needs to be allocated memory. The size of the process cannot be exactly fit in available holes. If memory is allocated to any of the available holes, then a new smaller hole will be created. Which of the following options is correct in this context? 

(a) The size of hole created using best fit is never greater than size created by first fit 

(b) The size of hole created using best fit is never greater than size created by next fit 

(c) The size of hole created using next fit is never greater than size created by first fit 

(d) The size of hole created using worst fit is never greater than size created by first fit 

Ans. (a) 

 

Q.49 Which of the following statements are TRUE? 

1. Symbol table is accessed only during lexical analysis and syntax analysis. 
2. Compilers for programming L that support recursion necessarily need heap storage for memory allocation in the runtime environment. 
3. Errors violating the condition any variable must be declared before its use are detected during syntax analysis. 

(a) None of 1, 2, 3 

(b) 1 and 3 

(c) 2 only 

(d) 1 only 

Ans. (a) 

 

Q.50 Consider A → PQ, A → XY are production of a grammar P, Q, X, Y, A are non-terminals, s is synthesized attribute, i is inherited attribute 

Rule 1: P . i = A. i + 2, Q . i = P . i + A . i, A . s = P . s + Q . s 

Rule 2: X . i = A. i + Y . s and Y . i = X . s + A . i 

Which of the following is TRUE? 

(a) Only Rule 1 is L attributed 

(b) Rule 1 and Rule 2 are L attributed 

(c) Neither Rule 1 Nor Rule 2 

(d) Only Rule 2 is L attributed 

Ans. (a)