GATE 2020 CS – Previous Year Questions with Solutions
All 65 questions of GATE 2020 CS with answers and explanations. Read each question, then practise it by topic or as a full paper.
65 questions worth 100 marks in all (30 1-mark, 35 2-mark). Subjects covered: General Aptitude (10), Engineering Mathematics (8), Programming and Data Structures (8), Computer Organization and Architecture (7), Theory of Computation (6), Operating System (6), Algorithms (5), Databases (5).
Practise this paper in The GATE Grind →
- Question 1 – Raman is confident of speaking English six months as he has been practising regularly the last three weeks.
- Question 2 – His knowledge of the subject was excellent but his classroom performance was .
- Question 3 – Select the word that fits the analogy: Cook : Cook :: Fly :
- Question 4 – The dawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on…
- Question 5 – There are multiple routes to reach from node 1 to node 2, as shown in the network. The cost of travel on an edge between two nodes is given in rupees.…
- Question 6 – Goods and Services Tax (GST) is an indirect tax introduced in India in 2017 that is imposed on the supply of goods and services, and it subsumes all…
- Question 7 – If P = 3, R = 27, T = 243, then Q + S = .
- Question 8 – The figure below shows an annular ring with outer and inner radii as b and a, respectively. The annular space has been painted in the form of blue…
- Question 9 – Two straight lines are drawn perpendicular to each other in X-Y plane. If and are the acute angles the straight lines make with the X-axis, then + is…
- Question 10 – The total revenue of a company during 2014-2018 is shown in the bar graph. If the total expenditure of the company in each year is 500 million rupees,…
- Question 11 – Consider the functions I. e-x II. x2- x III. x3+1 Which of the above functions is/are increasing everywhere in [0,1]?
- Question 12 – For parameters a and b, both of which are (1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is
- Question 13 – Consider the following statements. I. Daisy chaining is used to assign priorities in attending interrupts. II. When a device raises a vectored…
- Question 14 – Consider the following data path diagram. Consider an instruction: R0 ← R1 + R2. The following steps are used to execute it over the given data path.…
- Question 15 – The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?
- Question 16 – What is the worst case time complexity of inserting n2 elements into an AVL-tree with n elements initially?
- Question 17 – Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
- Question 18 – Consider the following statements. I. If L 1 L 2 is regular, then both L 1 and L 2 must be regular. II. The class of regular languages is closed under…
- Question 19 – Consider the following statements. I. Symbol table is accessed only during lexical analysis and syntax analysis. II. Compilers for programming…
- Question 20 – Consider the language L=\an n 0\\anbn n 0\ and the following statements. I. L is deterministic context-free. II. L is context-free but not…
- Question 21 – Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory…
- Question 22 – Consider the following statements about process state transitions for a system using preemptive scheduling. I. A running process can move to ready…
- Question 23 – Consider a relational database containing the following schemas. Catalogue(sno, pno, cost): (S1,P1,150), (S1,P2,50), (S1,P3,100), (S2,P4,200),…
- Question 24 – Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?
- Question 25 – Consider the following statements about the functionality of an IP based router. I. A router does not modify the IP packets during forwarding. II. It…
- Question 26 – What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?
- Question 27 – Let R be the set of all binary relations on the set \1,2,3\. Suppose a relation is chosen from R at random. The probability that the chosen relation…
- Question 28 – Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is .
- Question 29 – A multiplexer is placed between a group of 32 registers and an accumulator to regulate data movement such that at any given point in time the content…
- Question 30 – If there are m input lines and n output lines for a decoder that is used to uniquely address a byte addressable 1 KB RAM, then the minimum value of…
- Question 31 – A direct mapped cache memory of 1 MB has a block size of 256 bytes. The cache has an access time of 3 ns and a hit rate of 94%. During a cache miss,…
- Question 32 – Consider the following C program. The output of the program is .
- Question 33 – Consider a double hashing scheme in which the primary hash function is h 1(k)=k 23, and the secondary hash function is h 2(k)=1+(k 19). Assume that…
- Question 34 – Consider the following grammar. S aSB d B b The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is .
- Question 35 – Assume that you have made a request for a web page through your web browser to a web server. Initially the browser cache is empty. Further, the…
- Question 36 – Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M. L 1=\ M L(M)=\ L 2=\ M,w,q M on input w…
- Question 37 – Let A and B be two n n matrices over real numbers. Let rank(M) and (M) denote the rank and determinant of a matrix M, respectively. Consider the…
- Question 38 – Consider the Boolean function z(a,b,c). Which one of the following minterm lists represents the circuit given above?
- Question 39 – Consider three registers R1, R2, and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the…
- Question 40 – A computer system with a word length of 32 bits has a 16 MB byte-addressable main memory and a 64 KB, 4-way set associative cache memory with a block…
- Question 41 – Let G=(V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted…
- Question 42 – Consider the following languages. L 1=\wxyx w,x,y(0+1)+\ L 2=\xy x,y(a+b)*, x = y , x y\ Which one of the following is TRUE?
- Question 43 – Consider the productions A → PQ and A → XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i…
- Question 44 – Each of a set of n processes executes the following code using two semaphores a and b initialized to 1 and 0, respectively. Assume that count is a…
- Question 45 – Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given…
- Question 46 – Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?
- Question 47 – Consider a schedule of transactions T 1 and T 2. In time order (RX = Read(X), WX = Write(X)): T1:RA, T2:RB, T2:WB, T1:RC, T2:RD, T1:WD, T2:WC, T1:WB,…
- Question 48 – An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service…
- Question 49 – Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x.
- Question 50 – Let G=(V,E) be a directed, weighted graph with weight function w:ER. For some function f:VR, for each edge (u,v) E, define w'(u,v) as…
- Question 51 – In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the…
- Question 52 – The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L's are indistinguishable, is…
- Question 53 – Consider a non-pipelined processor operating at 2.5 GHz. It takes 5 clock cycles to complete an instruction. You are going to make a 5-stage pipeline…
- Question 54 – A processor has 64 registers and uses 16-bit instruction format. It has two types of instructions: I-type and R-type. Each I-type instruction contains…
- Question 55 – For n>2, let a\0,1\n be a non-zero vector. Suppose that x is chosen uniformly at random from \0,1\n. Then, the probability that i=1na ix i is an odd…
- Question 56 – Consider the following C functions. The return value of fun2(5) is .
- Question 57 – Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the…
- Question 58 – Consider the following C functions. The value returned by pp(3,4) is .
- Question 59 – Consider a graph G=(V,E), where V=\v 1,v 2,,v 100\, E=\(v i,v j) 1 i<j 100\, and weight of the edge (v i,v j) is i-j . The weight of minimum spanning…
- Question 60 – Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round…
- Question 61 – Consider the following language. L=\x\a,b\* number of a's in x is divisible by 2 but not divisible by 3\ The minimum number of states in a DFA that…
- Question 62 – Graph G is obtained by adding vertex s to K 3,4 and making s adjacent to every vertex of K 3,4. The minimum number of colours required to edge-colour…
- Question 63 – Consider a paging system that uses 1-level page table residing in main memory and a TLB for address translation. Each main memory access takes 100 ns…
- Question 64 – Consider a database implemented using B+ tree for file indexing and installed on a disk drive with block size of 4 KB. The size of search key is 12…
- Question 65 – Consider a TCP connection between a client and a server with the following specifications: the round trip time is 6 ms, the size of the receiver…