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

Computer Science and Information Technology

55 questions, 85 marks

Engineering MathematicsMCQ1 markEasy (estimate)
Q.1 (CS Q.1)
The statement $(\neg p) ⟹ (\neg q)$ is logically equivalent to which of the statements below? I. $p ⟹ q$ II. $q ⟹ p$ III. $(\neg q) \lor p$ IV.…
Propositional and First-Order Logic
Engineering MathematicsMCQ1 markMedium (estimate)
Q.2 (CS Q.2)
Consider the first-order logic sentence $F : \forall x (\exists y R (x, y))$ . Assuming non-empty logical domains, which of the sentences below are implied by $F$ ? I.…
Propositional and First-Order Logic
Engineering MathematicsMCQ1 markEasy (estimate)
Q.3 (CS Q.3)
Let $c_{1}, \dots, c_{n}$ be scalars, not all zero, such that $\sum_{i = 1}^{n} c_{i} a_{i} = 0$ where $a_{i}$ are column vectors in $R^{n}$ . Consider the set of linear equations…
Linear Algebra
AlgorithmsMCQ1 markEasy (estimate)
Q.4 (CS Q.4)
Consider the following functions from positive integers to real numbers: $10, n, n, lo g_{2} n, \frac{100}{n}$ The CORRECT arrangement of the abov...
Asymptotic Analysis and Time/Space Complexity
AlgorithmsMCQ1 markEasy (estimate)
Q.5 (CS Q.5)
Consider the following table: Algorithm Design Paradigm (P) Kruskal (i) Divide and Conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall (iii) Dynamic Programming Match the algor...
Greedy Algorithms · Dynamic Programming · Divide and Conquer
Data StructuresMCQ1 markEasy (estimate)
Q.6 (CS Q.6)
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.
Binary Trees, Binary Search Trees and Balanced Trees
Digital LogicMCQ1 markEasy (estimate)
Q.7 (CS Q.7)
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$ in this represent...
Number Representations and Computer Arithmetic
Programming in CMCQ1 markMedium (estimate)
Q.8 (CS Q.8)
Consider the C code fragment given below. typedef struct node { int data; struct node* next; } node; void join(node* m, node* n) { node* p = n; while (p->next != NULL) { p = p->...
Pointers, Arrays and Strings · Arrays and Linked Lists
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.9 (CS Q.9)
When two 8-bit numbers $A_{7} \dots A_{0}$ and $B_{7} \dots B_{0}$ in 2's complement representation (with $A_{0}$ and $B_{0}$ as the least significant bits) are added using a ripple-carry a...
ALU, Datapath and Control Unit · Number Representations and Computer Arithmetic
Theory of ComputationMCQ1 markMedium (estimate)
Q.10 (CS Q.10)
Consider the following context-free grammar over the alphabet $Σ = {a, b, c}$ with $S$ as the start symbol: $S \to ab S c T ∣ ab c T$ $T \to b T ∣ b$ Which one of the...
Context-Free Grammars, Pushdown Automata and CFLs
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.11 (CS Q.11)
Consider the C struct defined below: struct data { int marks[100]; char grade; int cnumber; }; struct data student; The base address of student is available in register R1. Th...
Machine Instructions and Addressing Modes
Compiler DesignMCQ1 markEasy (estimate)
Q.12 (CS Q.12)
Consider the following intermediate program in three address code: p = a - b q = p * c p = u * v q = p + q Which one of the following corresponds to a static single assi...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Programming in CMCQ1 markMedium (estimate)
Q.13 (CS Q.13)
Consider the following C code: #include <stdio.h> #include <stdlib.h> int *assignval(int *x, int val) { *x = val; return x; } void main() { int *x = malloc(sizeof(int)); if (NUL...
Structures, Unions and Dynamic Memory Allocation · Pointers, Arrays and Strings
Computer NetworksMCQ1 markEasy (estimate)
Q.14 (CS Q.14)
Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls close to terminate the connection and a FIN segm...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Computer NetworksMCQ1 markMedium (estimate)
Q.15 (CS Q.15)
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 security violations can take pl...
Application Layer: DNS, HTTP, SMTP, FTP
DatabasesMCQ1 markMedium (estimate)
Q.16 (CS Q.16)
The following functional dependencies hold true for the relational schema $R (V, W, X, Y, Z)$ : $V \to W$ $V W \to X$ $Y \to V X$ $Y \to Z$ Which of the following is irreduc...
Functional Dependencies and Normalization
Compiler DesignMCQ1 markEasy (estimate)
Q.17 (CS Q.17)
Consider the following grammar: $P \to x QR S$ $Q \to y z ∣ z$ $R \to w ∣ ϵ$ $S \to y$ What is $FOLLOW (Q)$ ?
Parsing and Syntax Analysis (LL and LR)
Operating SystemsMCQ1 markEasy (estimate)
Q.18 (CS Q.18)
Threads of a process share
Processes, Threads and System Calls
Engineering MathematicsNAT1 markEasy (estimate)
Q.19 (CS Q.19)
Let $X$ be a Gaussian random variable with mean 0 and variance $σ^{2}$ . Let $Y = max (X, 0)$ where $max (a, b)$ is the maximum of $a$ and $b$ . The median of $Y$ is ______.
Probability and Statistics
Engineering MathematicsNAT1 markEasy (estimate)
Q.20 (CS Q.20)
Let $T$ be a tree with 10 vertices. The sum of the degrees of all the vertices in $T$ is ______.
Graph Theory
Digital LogicNAT1 markMedium (estimate)
Q.21 (CS Q.21)
Consider the Karnaugh map given below, where X represents "don't care" and blank represents 0. 4 by 4 Karnaugh map for a 4-variable Boolean logic function with row variables dc...
Boolean Algebra and Logic Minimization · Combinational Circuits
Theory of ComputationNAT1 markEasy (estimate)
Q.22 (CS Q.22)
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 deterministic finite-state au...
Regular Expressions, Finite Automata and Regular Languages
DatabasesNAT1 markMedium (estimate)
Q.23 (CS Q.23)
Consider a database that has the relation schema $EMP (EmpId, EmpName, DeptName)$ . An instance of the schema EMP and a SQL query on it are given below...
SQL Queries and Integrity Constraints
Operating SystemsNAT1 markEasy (estimate)
Q.24 (CS Q.24)
Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below: Process Arrival time Burst time P1 0 7 P2 3...
CPU Scheduling
Computer Organization and ArchitectureNAT1 markMedium (estimate)
Q.25 (CS Q.25)
Consider a two-level cache hierarchy with L1 and L2 caches. An application incurs 1.4 memory accesses per instruction on average. For this application, the miss rate of L1 cache...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
AlgorithmsMCQ2 marksEasy (estimate)
Q.26 (CS Q.26)
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 statements: (I) Minimum Spann...
Greedy Algorithms · Graph Theory
Operating SystemsMCQ2 marksMedium (estimate)
Q.27 (CS Q.27)
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 locations. All locks...
Deadlock Prevention, Avoidance and Detection · Process Synchronization and Concurrency
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.28 (CS Q.28)
The value of $lim_{x \to 1} \frac{x ^{7} - 2 x ^{5} + 1}{x ^{3} - 3 x ^{2} + 2}$
Calculus
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.29 (CS Q.29)
Let $p, q$ , and $r$ be propositions and the expression $(p \to q) \to r$ be a contradiction. Then, the expression $(r \lor p) \to q$ is
Propositional and First-Order Logic
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.30 (CS Q.30)
Let $u$ and $v$ be two vectors in $R^{2}$ whose Euclidean norms satisfy $∥ u ∥ = 2∥ v ∥$ . What is the value of $α$ such that $w = u + α v$ bisects the angle be...
Linear Algebra
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.31 (CS Q.31)
Let $A$ be an $n \times n$ real valued square symmetric matrix of rank 2 with $\sum_{i = 1}^{n} \sum_{j = 1}^{n} A_{ij}^{2} = 50$ . Consider the following statements: (I) One eigenvalue mu...
Linear Algebra
Computer NetworksMCQ2 marksEasy (estimate)
Q.32 (CS Q.32)
A computer network uses polynomials over $GF (2)$ for error checking with 8 bits as information bits and uses $x^{3} + x + 1$ as the generator polynomial to generate the che...
Data Link Layer: Framing, Error Detection and Sliding Window
Digital LogicMCQ2 marksEasy (estimate)
Q.33 (CS Q.33)
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 the output of the T flip-fl...
Sequential Circuits, Counters and Registers
Theory of ComputationMCQ2 marksEasy (estimate)
Q.34 (CS Q.34)
If $G$ is a grammar with productions $S \to S a S ∣ a S b ∣ b S a ∣ S S ∣ ϵ$ where $S$ is the start variable, then which one of the following strings is not genera...
Context-Free Grammars, Pushdown Automata and CFLs
Programming in CMCQ2 marksMedium (estimate)
Q.35 (CS Q.35)
Consider the following two functions. void fun1(int n) { if (n == 0) return; printf("%d", n); fun2(n - 2); printf("%d", n); } void fun2(int n) { if (n == 0) return; printf("%d",...
Functions, Recursion, Scope and Storage Classes
Programming in CMCQ2 marksMedium (estimate)
Q.36 (CS Q.36)
Consider the C functions foo and bar given below: int foo(int val) { int x = 0; while (val > 0) { x = x + foo(val--); } return val; } int bar(int val) { int x = 0; while (val >...
Functions, Recursion, Scope and Storage Classes
Theory of ComputationMCQ2 marksEasy (estimate)
Q.37 (CS Q.37)
Consider the context-free grammars over the alphabet ${a, b, c}$ given below. $S$ and $T$ are non-terminals. $G_{1} : S \to a S b ∣ T, T \to c T ∣ ϵ$ …
Context-Free Grammars, Pushdown Automata and CFLs · Regular Expressions, Finite Automata and Regular Languages
Theory of ComputationMCQ2 marksEasy (estimate)
Q.38 (CS Q.38)
Consider the following languages over the alphabet $Σ = {a, b, c}$ . Let $L_{1} = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$ and $L_{2} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$ . Which of the...
Context-Free Grammars, Pushdown Automata and CFLs
Theory of ComputationMCQ2 marksMedium (estimate)
Q.39 (CS Q.39)
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 there exists a T...
Turing Machines and Chomsky Hierarchy
Operating SystemsMCQ2 marksEasy (estimate)
Q.40 (CS Q.40)
Recall that Belady's anomaly is that the page-fault rate may increase as the number of allocated frames increases. Now, consider the following statements: S1: Random page replac...
Memory Management and Virtual Memory
DatabasesMCQ2 marksHard (estimate)
Q.41 (CS Q.41)
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 NULL in the relation EMP....
Relational Algebra and Tuple Relational Calculus
DatabasesMCQ2 marksMedium (estimate)
Q.42 (CS Q.42)
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 transactio...
Transactions, Serializability and Concurrency Control
Compiler DesignNAT2 marksEasy (estimate)
Q.43 (CS Q.43)
Consider the following grammar: stmt -> if expr then expr else expr; stmt | 0 expr -> term relop term | term term -> id | number id -> a | b | c number -> [0-9] where…
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Computer NetworksNAT2 marksEasy (estimate)
Q.44 (CS Q.44)
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, then the private key o...
Application Layer: DNS, HTTP, SMTP, FTP
Computer NetworksNAT2 marksMedium (estimate)
Q.45 (CS Q.45)
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 sender to rece...
Data Link Layer: Framing, Error Detection and Sliding Window
DatabasesNAT2 marksMedium (estimate)
Q.46 (CS Q.46)
Consider a database that has the relation schema $CR (StudentName, CourseName)$ . An instance of the schema CR is as given below. StudentName CourseName SA CA...
Relational Algebra and Tuple Relational Calculus
Engineering MathematicsNAT2 marksEasy (estimate)
Q.47 (CS Q.47)
The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______.
Combinatorics, Counting, Recurrence Relations and Generating Functions
AlgorithmsNAT2 marksMedium (estimate)
Q.48 (CS Q.48)
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 $A [i]$ is 1 by probing t...
Searching and Sorting Algorithms
Computer Organization and ArchitectureNAT2 marksEasy (estimate)
Q.49 (CS Q.49)
Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PC-relative addressing mode with Offset specified i...
Machine Instructions and Addressing Modes
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.50 (CS Q.50)
Instruction execution in a processor is divided into 5 stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Execute (EX), and Write Back (WB). These stag...
Instruction Pipelining and Hazards
Computer Organization and ArchitectureNAT2 marksHard (estimate)
Q.51 (CS Q.51)
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 occur due to contention of...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Compiler DesignNAT2 marksMedium (estimate)
Q.52 (CS Q.52)
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 register spill) algorithm...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Programming in CNAT2 marksEasy (estimate)
Q.53 (CS Q.53)
Consider the following C program. #include <stdio.h> #include <string.h> void printlength(char *s, char *t) { unsigned int c = 0; int len = ((strlen(s) - strlen(t)) > c) ? strle...
Data Types, Operators and Control Flow
Computer Organization and ArchitectureNAT2 marksEasy (estimate)
Q.54 (CS Q.54)
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 the TAG field is 10 bits....
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Programming in CNAT2 marksMedium (estimate)
Q.55 (CS Q.55)
The output of executing the following C program is ______. #include <stdio.h> int total(int v) { static int count = 0; while (v) { count += v & 1; v >>= 1; } return count; } voi...
Functions, Recursion, Scope and Storage Classes · Data Types, Operators and Control Flow

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.56 (GA Q.56)
After Rajendra Chola returned from his voyage to Indonesia, he __________ to visit the temple in Thanjavur.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.57 (GA Q.57)
Research in the workplace reveals that people work for many reasons __________
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.58 (GA Q.58)
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. Which of the following pairs...
Analytical and Logical Reasoning
General AptitudeMCQ1 markEasy (estimate)
Q.59 (GA Q.59)
Find the smallest number $y$ such that $y \times 162$ is a perfect cube.
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.60 (GA Q.60)
The probability that a $k$ -digit number does NOT contain the digits 0, 5, or 9 is
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.61 (GA Q.61)
"The hold of the nationalist imagination on our colonial past is such that anything inadequately or improperly nationalist is just not history." Which of the following statement...
Reading Comprehension and Verbal Deduction
General AptitudeMCQ2 marksHard (estimate)
Q.62 (GA Q.62)
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 has a left-handed person to h...
Analytical and Logical Reasoning
General AptitudeMCQ2 marksEasy (estimate)
Q.63 (GA Q.63)
The expression $\frac{( x + y ) - ∣ x - y ∣}{2}$ is equal to
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.64 (GA Q.64)
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 colour red and Shweta disli...
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.65 (GA Q.65)
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 lines are shown at 25 m interva...
Data Interpretation and Graphs · Spatial Aptitude