GATE CS 2017 (Afternoon)
65 questions · 100 marks · 180 minutes
CORE CS
- Q1The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system isDigital Logic · Number Representations & Fixed/Floating Point Math · MCQ · 1 mark
- Q2Match the following: List-I (P) static char var; (Q) m = malloc (10); m = NULL ; (R) char ptr[10]; (S) register int var1; List-II (i) Sequence of memory locations to store address…Programming in C · Dynamic Memory Allocation & File Handling · MCQ · 1 mark
- Q3Match the algorithms with their time complexities: List-I (Algorithm) (P) Towers of Hanoi with n disks (Q) Binary search given n sorted numbers (R) Heap sort given n numbers at th…Algorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 1 mark
- Q4Let L 1, L 2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L 1 L 2 is context-free. II. L 1 is context-free. III.…Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- Q5Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: List-I (P) Syntax tree (Q) Character stream (R) Interm…Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 1 mark
- Q6Which of the following statements about parser is/are CORRECT? I. Canonical LR is more powerful than SLR. II. SLR is more powerful than LALR. III. SLR is more powerful than Canoni…Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 1 mark
- Q7Which of the following is/are shared by all the threads in a process? I. Program counter II. Stack III. Address space IV. RegistersOperating Systems (OS) · System Calls, Processes, Threads, InterProcess Communication · MCQ · 1 mark
- Q8In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed? I. Contiguous II. Linked III. IndexedOperating Systems (OS) · File Systems Operations & Disk Scheduling Optimization · MCQ · 1 mark
- Q9Consider the following statements about the routing protocols, Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) in an IPv4 network. I: RIP uses distance vect…Computer Networks (CN) · Routing Protocols (Shortest Path, Flooding, Distance Vector, Link State Routing) · MCQ · 1 mark
- Q12Given the following binary number in 32-bit (single precision) IEEE-754 format: 00111110011011010000000000000000 The decimal value closest to this floating-point number isDigital Logic · Number Representations & Fixed/Floating Point Math · MCQ · 1 mark
- Q13A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two extern…Data Structures · Abstract Data Types (ADTs), Stacks, Queues · MCQ · 1 mark
- Q14Consider the following function implemented in C: c void printxy (int x, int y) int ptr; x = 0; ptr = &x; y = ptr; ptr = 1; printf ("%d, %d", x, y); The output of invoking printxy…Programming in C · Pointers, Multi-Dimensional Arrays, Structures · MCQ · 1 mark
- Q15The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph bel…Algorithms · Graph Traversals (BFS, DFS) & Single-Source Shortest Paths · MCQ · 1 mark
- Q16Identify the language generated by the following grammar, where S is the start variable. S XY X aX a Y aYbTheory of Computation (TOC) · Context-Free Grammars & Push-Down Automata · MCQ · 1 mark
- Q17An ER model of a database consists of entity types A and B. These are connected by a relationship R which does not have its own attribute. Under which one of the following conditi…Database Management Systems (DBMS) · ER-Model · MCQ · 1 mark
- Q18Consider socket API on a Linux machine that supports connected UDP sockets. A connected UDP socket is a UDP socket on which connect function has already been called. Which of the…Computer Networks (CN) · Transport Layer (Flow Control and Congestion Control, TCP, UDP, Sockets) · MCQ · 1 mark
- Q19Consider the following tables T 1 and T 2. In table T 1, P is the primary key and Q is the foreign key referencing R in table T 2 with on-delete cascade and on-update cascade. In…Database Management Systems (DBMS) · Integrity Constraints & Functional Dependencies · NAT · 1 mark
- Q20The maximum number of IPv4 router addresses that can be listed in the record route (RR) option field of an IPv4 header is .Computer Networks (CN) · Fragmentation and IP Addressing (IPv4, IPv6, CIDR, Basics of IP support Protocols (ARP, DHCP, ICMP), NAT) · NAT · 1 mark
- Q24Consider a quadratic equation x 2 - 13x + 36 = 0 with coefficients in a base 'b'. The solutions of this equation in the same base 'b' are x = 5 and x = 6. Then b = .Digital Logic · Number Representations & Fixed/Floating Point Math · NAT · 1 mark
- Q25The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = \ w 1 a w 2 w 1, w 2 \ a, b\ , w 1 = 2, w 2 3\ is .Theory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · NAT · 1 mark
- Q27If w, x, y, z are Boolean variables, then which one of the following is INCORRECT?Digital Logic · Boolean Algebra, Minimization, K-Maps · MCQ · 2 marks
- Q28Given f(w, x, y, z) = m(0, 1, 2, 3, 7, 8, 10) + d(5, 6, 11, 15), where d represents the don't-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums…Digital Logic · Boolean Algebra, Minimization, K-Maps · MCQ · 2 marks
- Q29In a two-level cache system, the access times of L 1 and L 2 caches are 1 and 8 clock cycles, respectively. The miss penalty from the L 2 cache to main memory is 18 clock cycles.…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · MCQ · 2 marks
- Q30Consider the recurrence function T(n) = cases 2T( n ) + 1, & n > 2 \\ 2, & 0 < n 2 cases Then T(n) in terms of notation isAlgorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 2 marks
- Q32Consider the following expression grammar G : E E - T T T T + F F F (E) id Which of the following grammars is not left recursive, but is equivalent to G?Compiler Design · Lexical Analysis & Parsing Architectures (LL(1), LR(1), LALR) · MCQ · 2 marks
- Q33A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below: Which of the following best describes current sta…Operating Systems (OS) · Deadlock Prevention, Avoidance, Detection, Recovery · MCQ · 2 marks
- Q34Consider a binary code that consists of only four valid codewords as given below: 00000, 01011, 10101, 11110 Let the minimum Hamming distance of the code be p and the maximum numb…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · MCQ · 2 marks
- Q35Consider two hosts X and Y, connected by a single direct link of rate 10 6 bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2…Computer Networks (CN) · Data Link Layer (Framing, Error Detection, MAC, Ethernet Bridging) · MCQ · 2 marks
- Q36The pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:Data Structures · Binary Search Trees (BSTs) & Binary Heaps · MCQ · 2 marks
- Q37Consider the C program fragment below which is meant to divide x by y using repeated subtractions. The variables x, y, q and r are all unsigned int. c while (r >= y) r = r - y; q…Programming in C · Data Types, Syntax, Control Structures, Loops · MCQ · 2 marks
- Q38Consider the following C function. c int fun (int n) int i, j; for (i = 1; i <= n; i++) for (j = 1; j < n; j += i) printf("%d %d", i, j); Time complexity of fun in terms of notati…Algorithms · Asymptotic Analysis (O, Omega, Theta Complexities) · MCQ · 2 marks
- Q39Let denote the transition function and denote the extended transition function of the -NFA whose transition table is given below: The (q 2, aba) isTheory of Computation (TOC) · Regular Expressions & Finite Automata (DFA/NFA Min) · MCQ · 2 marks
- Q40Consider the following languages. L 1 = \ a p p is a prime number \ L 2 = \ a n b m c 2m n 0, m 0\ L 3 = \ a n b n c 2n n 0\ L 4 = \ a n b n n 1\ Which of the following are CORREC…Theory of Computation (TOC) · Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- Q41Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine…Theory of Computation (TOC) · Turing Machines & Undecidability · MCQ · 2 marks
- Q42The next state table of a 2-bit saturating up-counter is given below. The counter is built as a synchronous sequential circuit using T flip-flops. The expressions for T 1 and T 0…Digital Logic · Sequential Circuits (Flip-Flops, Registers, Counters) · MCQ · 2 marks
- Q43Consider the following snippet of a C program. Assume that swap (&x, &y) exchanges the contents of x and y. c int main() int array[] = 3, 5, 1, 4, 6, 2 ; int done = 0; int i; whil…Programming in C · Functions, Parameter Passing, Scope Rules, Recursion · NAT · 2 marks
- Q44Two transactions T 1 and T 2 are given as T 1: r 1(X) \ w 1(X) \ r 1(Y) \ w 1(Y) T 2: r 2(Y) \ w 2(Y) \ r 2(Z) \ w 2(Z) where r i(V) denotes a read operation by transaction T i on…Database Management Systems (DBMS) · Transactions, Concurrency Control, Conflict Serializability · NAT · 2 marks
- Q45The read access times and the hit ratios for different caches in a memory hierarchy are as given below. The read access time of main memory is 90 nanoseconds. Assume that the cach…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · NAT · 2 marks
- Q46Consider the following database table named top\ scorer . Consider the following SQL query: sql SELECT ta.player FROM top scorer as ta WHERE ta.goals > ALL (SELECT tb.goals FROM t…Database Management Systems (DBMS) · SQL Queries (DDL/DML, Joins, Aggregations) · NAT · 2 marks
- Q49In a B + tree, if the search-key value is 8 bytes long, the block size is 512 bytes and the block pointer size is 2 bytes, then the maximum order of the B + tree is .Database Management Systems (DBMS) · File Organization & Indexing (e.g., B and B+ Trees) · NAT · 2 marks
- Q50A message is made up entirely of characters from the set X = \ P, Q, R, S, T\ . The table of probabilities for each of the characters is shown below: If a message of 100 character…Algorithms · Greedy Approach & Divide-and-Conquer Designs · NAT · 2 marks
- Q51Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes ha…Operating Systems (OS) · CPU and I/O Scheduling · NAT · 2 marks
- Q53Consider a machine with a byte addressable main memory of 2 32 bytes divided into blocks of size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with th…Computer Organization and Architecture (COA) · Memory Hierarchy (Direct/Associative Cache Mapping) · NAT · 2 marks
- Q54Consider the following C program c include <stdio.h> int main( ) int m = 10; int n, n1; n = ++m; n1 = m++; n--; --n1; n -= n1; printf("%d", n); return 0; The output of the program…Programming in C · Data Types, Syntax, Control Structures, Loops · NAT · 2 marks
- Q55Consider the following C program. c include <stdio.h> include <string.h> int main( ) char c = "GATECSIT2017"; char p = c; printf("%d", (int) strlen (c+2[p] - 6[p]-1)); return 0; T…Programming in C · Pointers, Multi-Dimensional Arrays, Structures · NAT · 2 marks
MATHEMATICAL FOUNDATIONS
- Q10If f(x) = R ( x 2 ) + S, f' ( 1 2 ) = 2 and 0 1 f(x)dx = 2R , then the constants R and S are, respectivelyCalculus · Mean Value Theorems & Definite Integration · MCQ · 1 mark
- Q11Let p, q, r denote the statements " It is raining ", " It is cold ", and " It is pleasant ", respectively. Then the statement " It is not raining and it is pleasant, and it is not…Discrete Mathematics · Propositional and First-Order Quantifier Logic · MCQ · 1 mark
- Q21Consider the set X = a, b, c, d, e under the partial ordering R = (a, a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e) . The Hass…Discrete Mathematics · Sets, Relations, Functions, Partial Orders, Lattices · NAT · 1 mark
- Q22Let P = bmatrix 1 & 1 & -1 \\ 2 & -3 & 4 \\ 3 & -2 & 3 bmatrix and Q = bmatrix -1 & -2 & -1 \\ 6 & 12 & 6 \\ 5 & 10 & 5 bmatrix be two matrices. Then the rank of P + Q is .Linear Algebra · Matrices, Determinants, & Linear Equation Systems · NAT · 1 mark
- Q23G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is .Discrete Mathematics · Graph Theory (Connectivity, Paths, Cycles, Trees) · NAT · 1 mark
- Q26P and Q are considering to apply for a job. The probability that P applies for the job is 1 4 , the probability that P applies for the job given that Q applies for the job is 1 2…Probability & Statistics · Conditional Probability & Bayes Theorem · MCQ · 2 marks
- Q31For any discrete random variable X, with probability mass function P(X = j) = p j, p j 0, j \ 0 N\ , and j=0 N p j = 1, define the polynomial function g X(z) = j=0 N p j z j. For…Probability & Statistics · Random Variables & Sampling Rules · MCQ · 2 marks
- Q47If the ordinary generating function of a sequence \ a n\ n=0 is 1 + z (1 - z) 3 , then a 3 - a 0 is equal toDiscrete Mathematics · Recurrence Relations and Generating Functions · NAT · 2 marks
- Q48If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2) 2] equals .Probability & Statistics · Standard Distributions (Poisson, Binomial) · NAT · 2 marks
- Q52If the characteristic polynomial of a 3 3 matrix M over R (the set of real numbers) is 3 - 4 2 + a + 30, a R , and one eigenvalue of M is 2, then the largest among the absolute va…Linear Algebra · Eigenvalues and Eigenvectors · NAT · 2 marks
GENERAL APTITUDE (GA)
- Q56Choose the option with words that are not synonyms.Verbal Aptitude · Vocabulary Mechanics (Antonyms, Synonyms) · MCQ · 1 mark
- Q57Saturn is to be seen on a clear night with the naked eye.Verbal Aptitude · Basic English Grammar (Tenses, Articles, Adjectives) · MCQ · 1 mark
- Q58There are five buildings called V, W, X, Y and Z in a row (not necessarily in that order). V is to the West of W. Z is to the East of X and the West of V. W is to the West of Y. W…Analytical Aptitude · Operational Puzzles and Systemic Reasoning · MCQ · 1 mark
- Q59A test has twenty questions worth 100 marks in total. There are two types of questions. Multiple choice questions are worth 3 marks each and essay questions are worth 11 marks eac…Analytical Aptitude · Numerical Relations & Arithmetic Logic · MCQ · 1 mark
- Q60There are 3 red socks, 4 green socks and 3 blue socks. You choose 2 socks. The probability that they are of the same colour isQuantitative Aptitude · Elementary Statistics and Probability · MCQ · 1 mark
- Q61"We lived in a culture that denied any merit to literary works, considering them important only when they were handmaidens to something seemingly more urgent- namely ideology. Thi…Verbal Aptitude · Reading Comprehension · MCQ · 2 marks
- Q62There are three boxes. One contains apples, another contains oranges and the last one contains both apples and oranges. All three are known to be incorrectly labelled. If you are…Analytical Aptitude · Logic Deduction and Induction Frameworks · MCQ · 2 marks
- Q63X is a 30 digit number starting with the digit 4 followed by the digit 7. Then the number X 3 will haveQuantitative Aptitude · Mathematical Operations (Powers, Exponents, Logarithms) · MCQ · 2 marks
- Q64The number of roots of e x + 0.5x 2 - 2 = 0 in the range [-5, 5] isQuantitative Aptitude · Mathematical Operations (Powers, Exponents, Logarithms) · MCQ · 2 marks
- Q65An air pressure contour line joins locations in a region having the same atmospheric pressure. The following is an air pressure contour plot is a geographical region. Contour line…Quantitative Aptitude · Graphical Representations (2D and 3D Plots, Maps, Tables) · MCQ · 2 marks

