Previous year paper
GATE CS 2018
GATE 2018 Computer Science and Information Technology (CS)
General Aptitude
10 questions, 15 marks
Q.1 (GA Q.1)
“From where are they bringing their books? ________ bringing _______ books from _____.” The words that best fill the blanks in the above sentence are
Verbal Ability and Grammar
Q.2 (GA Q.2)
“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 is
Verbal Ability and Grammar
Q.3 (GA Q.3)
The area of a square is . What is the area of the circle which has the diagonal of the square as its diameter?
Quantitative Aptitude
Q.4 (GA Q.4)
What 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?
Quantitative Aptitude
Q.5 (GA Q.5)
What is the missing number in the following sequence? 2, 12, 60, 240, 720, 1440, _____, 0
Quantitative Aptitude
Q.6 (GA Q.6)
In 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 femal...
Quantitative Aptitude
Q.7 (GA Q.7)
If and , , , what is the value of the product ?
Quantitative Aptitude
Q.8 (GA Q.8)
In 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 t...
Quantitative Aptitude
Q.9 (GA Q.9)
In the figure below, is equal to ____________ . Geometric diagram showing points A, B, C, D, E, F with line segments EDA and ABF, and lines EB and FD i...
Quantitative Aptitude
Q.10 (GA Q.10)
A 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
Computer Science and Information Technology
55 questions, 85 marks
Q.11 (CS Q.1)
Which one of the following is a closed form expression for the generating function of the sequence , where for all ?
Combinatorics, Counting, Recurrence Relations and Generating Functions
Q.12 (CS Q.2)
Consider the following C program. #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", *(...
Pointers, Arrays and Strings
Q.13 (CS Q.3)
A 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...
Stacks and Queues
Q.14 (CS Q.4)
Let and denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?
Boolean Algebra and Logic Minimization
Q.15 (CS Q.5)
Consider the following processor design characteristics. I. Register-to-register arithmetic operations only II. Fixed-length instruction format III. Hardwired control unit Which...
Machine Instructions and Addressing Modes
Q.16 (CS Q.6)
Let be an NFA with states. Let be the number of states of a minimal DFA which is equivalent to . Which one of the following is necessarily true?
Regular Expressions, Finite Automata and Regular Languages
Q.17 (CS Q.7)
The set of all recursively enumerable languages is
Decidability, Reducibility and Undecidability
Q.18 (CS Q.8)
Which one of the following statements is FALSE?
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Q.19 (CS Q.9)
The 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...
Processes, Threads and System Calls
Q.20 (CS Q.10)
Consider 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 av...
Memory Management and Virtual Memory
Q.21 (CS Q.11)
In an Entity-Relationship (ER) model, suppose is a many-to-one relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in and that th...
ER Model and Relational Schema Design
Q.22 (CS Q.12)
Consider 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...
Relational Algebra and Tuple Relational Calculus
Q.23 (CS Q.13)
Match 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. 16
OSI/TCP-IP Layering, Physical Layer and Switching
Q.24 (CS Q.14)
Consider 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...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Q.25 (CS Q.15)
Two 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...
Probability and Statistics
Q.26 (CS Q.16)
The value of correct to three decimal places (assuming that ) is _____.
Calculus
Q.27 (CS Q.17)
Consider a matrix where . Note that denotes the transpose of . The large...
Linear Algebra
Q.28 (CS Q.18)
The chromatic number of the following graph is _______. 6-vertex undirected graph consisting of an outer 4-cycle and two inner vertices with diagonal cross-connections to find c...
Graph Theory
Q.29 (CS Q.19)
Let be a finite group on 84 elements. The size of a largest possible proper subgroup of is ________.
Monoids and Groups
Q.30 (CS Q.20)
The 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 pat...
Binary Trees, Binary Search Trees and Balanced Trees
Q.31 (CS Q.21)
Consider the following C program: #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*...
Functions, Recursion, Scope and Storage Classes
Q.32 (CS Q.22)
Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops. Sequential circuit with two positive edge-triggered D f...
Sequential Circuits, Counters and Registers
Q.33 (CS Q.23)
A 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 . The time taken to...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Q.34 (CS Q.24)
Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of instances. Resource instances can be requested and...
Deadlock Prevention, Avoidance and Detection
Q.35 (CS Q.25)
Consider a long-lived TCP session with an end-to-end bandwidth of 1 Gbps (= bits-per-second). The session starts with a sequence number of 1234. The minimum time (in seco...
OSI/TCP-IP Layering, Physical Layer and Switching
Q.36 (CS Q.26)
Consider a matrix whose only eigenvectors are the multiples of . Consider the following statements: (I) does not have an inverse (I...
Linear Algebra
Q.37 (CS Q.27)
Let 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 R...
Monoids and Groups
Q.38 (CS Q.28)
Consider the first-order logic sentence where…
Propositional and First-Order Logic
Q.39 (CS Q.29)
Consider the following C program: #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 = *s...
Pointers, Arrays and Strings
Q.40 (CS Q.30)
Let be a simple undirected graph. Let be a depth first search tree of . Let be a breadth first search tree of . Consider the following statements. (I) No e...
Graph Traversals, Topological Sort and Connectivity
Q.41 (CS Q.31)
Assume that multiplying a matrix of dimension with another matrix of dimension requires scalar multiplications. Computing the product...
Dynamic Programming
Q.42 (CS Q.32)
Consider the following C code. Assume that unsigned long int type length is 64 bits. unsigned long int fun(unsigned long int n){ unsigned long int i, j = 0, sum = 0; for (i = n;...
Functions, Recursion, Scope and Storage Classes
Q.43 (CS Q.33)
Consider the unsigned 8-bit fixed point binary number representation below, where the position of the binary point...
Number Representations and Computer Arithmetic
Q.44 (CS Q.34)
The size of the physical address space of a processor is bytes. The word length is bytes. The capacity of cache memory is bytes. The size of each cache block i...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Q.45 (CS Q.35)
Consider the following languages: I. II.…
Context-Free Grammars, Pushdown Automata and CFLs
Q.46 (CS Q.36)
Consider the following problems. denotes the language generated by a grammar . denotes the language accepted by a machine . (I) For an unrestricted grammar…
Decidability, Reducibility and Undecidability
Q.47 (CS Q.37)
A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet .…
Lexical Analysis
Q.48 (CS Q.38)
Consider the following parse tree for the expression
a#b$c$d#e#f, involving two binary operators$and#. Parse tree for the expression a#bd#e#f showing precedence and...Parsing and Syntax Analysis (LL and LR)
Q.49 (CS Q.39)
In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum reso...
Deadlock Prevention, Avoidance and Detection
Q.50 (CS Q.40)
Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is . Three semaphores empty, full and mutex are defined with respecti...
Process Synchronization and Concurrency
Q.51 (CS Q.41)
Consider the relations and , where is a primary key and is a foreign key referencing . Consider the query ...
Relational Algebra and Tuple Relational Calculus
Q.52 (CS Q.42)
Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys. S...
Functional Dependencies and Normalization
Q.53 (CS Q.43)
Let be a graph with vertices, with each vertex labelled by a distinct permutation of the numbers . There is an edge between vertices and if...
Graph Theory
Q.54 (CS Q.44)
Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (), medium () and low (). Let denote the probability that Guwahati has high te...
Probability and Statistics
Q.55 (CS Q.45)
Consider the following program written in pseudo-code. Assume that x and y are integers. Count(x,y) { if (y != 1){ if (x != 1) { print("*"); Count(x/2, y); } else { y = y-1; Cou...
Functions, Recursion, Scope and Storage Classes
Q.56 (CS Q.46)
The number of possible min-heaps containing each value from exactly once is _____.
Binary Heaps and Priority Queues
Q.57 (CS Q.47)
Consider the following undirected graph G: Undirected weighted graph G with 5 vertices and 7 edges, with edge weights 1, 3, 4, 4, 4, 5, and variable x. Choose a value for th...
Greedy Algorithms
Q.58 (CS Q.48)
Consider 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...
Dynamic Programming
Q.59 (CS Q.49)
Consider the minterm list form of a Boolean function given below. Here, denotes a minterm and den...
Boolean Algebra and Logic Minimization
Q.60 (CS Q.50)
The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback...
Instruction Pipelining and Hazards
Q.61 (CS Q.51)
A 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 instr...
Machine Instructions and Addressing Modes
Q.62 (CS Q.52)
Given a language , define as follows: The order of a lang...
Regular Expressions, Finite Automata and Regular Languages
Q.63 (CS Q.53)
Consider 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 follow...
File Systems, I/O and Disk Scheduling
Q.64 (CS Q.54)
Consider 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 Maximu...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Q.65 (CS Q.55)
Consider 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 car...
OSI/TCP-IP Layering, Physical Layer and Switching