GATE CS 2018 (Forenoon)

65 questions · 100 marks · 180 minutes

Take this paper as a timed test
From RENYXERAThis week's 10-question challengeSame 10 past-GATE questions for everyone this week — see where you stand.

GENERAL APTITUDE (GA)

  1. Q1“From where are they bringing their books? bringing books from .” The words that best fill the blanks in the above sentence areVerbal Aptitude · Grammar Rules (Prepositions, Conjunctions, Verb-Noun Agreement, Other Parts of Speech) · MCQ · 1 mark
  2. Q2“A investigation can sometimes yield new facts, but typically organized ones are more successful.” The word that best fills the blank in the above sentence isVerbal Aptitude · Basic Vocabulary (Words, Idioms, Phrases in Context) · MCQ · 1 mark
  3. Q3The area of a square is d. What is the area of the circle which has the diagonal of the square as its diameter?Quantitative Aptitude · Mensuration and Geometry · MCQ · 1 mark
  4. Q4What would be the smallest natural number which when divided either by 20 or by 42 or by 76 leaves a remainder of 7 in each case?Analytical Aptitude · Numerical Relations & Arithmetic Logic · MCQ · 1 mark
  5. Q5What is the missing number in the following sequence? 2, 12, 60, 240, 720, 1440, , 0Analytical Aptitude · Numerical Relations & Arithmetic Logic · MCQ · 1 mark
  6. Q6In appreciation of the social improvements completed in a town, a wealthy philanthropist decided to gift Rs 750 to each male senior citizen in the town and Rs 1000 to each female…Quantitative Aptitude · Numerical Computation (Percentages, Ratios) · MCQ · 2 marks
  7. Q7If pqr 0 and p -x = 1 q , q -y = 1 r , r -z = 1 p , what is the value of the product xyz?Quantitative Aptitude · Mathematical Operations (Powers, Exponents, Logarithms) · MCQ · 2 marks
  8. Q8In a party, 60% of the invited guests are male and 40% are female. If 80% of the invited guests attended the party and if all the invited female guests attended, what would be the…Quantitative Aptitude · Numerical Computation (Percentages, Ratios) · MCQ · 2 marks
  9. Q9In the figure below, DEC + BFC is equal to .Quantitative Aptitude · Mensuration and Geometry · MCQ · 2 marks
  10. Q10A six sided unbiased die with four green faces and two red faces is rolled seven times. Which of the following combinations is the most likely outcome of the experiment?Quantitative Aptitude · Elementary Statistics and Probability · MCQ · 2 marks

MATHEMATICAL FOUNDATIONS

  1. Q11Which one of the following is a closed form expression for the generating function of the sequence \ a n\ , where a n = 2n + 3 for all n = 0, 1, 2, ?Discrete Mathematics · Recurrence Relations and Generating Functions · MCQ · 1 mark
  2. Q25Two people, P and Q, decide to independently roll two identical dice, each with 6 faces, numbered 1 to 6. The person with the lower number wins. In case of a tie, they roll the di…Probability & Statistics · Conditional Probability & Bayes Theorem · NAT · 1 mark
  3. Q26The value of 0 /4 x (x 2) dx correct to three decimal places (assuming that = 3.14) is .Calculus · Mean Value Theorems & Definite Integration · NAT · 1 mark
  4. Q27Consider a matrix A = uv T where u = pmatrix 1 \\ 2 pmatrix , v = pmatrix 1 \\ 1 pmatrix . Note that v T denotes the transpose of v. The largest eigenvalue of A is .Linear Algebra · Eigenvalues and Eigenvectors · NAT · 1 mark
  5. Q28The chromatic number of the following graph is .Discrete Mathematics · Advanced Graph Bounds (Matching, Coloring Theorems) · NAT · 1 mark
  6. Q29Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is .Discrete Mathematics · Algebraic Structures (Monoids, Groups) · NAT · 1 mark
  7. Q36Consider a matrix P whose only eigenvectors are the multiples of bmatrix 1 \\ 4 bmatrix . Consider the following statements. (I) P does not have an inverse (II) P has a repeated e…Linear Algebra · Eigenvalues and Eigenvectors · MCQ · 2 marks
  8. Q37Let N be the set of natural numbers. Consider the following sets. P: Set of Rational numbers (positive and negative) Q: Set of functions from \ 0, 1\ to N R: Set of functions from…Discrete Mathematics · Sets, Relations, Functions, Partial Orders, Lattices · MCQ · 2 marks
  9. Q38Consider the first-order logic sentence s t u v w x y (s, t, u, v, w, x, y) where (s, t, u, v, w, x, y) is a quantifier-free first-order logic formula using only predicate symbols…Discrete Mathematics · Propositional and First-Order Quantifier Logic · MCQ · 2 marks
  10. Q53Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, ..., 100. There is an edge between vertices u and v if and only if the…Discrete Mathematics · Graph Theory (Connectivity, Paths, Cycles, Trees) · NAT · 2 marks
  11. Q54Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (H), medium (M) and low (L). Let P(H G) denote the probability that Guwahati has high temperature.…Probability & Statistics · Conditional Probability & Bayes Theorem · NAT · 2 marks

CORE CS

  1. Q12Consider the following C program. c include<stdio.h> struct Ournode char x,y,z; ; int main() struct Ournode p = '1', '0', 'a'+2 ; struct Ournode q = &p; printf ("%c, %c", ((char )…Programming in C · Pointers, Multi-Dimensional Arrays, Structures · MCQ · 1 mark
  2. Q13A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the qu…Data Structures · Abstract Data Types (ADTs), Stacks, Queues · MCQ · 1 mark
  3. Q14Let and denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?Digital Logic · Boolean Algebra, Minimization, K-Maps · MCQ · 1 mark
  4. Q15Consider the following processor design characteristics. I. Register-to-register arithmetic operations only II. Fixed-length instruction format III. Hardwired control unit Which o…Computer Organization and Architecture (COA) · ALU, Control Unit Design, Data-Path Operations · MCQ · 1 mark
  5. Q16Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · MCQ · 1 mark
  6. Q17The set of all recursively enumerable languages isTheory of Computation (TOC) · Turing Machines & Undecidability · MCQ · 1 mark
  7. Q18Which one of the following statements is FALSE?Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 1 mark
  8. Q19The following are some events that occur after a device controller issues an interrupt while process L is under execution. (P) The processor pushes the process status of L onto th…Computer Organization and Architecture (COA) · I/O Interfaces (Interrupts & DMA Control Modes) · MCQ · 1 mark
  9. Q20Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is avai…Operating Systems (OS) · Memory Management and Virtual Memory · MCQ · 1 mark
  10. Q21In an Entity-Relationship (ER) model, suppose R is a many-to-one relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in R and that the card…Database Management Systems (DBMS) · ER-Model · MCQ · 1 mark
  11. Q22Consider the following two tables and four queries in SQL. Book (isbn, bname), Stock (isbn, copies) Query 1: SELECT B.isbn, S.copies FROM Book B INNER JOIN Stock S ON B.isbn = S.i…Database Management Systems (DBMS) · SQL Queries (DDL/DML, Joins, Aggregations) · MCQ · 1 mark
  12. Q23Match the following: Field Length in bits P. UDP Header’s Port Number I. 48 Q. Ethernet MAC Address II. 8 R. IPv6 Next Header III. 32 S. TCP Header’s Sequence Number IV. 16Computer Networks (CN) · OSI & TCP/IP Protocol Layers · MCQ · 1 mark
  13. Q24Consider the following statements regarding the slow start phase of the TCP congestion control algorithm. Note that cwnd stands for the TCP congestion window and MSS denotes the M…Computer Networks (CN) · Transport Layer (Flow Control and Congestion Control, TCP, UDP, Sockets) · MCQ · 1 mark
  14. Q30The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path…Data Structures · Linked Lists & Binary Trees · NAT · 1 mark
  15. Q31Consider the following C program: c include <stdio.h> int counter = 0; int calc (int a, int b) int c; counter++; if (b==3) return (a a a); else c = calc(a, b/3); return (c c c); i…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · NAT · 1 mark
  16. Q32Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops. The number of states in the state transition diagram of t…Digital Logic · Sequential Circuits (Flip-Flops, Registers, Counters) · NAT · 1 mark
  17. Q33A 32-bit wide main memory unit with a capacity of 1 GB is built using 256M 4-bit DRAM chips. The number of rows of memory cells in the DRAM chip is 2 14 . The time taken to perfor…Computer Organization and Architecture (COA) · Main Memory & Virtual Memory Mechanics · NAT · 1 mark
  18. Q34Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of K instances. Resource instances can be requested and rel…Operating Systems (OS) · Deadlock Prevention, Avoidance, Detection, Recovery · NAT · 1 mark
  19. Q35Consider a long-lived TCP session with an end-to-end bandwidth of 1 Gbps (= 10 9 bits-per-second). The session starts with a sequence number of 1234. The minimum time (in seconds,…Computer Networks (CN) · Transport Layer (Flow Control and Congestion Control, TCP, UDP, Sockets) · NAT · 1 mark
  20. Q39Consider the following C program: c include<stdio.h> void fun1(char s1, char s2) char tmp; tmp = s1; s1 = s2; s2 = tmp; void fun2(char s1, char s2) char tmp; tmp = s1; s1 = s2; s2…Programming in C · Pointers, Multi-Dimensional Arrays, Structures · MCQ · 2 marks
  21. Q40Let G be a simple undirected graph. Let T D be a depth first search tree of G. Let T B be a breadth first search tree of G. Consider the following statements. (I) No edge of G is…Algorithms · Graph Traversals (BFS, DFS) & Single-Source Shortest Paths · MCQ · 2 marks
  22. Q41Assume that multiplying a matrix G 1 of dimension p q with another matrix G 2 of dimension q r requires pqr scalar multiplications. Computing the product of n matrices G 1G 2G 3 G…Algorithms · Dynamic Programming Infrastructure · MCQ · 2 marks
  23. Q42Consider the following C code. Assume that unsigned long int type length is 64 bits. c unsigned long int fun(unsigned long int n) unsigned long int i, j = 0, sum = 0; for (i = n;…Algorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 2 marks
  24. Q43Consider the unsigned 8-bit fixed point binary number representation below, b 7 b 6 b 5 b 4 b 3 . b 2 b 1 b 0 where the position of the binary point is between b 3 and b 2. Assume…Digital Logic · Number Representations & Fixed/Floating Point Math · MCQ · 2 marks
  25. Q44The size of the physical address space of a processor is 2 P bytes. The word length is 2 W bytes. The capacity of cache memory is 2 N bytes. The size of each cache block is 2 M wo…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · MCQ · 2 marks
  26. Q45Consider the following languages: I. \ a m b n c p d q m + p = n + q, where m, n, p, q 0\ II. \ a m b n c p d q m = n and p = q, where m, n, p, q 0\ III. \ a m b n c p d q m = n =…Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
  27. Q46Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M. (I) For an unrestricted grammar G and a str…Theory of Computation (TOC) · Turing Machines & Undecidability · MCQ · 2 marks
  28. Q47A lexical analyzer uses the following patterns to recognize three tokens T 1, T 2, and T 3 over the alphabet \ a,b,c\ . T 1: a? (b c) a T 2: b? (a c) b T 3: c? (b a) c Note that ‘…Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 2 marks
  29. Q48Consider the following parse tree for the expression a bcd e f, involving two binary operators and . Which one of the following is correct for the given parse tree?Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 2 marks
  30. Q49In a system, there are three types of resources: E, F and G. Four processes P 0, P 1, P 2 and P 3 execute concurrently. At the outset, the processes have declared their maximum re…Operating Systems (OS) · Deadlock Prevention, Avoidance, Detection, Recovery · MCQ · 2 marks
  31. Q50Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is N. Three semaphores empty, full and mutex are defined with respective i…Operating Systems (OS) · Concurrency & Synchronization (Semaphores, Mutex, Monitors, Locks) · MCQ · 2 marks
  32. Q51Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query Q: r ( B<5 (s)) Let LOJ denote the natural left…Database Management Systems (DBMS) · Relational Models, Relational Algebra, Tuple Calculus · MCQ · 2 marks
  33. Q52Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys. Sch…Database Management Systems (DBMS) · Normalization Schemes (1NF, 2NF, 3NF, BCNF Boundaries) · MCQ · 2 marks
  34. Q55Consider the following program written in pseudo-code. Assume that x and y are integers. c Count(x,y) if (y != 1) if (x != 1) print(" "); Count(x/2, y); else y = y-1; Count(1024,…Algorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · NAT · 2 marks
  35. Q56The number of possible min-heaps containing each value from \ 1, 2, 3, 4, 5, 6, 7\ exactly once is .Data Structures · Binary Search Trees (BSTs) & Binary Heaps · NAT · 2 marks
  36. Q57Consider the following undirected graph G: Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this valu…Algorithms · Minimum Spanning Trees (Prim/Kruskal Algorithms) · NAT · 2 marks
  37. Q58Consider the weights and values of items listed below. Note that there is only one unit of each item. Item number Weight (in Kgs) Value (in Rupees) 1 10 60 2 7 28 3 4 20 4 2 24 Th…Algorithms · Greedy Approach & Divide-and-Conquer Designs · NAT · 2 marks
  38. Q59Consider the minterm list form of a Boolean function F given below. F(P, Q, R, S) = m(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14) Here, m denotes a minterm and d denotes a don’t care…Digital Logic · Boolean Algebra, Minimization, K-Maps · NAT · 2 marks
  39. Q60The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (W…Computer Organization and Architecture (COA) · Instruction Pipelining, Performance, Hazard Management · NAT · 2 marks
  40. Q61A processor has 16 integer registers (R0, R1, .. , R15) and 64 floating point registers (F0, F1,… , F63). It uses a 2-byte instruction format. There are four categories of instruc…Computer Organization and Architecture (COA) · Machine Instructions & Addressing Modes · NAT · 2 marks
  41. Q62Given a language L, define L i as follows: L 0 = \ \ L i = L i-1 L for all i > 0 The order of a language L is defined as the smallest k such that L k = L k+1 . Consider the langua…Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · NAT · 2 marks
  42. Q63Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, … , 199), and 256 sectors per track (numbered as 0, 1, … , 255). The followin…Operating Systems (OS) · File Systems Operations & Disk Scheduling Optimization · NAT · 2 marks
  43. Q64Consider an IP packet with a length of 4,500 bytes that includes a 20-byte IPv4 header and a 40-byte TCP header. The packet is forwarded to an IPv4 router that supports a Maximum…Computer Networks (CN) · Fragmentation and IP Addressing (IPv4, IPv6, CIDR, Basics of IP support Protocols (ARP, DHCP, ICMP), NAT) · NAT · 2 marks
  44. Q65Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carri…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · NAT · 2 marks