GATE 2016 CS – Previous Year Questions with Solutions
All 65 questions of GATE 2016 CS with answers and explanations. Read each question, then practise it by topic or as a full paper.
Practise this paper in The GATE Grind →
- Question 1 – Out of the following four sentences, select the most suitable sentence with respect to grammar and usage.
- Question 2 – A rewording of something written or spoken is a .
- Question 3 – Archimedes said, "Give me a lever long enough and a fulcrum on which to place it, and I will move the world." The sentence above is an example of a…
- Question 4 – If 'relftaga' means carefree, 'otaga' means careful and 'fertaga' means careless, which of the following could mean 'aftercare'?
- Question 5 – A cube is built using 64 cubic blocks of side one unit. After it is built, one cubic block is removed from every corner of the cube. The resulting…
- Question 6 – A shaving set company sells 4 different types of razors, Elegance, Smooth, Soft and Executive. Elegance sells at Rs. 48, Smooth at Rs. 63, Soft at Rs.…
- Question 7 – Indian currency notes show the denomination indicated in at least seventeen languages. If this is not an indication of the nation's diversity, nothing…
- Question 8 – Consider the following statements relating to the level of poker play of four players P, Q, R and S. I. P always beats Q II. R always beats S III. S…
- Question 9 – If f(x) = 2x7 + 3x - 5, which of the following is a factor of f(x)?
- Question 10 – In a process, the number of cycles to failure decreases exponentially with an increase in load. At a load of 80 units, it takes 100 cycles for…
- Question 11 – Let p, q, r, s represent the following propositions. p: x \8, 9, 10, 11, 12\ q: x is a composite number r: x is a perfect square s: x is a prime…
- Question 12 – Let a n be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for a n?
- Question 13 – x 4 (x - 4)x - 4 = .
- Question 14 – A probability density function on the interval [a, 1] is given by 1/x2 and outside this interval the value of the function is zero. The value of a is…
- Question 15 – Two eigenvalues of a 3 3 real matrix P are (2 + -1) and 3. The determinant of P is .
- Question 16 – Consider the Boolean operator \# with the following properties: x \# 0 = x, x \# 1 = x, x \# x = 0 and x \# x = 1. Then x \# y is equivalent to
- Question 17 – The 16-bit 2's complement representation of an integer is 1111 1111 1111 0101; its decimal representation is .
- Question 18 – We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to…
- Question 19 – A processor can support a maximum memory of 4 GB, where the memory is word-addressable (a word consists of two bytes). The size of the address bus of…
- Question 20 – A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is…
- Question 21 – Consider the following directed graph: [Directed graph on vertices a, b, c, d, e, f with edges a→b, b→c, c→f, a→d, d→e, e→f.] The number of different…
- Question 22 – Consider the following C program. Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?
- Question 23 – The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
- Question 24 – Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of…
- Question 25 – Consider the following C program. The output of the program is .
- Question 26 – Which of the following languages is generated by the given grammar? S aS bS
- Question 27 – Which of the following decision problems are undecidable? I. Given NFAs N 1 and N 2, is L(N 1) L(N 2) = ? II. Given a CFG G = (N, , P, S) and a string…
- Question 28 – Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive…
- Question 29 – Consider the following code segment. The minimum number of *total* variables required to convert the above code segment to *static single assignment*…
- Question 30 – Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the…
- Question 31 – Which of the following is NOT a superkey in a relational schema with attributes V, W, X, Y, Z and primary key VY?
- Question 32 – Which one of the following is NOT a part of the ACID properties of database transactions?
- Question 33 – A database of research articles in a journal uses the following schema. (Volume, Number, StartPage, EndPage, Title, Year, Price) The primary key is…
- Question 34 – Which one of the following protocols is NOT used to resolve one form of address to another one?
- Question 35 – Which of the following is/are example(s) of stateful application layer protocols? (i) HTTP (ii) FTP (iii) TCP (iv) POP3
- Question 36 – The coefficient of x12 in (x3 + x4 + x5 + x6 + )3 is .
- Question 37 – Consider the recurrence relation a 1 = 8, a n = 6n2 + 2n + a n-1. Let a 99 = K 104. The value of K is .
- Question 38 – A function f : N+ N+, defined on the set of positive integers N+, satisfies the following properties: f(n) = f(n/2) if n is even f(n) = f(n+5) if n is…
- Question 39 – Consider the following experiment. Step 1. Flip a fair coin twice. Step 2. If the outcomes are (TAILS, HEADS) then output Y and stop. Step 3. If the…
- Question 40 – Consider the two cascaded 2-to-1 multiplexers as shown in the figure. [Figure: The first 2-to-1 MUX has input 0 tied to 0, input 1 tied to R, and…
- Question 41 – The size of the data count register of a DMA controller is 16 bits. The processor needs to transfer a file of 29,154 kilobytes from disk to main…
- Question 42 – The stage delays in a 4-stage pipeline are 800, 500, 400 and 300 picoseconds. The first stage (with delay 800 picoseconds) is replaced with a…
- Question 43 – Consider a carry lookahead adder for adding two n-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder…
- Question 44 – The following function computes the maximum value contained in an integer array `p[]` of size n (n 1). The missing loop condition is
- Question 45 – What will be the output of the following C program?
- Question 46 – What will be the output of the following pseudo-code when parameters are passed by reference and dynamic scoping is assumed?
- Question 47 – An operator `delete(i)` for a binary heap data structure is to be designed to delete the item in the i-th node. Assume that the heap is implemented in…
- Question 48 – Consider the weighted undirected graph with 4 vertices, where the weight of edge \i, j\ is given by the entry W ij in the matrix W. W = bmatrix 0 & 2…
- Question 49 – Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum…
- Question 50 – G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements…
- Question 51 – Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns the element at the head of the queue Q without removing it…
- Question 52 – Consider the following context-free grammars: G 1: S aS B, B b bB G 2: S aA bB, A aA B , B bB Which one of the following pairs of languages is…
- Question 53 – Consider the transition diagram of a PDA given below with input alphabet = \a, b\ and stack alphabet = \X, Z\. Z is the initial stack symbol. Let L…
- Question 54 – Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y reduces to W, and…
- Question 55 – The attributes of three arithmetic operators in some programming language are given below. Operator Precedence Associativity Arity --- --- --- --- +…
- Question 56 – Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals \S, A\ and terminals \a, b\. S aA print 1 S a print 2 A Sb print…
- Question 57 – Consider a computer system with 40-bit virtual addressing and page size of sixteen kilobytes. If the computer system has a one-level page table per…
- Question 58 – Consider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The C-LOOK scheduling algorithm is used. The head…
- Question 59 – Consider a computer system with ten physical page frames. The system is provided with an access sequence (a 1, a 2, , a 20, a 1, a 2, , a 20), where…
- Question 60 – Consider the following proposed solution for the critical section problem. There are n processes: P 0 P n-1. In the code, function `pmax` returns an…
- Question 61 – Consider the following two phase locking protocol. Suppose a transaction T accesses (for read or write operations), a certain set of objects \O 1, , O…
- Question 62 – Consider that B wants to send a message m that is digitally signed to A. Let the pair of private and public keys for A and B be denoted by K x- and K…
- Question 63 – An IP datagram of size 1000 bytes arrives at a router. The router has to forward this packet on a link whose MTU (maximum transmission unit) is 100…
- Question 64 – For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 megabyte and the maximum output…
- Question 65 – A sender uses the Stop-and-Wait ARQ protocol for reliable transmission of frames. Frames are of size 1000 bytes and the transmission rate at the…