GATE CS 2020 (Forenoon)
65 questions · 100 marks · 180 minutes
GENERAL APTITUDE (GA)
- Q1Raman is confident of speaking English six months as he has been practising regularly the last three weeks.Verbal Aptitude · Grammar Rules (Prepositions, Conjunctions, Verb-Noun Agreement, Other Parts of Speech) · MCQ · 1 mark
- Q2His knowledge of the subject was excellent but his classroom performance was .Verbal Aptitude · Basic Vocabulary (Words, Idioms, Phrases in Context) · MCQ · 1 mark
- Q3Select the word that fits the analogy: Cook : Cook :: Fly :Analytical Aptitude · Analogy and Relationship Matching · MCQ · 1 mark
- Q4The dawn of the 21st century witnessed the melting glaciers oscillating between giving too much and too little to billions of people who depend on them for fresh water. The UN cli…Verbal Aptitude · Reading Comprehension · MCQ · 1 mark
- Q5There 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. Nodes 'a', 'b', 'c', 'd', 'e…Analytical Aptitude · Operational Puzzles and Systemic Reasoning · MCQ · 1 mark
- Q6Goods 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 indirect taxes except few. It…Verbal Aptitude · Reading Comprehension · MCQ · 2 marks
- Q7If P = 3 , R = 27 , T = 243 , then Q + S = .Quantitative Aptitude · Mathematical Operations (Powers, Exponents, Logarithms) · MCQ · 2 marks
- Q8The 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 colour circles touching the out…Quantitative Aptitude · Mensuration and Geometry · MCQ · 2 marks
- Q9Two 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 .Quantitative Aptitude · Mensuration and Geometry · MCQ · 2 marks
- Q10The 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, then the aggregate profit or…Quantitative Aptitude · Data Interpretation (Bar Graphs, Pie Charts, Histograms) · MCQ · 2 marks
MATHEMATICAL FOUNDATIONS
- Q11Consider the functions: I. e -x II. x 2 - x III. x 3 + 1 Which of the above functions is/are increasing everywhere in [0,1]?Calculus · Maxima and Minima Optimization Bounds · MCQ · 1 mark
- Q27Let 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 is reflexive (round off to…Discrete Mathematics · Sets, Relations, Functions, Partial Orders, Lattices · NAT · 1 mark
- Q28Let G be a group of 35 elements. Then the largest possible size of a subgroup of G other than G itself is .Discrete Mathematics · Algebraic Structures (Monoids, Groups) · NAT · 1 mark
- Q37Let A and B be two n n matrices over real numbers. Let rank(M) and det(M) denote the rank and determinant of a matrix M, respectively. Consider the following statements: I. rank(A…Linear Algebra · Matrices, Determinants, & Linear Equation Systems · MCQ · 2 marks
- Q49Which one of the following predicate formulae is NOT logically valid? Note that W is a predicate formula without any free occurrence of x .Discrete Mathematics · Propositional and First-Order Quantifier Logic · MCQ · 2 marks
- Q52The 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 .Discrete Mathematics · Combinatorics (Counting Rules, Summation Formulas) · NAT · 2 marks
- Q55For 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=1 n a i x i is an odd number is .Probability & Statistics · Random Variables & Sampling Rules · NAT · 2 marks
- Q62Graph 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 G is .Discrete Mathematics · Advanced Graph Bounds (Matching, Coloring Theorems) · NAT · 2 marks
CORE CS
- Q12For parameters a and b , both of which are (1) , T(n) = T(n 1/a ) + 1 , and T(b) = 1 . Then T(n) isAlgorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 1 mark
- Q13Consider the following statements: I. Daisy chaining is used to assign priorities in attending interrupts. II. When a device raises a vectored interrupt, the CPU does polling to i…Computer Organization and Architecture (COA) · I/O Interfaces (Interrupts & DMA Control Modes) · MCQ · 1 mark
- Q14Consider the following data path diagram. Consider an instruction: R0 R1 + R2. The following steps are used to execute it over the given data path. Assume that PC is incremented a…Computer Organization and Architecture (COA) · ALU, Control Unit Design, Data-Path Operations · MCQ · 1 mark
- Q15The 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?Data Structures · Binary Search Trees (BSTs) & Binary Heaps · MCQ · 1 mark
- Q16What is the worst case time complexity of inserting n 2 elements into an AVL-tree with n elements initially?Data Structures · Binary Search Trees (BSTs) & Binary Heaps · MCQ · 1 mark
- Q17Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · MCQ · 1 mark
- Q18Consider 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 infinite union. Which of the…Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- Q19Consider the following statements: I. Symbol table is accessed only during lexical analysis and syntax analysis. II. Compilers for programming languages that support recursion nec…Compiler Design · Syntax-Directed Translation & Runtime Environments · MCQ · 1 mark
- Q20Consider the language L = \ a n n 0\ \ a nb n n 0\ and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministic context-free. III.…Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- Q21Consider allocation of memory to a new process. Assume that none of the existing holes in the memory will exactly fit the process's memory requirement. Hence, a new hole of smalle…Operating Systems (OS) · Memory Management and Virtual Memory · MCQ · 1 mark
- Q22Consider the following statements about process state transitions for a system using preemptive scheduling. I. A running process can move to ready state. II. A ready process can m…Operating Systems (OS) · System Calls, Processes, Threads, InterProcess Communication · MCQ · 1 mark
- Q23Consider a relational database containing the following schemas. The primary key of each table is indicated by underlining the constituent fields. sql SELECT s.sno, s.sname FROM S…Database Management Systems (DBMS) · SQL Queries (DDL/DML, Joins, Aggregations) · MCQ · 1 mark
- Q24Which one of the following is used to represent the supporting many-one relationships of a weak entity set in an entity-relationship diagram?Database Management Systems (DBMS) · ER-Model · MCQ · 1 mark
- Q25Consider the following statements about the functionality of an IP based router. I. A router does not modify the IP packets during forwarding. II. It is not necessary for a router…Computer Networks (CN) · Fragmentation and IP Addressing (IPv4, IPv6, CIDR, Basics of IP support Protocols (ARP, DHCP, ICMP), NAT) · MCQ · 1 mark
- Q26What 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?Data Structures · Linked Lists & Binary Trees · MCQ · 1 mark
- Q29A 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 of only one register will mov…Digital Logic · Combinational Logic (Multiplexers, Decoders, Adders) · NAT · 1 mark
- Q30If 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 m + n is .Digital Logic · Combinational Logic (Multiplexers, Decoders, Adders) · NAT · 1 mark
- Q31A 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, it takes 20 ns to bring the fi…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · NAT · 1 mark
- Q32Consider the following C program: c include <stdio.h> int main( ) int a[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+2)…Programming in C · Pointers, Multi-Dimensional Arrays, Structures · NAT · 1 mark
- Q33Consider 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 the table size is 23. The…Algorithms · Searching, Sorting, Hashing Mechanisms · NAT · 1 mark
- Q34Consider 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 .Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · NAT · 1 mark
- Q35Assume 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 browser is configured to send HTTP…Computer Networks (CN) · Application Layer (DNS, SMTP, HTTP, FTP, Email) & Security · NAT · 1 mark
- Q36Which 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 reaches state q in exactl…Theory of Computation (TOC) · Turing Machines & Undecidability · MCQ · 2 marks
- Q38Consider the Boolean function z(a, b, c) . Which one of the following minterm lists represents the circuit given above?Digital Logic · Boolean Algebra, Minimization, K-Maps · MCQ · 2 marks
- Q39Consider three registers R1, R2, and R3 that store numbers in IEEE-754 single precision floating point format. Assume that R1 and R2 contain the values (in hexadecimal notation) 0…Digital Logic · Number Representations & Fixed/Floating Point Math · MCQ · 2 marks
- Q40A 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 size of 256 bytes. Consider t…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · MCQ · 2 marks
- Q41Let 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 edge (u, v) V V is added to…Algorithms · Minimum Spanning Trees (Prim/Kruskal Algorithms) · MCQ · 2 marks
- Q42Consider 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?Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- Q43Consider 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 is an inherited attribute. Conside…Compiler Design · Syntax-Directed Translation & Runtime Environments · MCQ · 2 marks
- Q44Each 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 shared variable initialized to 0…Operating Systems (OS) · Concurrency & Synchronization (Semaphores, Mutex, Monitors, Locks) · MCQ · 2 marks
- Q45Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time. (P, 155), (Q, 85), (R, 110…Operating Systems (OS) · File Systems Operations & Disk Scheduling Optimization · MCQ · 2 marks
- Q46Consider a relational table R that is in 3NF, but not in BCNF. Which one of the following statements is TRUE?Database Management Systems (DBMS) · Normalization Schemes (1NF, 2NF, 3NF, BCNF Boundaries) · MCQ · 2 marks
- Q47Consider a schedule of transactions T 1 and T 2 : Here, RX stands for "Read(X)" and WX stands for "Write(X)". Which one of the following schedules is conflict equivalent to the ab…Database Management Systems (DBMS) · Transactions, Concurrency Control, Conflict Serializability · MCQ · 2 marks
- Q48An organization requires a range of IP addresses to assign one to each of its 1500 computers. The organization has approached an Internet Service Provider (ISP) for this task. The…Computer Networks (CN) · Fragmentation and IP Addressing (IPv4, IPv6, CIDR, Basics of IP support Protocols (ARP, DHCP, ICMP), NAT) · MCQ · 2 marks
- Q50Let G = (V, E) be a directed, weighted graph with weight function w : E R . For some function f : V R , for each edge (u, v) E , define w'(u, v) as w(u, v) + f(u) - f(v) . Which o…Algorithms · Graph Traversals (BFS, DFS) & Single-Source Shortest Paths · MCQ · 2 marks
- Q51In 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 number of reported elements is…Data Structures · Binary Search Trees (BSTs) & Binary Heaps · MCQ · 2 marks
- Q53Consider 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 out of this processor. Overhe…Computer Organization and Architecture (COA) · Instruction Pipelining, Performance, Hazard Management · NAT · 2 marks
- Q54A 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 an opcode, a register name,…Computer Organization and Architecture (COA) · Machine Instructions & Addressing Modes · NAT · 2 marks
- Q56Consider the following C functions: c int fun1(int n) static int i = 0; if (n > 0) ++i; fun1(n - 1); return(i); int fun2(int n) static int i = 0; if (n > 0) i = i + fun1(n); fun2(…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · NAT · 2 marks
- Q57Consider the array representation of a binary min-heap containing 1023 elements. The minimum number of comparisons required to find the maximum in the heap is .Data Structures · Binary Search Trees (BSTs) & Binary Heaps · NAT · 2 marks
- Q58Consider the following C functions: c int tob(int b, int arr) int i; for(i=0; b>0; i++) if(b%2) arr[i]=1; else arr[i]=0; b=b/2; return(i); int pp(int a, int b) int arr[20]; int i,…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · NAT · 2 marks
- Q59Consider 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 tree o…Algorithms · Minimum Spanning Trees (Prim/Kruskal Algorithms) · NAT · 2 marks
- Q60Consider the following set of processes, assumed to have arrived at time 0. Consider the CPU scheduling algorithms Shortest Job First (SJF) and Round Robin (RR). For RR, assume th…Operating Systems (OS) · CPU and I/O Scheduling · NAT · 2 marks
- Q61Consider 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 accepts L is .Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · NAT · 2 marks
- Q63Consider 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 and TLB lookup takes 20 ns. E…Operating Systems (OS) · Memory Management and Virtual Memory · NAT · 2 marks
- Q64Consider 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 bytes and the size of tree/disk…Database Management Systems (DBMS) · File Organization & Indexing (e.g., B and B+ Trees) · NAT · 2 marks
- Q65Consider 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 advertised window is 50 KB, slow-s…Computer Networks (CN) · Transport Layer (Flow Control and Congestion Control, TCP, UDP, Sockets) · NAT · 2 marks

