The GATE Grind

GATE 2017 CS (CS1) – Previous Year Questions with Solutions

All 65 questions of GATE 2017 CS (CS1) 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 (10), Programming and Data Structures (7), Theory of Computation (6), Computer Organization and Architecture (6), Computer Networks (5), Databases (5), Algorithms (4).

Practise this paper in The GATE Grind →

  1. Question 1 (1 mark, Multiple choice) – After Rajendra Chola returned from his voyage to Indonesia, he to visit the temple in Thanjavur.
  2. Question 2 (1 mark, Multiple choice) – Research in the workplace reveals that people work for many reasons .
  3. Question 3 (1 mark, Multiple choice) – Rahul, Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of Murali. Srinivas is sitting to the right of Arul.…
  4. Question 4 (1 mark, Multiple choice) – Find the smallest number y such that y 162 is a perfect cube.
  5. Question 5 (1 mark, Multiple choice) – The probability that a k-digit number does NOT contain the digits 0, 5, or 9 is
  6. Question 6 (2 marks, Multiple choice) – "The hold of the nationalist imagination on our colonial past is such that anything inadequately or improperly nationalist is just not history." Which…
  7. Question 7 (2 marks, Multiple choice) – Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman…
  8. Question 8 (2 marks, Multiple choice) – The expression (x + y) - x - y 2 is equal to
  9. Question 9 (2 marks, Multiple choice) – Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and white respectively. Arun dislikes the…
  10. Question 10 (2 marks, Multiple choice) – A contour line joins locations having the same height above the mean sea level. The following is a contour plot of a geographical region. Contour…
  11. Question 11 (1 mark, Multiple choice) – The statement ( p) ( q) is logically equivalent to which of the statements below? I. p q II. q p III. ( q) p IV. ( p) q
  12. Question 12 (1 mark, Multiple choice) – Consider the first-order logic sentence F: x( y R(x, y)). Assuming non-empty logical domains, which of the sentences below are implied by F? I. y( x…
  13. Question 13 (1 mark, Multiple choice) – Let c 1, , c n be scalars, not all zero, such that i=1n c i a i = 0 where a i are column vectors in Rn. Consider the set of linear equations Ax = b…
  14. Question 14 (1 mark, Multiple choice) – Consider the following functions from positive integers to real numbers: 10, n, n, 2 n, 100n. The CORRECT arrangement of the above functions in…
  15. Question 15 (1 mark, Multiple choice) – Consider the following table: Algorithms Design Paradigms --- --- (P) Kruskal (i) Divide and Conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall…
  16. Question 16 (1 mark, Multiple choice) – Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are: Note: The height of a tree with a single node is 0.
  17. Question 17 (1 mark, Multiple choice) – The n-bit fixed-point representation of an unsigned real number X uses f bits for the fraction part. Let i = n - f. The range of decimal values for X…
  18. Question 18 (1 mark, Multiple choice) – Consider the C code fragment given below. Assuming that `m` and `n` point to valid NULL-terminated linked lists, invocation of `join` will
  19. Question 19 (1 mark, Multiple choice) – When two 8-bit numbers A 7 A 0 and B 7 B 0 in 2's complement representation (with A 0 and B 0 as the least significant bits) are added using a…
  20. Question 20 (1 mark, Multiple choice) – Consider the following context-free grammar over the alphabet = \a, b, c\ with S as the start symbol: S abScT abcT T bT b Which one of the following…
  21. Question 21 (1 mark, Multiple choice) – Consider the C struct defined below: The base address of `student` is available in register R1. The field `student.grade` can be accessed efficiently…
  22. Question 22 (1 mark, Multiple choice) – Consider the following intermediate program in three address code Which one of the following corresponds to a *static single assignment* form of the…
  23. Question 23 (1 mark, Multiple choice) – Consider the following C code: The code suffers from which one of the following problems:
  24. Question 24 (1 mark, Multiple choice) – Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls `close` to terminate…
  25. Question 25 (1 mark, Multiple choice) – A sender S sends a message m to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following…
  26. Question 26 (1 mark, Multiple choice) – The following functional dependencies hold true for the relational schema R\V, W, X, Y, Z\: V W VW X Y VX Y Z Which of the following is irreducible…
  27. Question 27 (1 mark, Multiple choice) – Consider the following grammar: P xQRS Q yz z R w S y What is FOLLOW(Q)?
  28. Question 28 (1 mark, Multiple choice) – Threads of a process share
  29. Question 29 (1 mark, Numerical answer) – Let X be a Gaussian random variable with mean 0 and variance 2. Let Y = (X, 0) where (a, b) is the maximum of a and b. The median of Y is .
  30. Question 30 (1 mark, Numerical answer) – Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is .
  31. Question 31 (1 mark, Numerical answer) – Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0. [Karnaugh map with columns ba = 00, 01, 11, 10 and rows…
  32. Question 32 (1 mark, Numerical answer) – Consider the language L given by the regular expression (a + b)* b (a + b) over the alphabet \a, b\. The smallest number of states needed in a…
  33. Question 33 (1 mark, Numerical answer) – Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance of the schema EMP and a SQL query on it are given…
  34. Question 34 (1 mark, Numerical answer) – Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below: Process Arrival…
  35. Question 35 (1 mark, Numerical answer) – Consider a two-level cache hierarchy with L1 and L2 caches. An application incurs 1.4 memory accesses per instruction on average. For this…
  36. Question 36 (2 marks, Multiple choice) – Let G = (V, E) be *any* connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following…
  37. Question 37 (2 marks, Multiple choice) – A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory…
  38. Question 38 (2 marks, Multiple choice) – The value of x 1 x7 - 2x5 + 1x3 - 3x2 + 2
  39. Question 39 (2 marks, Multiple choice) – Let p, q, and r be propositions and the expression (p q) r be a contradiction. Then, the expression (r p) q is
  40. Question 40 (2 marks, Multiple choice) – Let u and v be two vectors in R2 whose Euclidean norms satisfy \ u\ = 2\ v\ . What is the value of such that w = u + v bisects the angle between u and…
  41. Question 41 (2 marks, Multiple choice) – Let A be n n real valued square symmetric matrix of rank 2 with i=1n j=1n A ij2 = 50. Consider the following statements. (I) One eigenvalue must be in…
  42. Question 42 (2 marks, Multiple choice) – A computer network uses polynomials over GF(2) for error checking with 8 bits as information bits and uses x3 + x + 1 as the generator polynomial to…
  43. Question 43 (2 marks, Multiple choice) – Consider a combination of T and D flip-flops connected as shown below. The output of the D flip-flop is connected to the input of the T flip-flop and…
  44. Question 44 (2 marks, Multiple choice) – If G is a grammar with productions S SaS aSb bSa SS where S is the start variable, then which one of the following strings is not generated by G?
  45. Question 45 (2 marks, Multiple choice) – Consider the following two functions. The output printed when `fun1(5)` is called is
  46. Question 46 (2 marks, Multiple choice) – Consider the C functions `foo` and `bar` given below: Invocations of `foo(3)` and `bar(3)` will result in:
  47. Question 47 (2 marks, Multiple choice) – Consider the context-free grammars over the alphabet \a, b, c\ given below. S and T are non-terminals. G 1: S aSb T, T cT G 2: S bSa T, T cT The…
  48. Question 48 (2 marks, Multiple choice) – Consider the following languages over the alphabet = \a, b, c\. Let L 1 = \an bn cm m, n 0\ and L 2 = \am bn cn m, n 0\. Which of the following are…
  49. Question 49 (2 marks, Multiple choice) – Let A and B be finite alphabets and let \# be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is *computable* if…
  50. Question 50 (2 marks, Multiple choice) – Recall that Belady's anomaly is that the page-fault rate may *increase* as the number of allocated frames increases. Now, consider the following…
  51. Question 51 (2 marks, Multiple choice) – Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be…
  52. Question 52 (2 marks, Multiple choice) – In a database system, unique timestamps are assigned to each transaction using Lamport's logical clock. Let TS(T 1) and TS(T 2) be the timestamps of…
  53. Question 53 (2 marks, Numerical answer) – Consider the following grammar: where `relop` is a relational operator (e.g., <, >, ...), ò refers to the empty statement, and `if`, `then`, `else`…
  54. Question 54 (2 marks, Numerical answer) – In a RSA cryptosystem, a participant A uses two prime numbers p = 13 and q = 17 to generate her public and private keys. If the public key of A is 35,…
  55. Question 55 (2 marks, Numerical answer) – The values of parameters for the Stop-and-Wait ARQ protocol are as given below: Bit rate of the transmission channel = 1 Mbps. Propagation delay from…
  56. Question 56 (2 marks, Numerical answer) – Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below. StudentName CourseName…
  57. Question 57 (2 marks, Numerical answer) – The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is .
  58. Question 58 (2 marks, Numerical answer) – Let A be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The problem is to find the smallest index i such that…
  59. Question 59 (2 marks, Numerical answer) – Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PC-relative addressing…
  60. Question 60 (2 marks, Numerical answer) – Instruction execution in a processor is divided into 5 stages, Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX), and…
  61. Question 61 (2 marks, Numerical answer) – Consider a 2-way set associative cache with 256 blocks and uses LRU replacement. Initially the cache is empty. Conflict misses are those misses which…
  62. Question 62 (2 marks, Numerical answer) – Consider the expression (a - 1) * (((b + c) / 3) + d). Let X be the minimum number of registers required by an *optimal* code generation (without any…
  63. Question 63 (2 marks, Numerical answer) – Consider the following C program. Recall that `strlen` is defined in `string.h` as returning a value of type `size t`, which is an `unsigned int`. The…
  64. Question 64 (2 marks, Numerical answer) – A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as a direct mapped cache, the length of…
  65. Question 65 (2 marks, Numerical answer) – The output of executing the following C program is .