GATE CS 2017 Set 2 question paper: all 65 questions with answers and solutions

Computer Science and Information Technology

55 questions, 85 marks

Digital LogicMCQ1 markEasy (estimate)
Q.1 (CS Q.1)
The representation of the value of a 16-bit unsigned integer $Y$ in hexadecimal number system is $BCA9$ . The representation of the value of $Y$ in octal number system is
Number Representations and Computer Arithmetic
Programming in CMCQ1 markEasy (estimate)
Q.2 (CS Q.2)
Match the following: | Item | Description | | :--- | :--- | | (P) static char var; | (i) Sequence of memory locations to store addresses | | (Q) m = malloc(10); m = NULL; |...
Functions, Recursion, Scope and Storage Classes · Structures, Unions and Dynamic Memory Allocation
AlgorithmsMCQ1 markEasy (estimate)
Q.3 (CS Q.3)
Match the algorithms with their time complexities: | Algorithm | Time complexity | | :--- | :--- | | (P) Towers of Hanoi with $n$ disks | (i) $Θ (n^{2})$ | | (Q) Binary search...
Asymptotic Analysis and Time/Space Complexity · Searching and Sorting Algorithms
Theory of ComputationMCQ1 markEasy (estimate)
Q.4 (CS Q.4)
Let $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} \cup L_{2}$ is context-free. II.…
Context-Free Grammars, Pushdown Automata and CFLs
Compiler DesignMCQ1 markEasy (estimate)
Q.5 (CS Q.5)
Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: | Input | Compiler Phase | | :--- | :--- | | (P) Syn...
Lexical Analysis · Parsing and Syntax Analysis (LL and LR)
Compiler DesignMCQ1 markEasy (estimate)
Q.6 (CS Q.6)
Which 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 Cano...
Parsing and Syntax Analysis (LL and LR)
Operating SystemsMCQ1 markEasy (estimate)
Q.7 (CS Q.7)
Which of the following is/are shared by all the threads in a process? I. Program counter II. Stack III. Address space IV. Registers
Processes, Threads and System Calls
Operating SystemsMCQ1 markEasy (estimate)
Q.8 (CS Q.8)
In 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. Indexed
File Systems, I/O and Disk Scheduling
Computer NetworksMCQ1 markEasy (estimate)
Q.9 (CS Q.9)
Consider 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 ve...
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF · Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Engineering MathematicsMCQ1 markMedium (estimate)
Q.10 (CS Q.10)
If $f (x) = R sin (\frac{π x}{2}) + S$ , $f^{'} (\frac{1}{2}) = 2$ and $\int_{0}^{1} f (x) d x = \frac{2 R}{π}$ , then the constants $R$ and $S$ are, respe...
Calculus
Engineering MathematicsMCQ1 markEasy (estimate)
Q.11 (CS Q.11)
Let $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 pl...
Propositional and First-Order Logic
Digital LogicMCQ1 markMedium (estimate)
Q.12 (CS Q.12)
Given the following binary number in 32-bit (single precision) IEEE-754 format: 00111110011011010000000000000000 The decimal value closest to this floating-point number is
Number Representations and Computer Arithmetic
Data StructuresMCQ1 markEasy (estimate)
Q.13 (CS Q.13)
A 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 exte...
Stacks and Queues · Arrays and Linked Lists
Programming in CMCQ1 markEasy (estimate)
Q.14 (CS Q.14)
Consider the following function implemented in 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 in...
Pointers, Arrays and Strings
AlgorithmsMCQ1 markMedium (estimate)
Q.15 (CS Q.15)
The 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 b...
Graph Traversals, Topological Sort and Connectivity · Graph Representations and Disjoint Sets
Theory of ComputationMCQ1 markEasy (estimate)
Q.16 (CS Q.16)
Identify the language generated by the following grammar, where $S$ is the start variable.…
Context-Free Grammars, Pushdown Automata and CFLs
DatabasesMCQ1 markMedium (estimate)
Q.17 (CS Q.17)
An 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 condi...
ER Model and Relational Schema Design
Computer NetworksMCQ1 markMedium (estimate)
Q.18 (CS Q.18)
Consider 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...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
DatabasesNAT1 markMedium (estimate)
Q.19 (CS Q.19)
Consider the following tables T1 and T2. Table T1 | P | Q | | :-: | :-: | | 2 | 2 | | 3 | 8 | | 7 | 3 | | 5 | 8 | | 6 | 9 | | 8 | 5 | | 9 | 8 | Table T2 | R | S | | :-:...
ER Model and Relational Schema Design · SQL Queries and Integrity Constraints
Computer NetworksNAT1 markEasy (estimate)
Q.20 (CS Q.20)
The maximum number of IPv4 router addresses that can be listed in the record route (RR) option field of an IPv4 header is
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Engineering MathematicsNAT1 markMedium (estimate)
Q.21 (CS Q.21)
Consider 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 Has...
Sets, Relations, Functions, Partial Orders and Lattices
Engineering MathematicsNAT1 markEasy (estimate)
Q.22 (CS Q.22)
Let $P = 123 1 - 3 - 2 - 1 43$ and $Q = - 1 65 - 2 1210 - 1 65$ be two matrices....
Linear Algebra
Engineering MathematicsNAT1 markEasy (estimate)
Q.23 (CS Q.23)
$G$ 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
Graph Theory
Digital LogicNAT1 markEasy (estimate)
Q.24 (CS Q.24)
Consider a quadratic equation $x^{2} - 13 x + 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 =$
Number Representations and Computer Arithmetic
Theory of ComputationNAT1 markMedium (estimate)
Q.25 (CS Q.25)
The minimum possible number of states of a deterministic finite automaton that accepts the regular language…
Regular Expressions, Finite Automata and Regular Languages
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.26 (CS Q.26)
P and Q are considering to apply for a job. The probability that P applies for the job is $\frac{1}{4}$ , the probability that P applies for the job given that Q applies for the...
Probability and Statistics
Digital LogicMCQ2 marksMedium (estimate)
Q.27 (CS Q.27)
If $w, x, y, z$ are Boolean variables, then which one of the following is INCORRECT?
Boolean Algebra and Logic Minimization
Digital LogicMCQ2 marksMedium (estimate)
Q.28 (CS Q.28)
Given $f (w, x, y, z) = \sum m (0, 1, 2, 3, 7, 8, 10) + \sum 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-s...
Boolean Algebra and Logic Minimization
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.29 (CS Q.29)
In 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...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
AlgorithmsMCQ2 marksMedium (estimate)
Q.30 (CS Q.30)
Consider the recurrence function $T (n) = {2 T (n) + 1, 2, n > 2 0 < n \leq 2$ Then $T (n)$ in terms of $Θ$ notation is
Asymptotic Analysis and Time/Space Complexity
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.31 (CS Q.31)
For any discrete random variable $X$ , with probability mass function…
Probability and Statistics
Compiler DesignMCQ2 marksMedium (estimate)
Q.32 (CS Q.32)
Consider the following expression grammar $G$ : $E T F \to E - T ∣ T \to T + F ∣ F \to (E) ∣ id$ Which of the following g...
Parsing and Syntax Analysis (LL and LR)
Operating SystemsMCQ2 marksEasy (estimate)
Q.33 (CS Q.33)
A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below: | Process | Current Allocation | Maximum Requir...
Deadlock Prevention, Avoidance and Detection
Computer NetworksMCQ2 marksEasy (estimate)
Q.34 (CS Q.34)
Consider 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...
Data Link Layer: Framing, Error Detection and Sliding Window
Computer NetworksMCQ2 marksEasy (estimate)
Q.35 (CS Q.35)
Consider two hosts $X$ and $Y$ , connected by a single direct link of rate $1 0^{6}$ bits/sec. The distance between the two hosts is $10, 000$ km and the propagation speed along the...
OSI/TCP-IP Layering, Physical Layer and Switching
Data StructuresMCQ2 marksMedium (estimate)
Q.36 (CS Q.36)
The 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:
Binary Trees, Binary Search Trees and Balanced Trees
Programming in CMCQ2 marksMedium (estimate)
Q.37 (CS Q.37)
Consider 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. while (r >= y...
Data Types, Operators and Control Flow
AlgorithmsMCQ2 marksMedium (estimate)
Q.38 (CS Q.38)
Consider the following C function. 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…
Asymptotic Analysis and Time/Space Complexity
Theory of ComputationMCQ2 marksMedium (estimate)
Q.39 (CS Q.39)
Let $δ$ denote the transition function and $δ^$ denote the extended transition function of the $ϵ$ -NFA whose transition table is given below: | $δ$ |...
Regular Expressions, Finite Automata and Regular Languages
Theory of ComputationMCQ2 marksMedium (estimate)
Q.40 (CS Q.40)
Consider the following languages.…
Context-Free Grammars, Pushdown Automata and CFLs · Turing Machines and Chomsky Hierarchy
Theory of ComputationMCQ2 marksEasy (estimate)
Q.41 (CS Q.41)
Let $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 Tu...
Decidability, Reducibility and Undecidability
Digital LogicMCQ2 marksMedium (estimate)
Q.42 (CS Q.42)
The next state table of a 2-bit saturating up-counter is given below. | $Q_{1}$ | $Q_{0}$ | $Q_{1}^{+}$ | $Q_{0}^{+}$ | | :-: | :-: | :-: | :-: | | 0 | 0 | 0 | 1 | | 0 | 1 | 1 | 0 | | 1 | 0...
Sequential Circuits, Counters and Registers
Programming in CNAT2 marksMedium (estimate)
Q.43 (CS Q.43)
Consider the following snippet of a C program. Assume that swap(&x, &y) exchanges the contents of x and y. int main() { int array[] = {3, 5, 1, 4, 6, 2}; int done = 0...
Pointers, Arrays and Strings · Searching and Sorting Algorithms
DatabasesNAT2 marksHard (estimate)
Q.44 (CS Q.44)
Two transactions $T_{1}$ and $T_{2}$ are given as $T_{1} T_{2} : r_{1} (X) w_{1} (X) r_{1} (Y) w_{1} (Y) : r_{2} (Y) w_{2} (Y) r_{2} (Z) w_{2} (Z)$ where $r_{i} (V)$ denotes a...
Transactions, Serializability and Concurrency Control
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.45 (CS Q.45)
The read access times and the hit ratios for different caches in a memory hierarchy are as given below. | Cache | Read access time (in nanoseconds) | Hit ratio | | :--- | :---:...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
DatabasesNAT2 marksMedium (estimate)
Q.46 (CS Q.46)
Consider the following database table named top_scorer. | player | country | goals | | :--- | :--- | :---: | | Klose | Germany | 16 | | Ronaldo | Brazil | 15 | | G Müller | Ge...
SQL Queries and Integrity Constraints
Engineering MathematicsNAT2 marksMedium (estimate)
Q.47 (CS Q.47)
If the ordinary generating function of a sequence ${a_{n}}_{n = 0}^{\infty}$ is $\frac{1 + z}{( 1 - z ) ^{3}}$ , then $a_{3} - a_{0}$ is equal to
Combinatorics, Counting, Recurrence Relations and Generating Functions
Engineering MathematicsNAT2 marksEasy (estimate)
Q.48 (CS Q.48)
If a random variable $X$ has a Poisson distribution with mean 5, then the expectation $E [(X + 2)^{2}]$ equals
Probability and Statistics
DatabasesNAT2 marksMedium (estimate)
Q.49 (CS Q.49)
In 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
File Organization, B-Trees and B+ Trees Indexing
AlgorithmsNAT2 marksMedium (estimate)
Q.50 (CS Q.50)
A 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: | Character | Probability...
Greedy Algorithms
Operating SystemsNAT2 marksMedium (estimate)
Q.51 (CS Q.51)
Consider 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...
CPU Scheduling
Engineering MathematicsNAT2 marksEasy (estimate)
Q.52 (CS Q.52)
If the characteristic polynomial of a $3 \times 3$ matrix $M$ over $R$ (the set of real numbers) is $λ^{3} - 4 λ^{2} + aλ + 30$ , $a \in R$ , and on...
Linear Algebra
Computer Organization and ArchitectureNAT2 marksEasy (estimate)
Q.53 (CS Q.53)
Consider 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 w...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Programming in CNAT2 marksEasy (estimate)
Q.54 (CS Q.54)
Consider the following C program. #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...
Data Types, Operators and Control Flow
Programming in CNAT2 marksMedium (estimate)
Q.55 (CS Q.55)
Consider the following C program. #include <stdio.h> #include <string.h> int main() { char* c = "GATECSIT2017"; char* p = c; printf("%d", (int) strlen(c + 2[p] - 6[p] - 1))...
Pointers, Arrays and Strings

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.56 (GA Q.1)
Choose the option with words that are not synonyms.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.57 (GA Q.2)
Saturn is ________ to be seen on a clear night with the naked eye.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.58 (GA Q.3)
There 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....
Analytical and Logical Reasoning
General AptitudeMCQ1 markEasy (estimate)
Q.59 (GA Q.4)
A 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 e...
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.60 (GA Q.5)
There are 3 red socks, 4 green socks and 3 blue socks. You choose 2 socks. The probability that they are of the same colour is
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.61 (GA Q.6)
“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....
Reading Comprehension and Verbal Deduction · Verbal Ability and Grammar
General AptitudeMCQ2 marksMedium (estimate)
Q.62 (GA Q.7)
There 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 ar...
Analytical and Logical Reasoning
General AptitudeMCQ2 marksMedium (estimate)
Q.63 (GA Q.8)
$X$ is a 30 digit number starting with the digit 4 followed by the digit 7. Then the number $X^{3}$ will have
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.64 (GA Q.9)
The number of roots of $e^{x} + 0.5 x^{2} - 2 = 0$ in the range $[- 5, 5]$ is
Quantitative Aptitude · Calculus
General AptitudeMCQ2 marksEasy (estimate)
Q.65 (GA Q.10)
An air pressure contour line joins locations in a region having the same atmospheric pressure. The following is an air pressure contour plot of a geographical region. Contour li...
Data Interpretation and Graphs · Spatial Aptitude