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

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.1 (GA Q.1)
We ____________ our friend's birthday and we ____________ how to make it up to him.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.2 (GA Q.2)
Choose the statement where underlined word is used correctly.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
Consider a function $f (x) = 1 - ∣ x ∣$ on $- 1 \leq x \leq 1$ . The value of $x$ at which the function attains a maximum, and the maximum value of the function are:
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.4 (GA Q.4)
A generic term that includes various items of clothing such as a skirt, a pair of trousers and a shirt is
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.5 (GA Q.5)
Based on the given statements, select the most appropriate option to solve the given question. What will be the total weight of 10 poles each of same weight? Statements: I. One...
Analytical and Logical Reasoning
General AptitudeMCQ2 marksEasy (estimate)
Q.6 (GA Q.6)
If the list of letters, $P, R, S, T, U$ is an arithmetic sequence, which of the following are also in arithmetic sequence? I. $2 P, 2 R, 2 S, 2 T, 2 U$ II.…
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.7 (GA Q.7)
Four branches of a company are located at $M, N, O,$ and $P$ . $M$ is north of $N$ at a distance of 4 km; $P$ is south of $O$ at a distance of 2 km; $N$ is southeast of $O$ by 1...
Spatial Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.8 (GA Q.8)
In a triangle $P QR$ , $P S$ is the angle bisector of $∠ QP R$ and $∠ QP S = 6 0^{\circ}$ . What is the length of $P S$ ? Triangle PQR with angle bisector PS and side lengths p,...
Quantitative Aptitude
General AptitudeNAT2 marksMedium (estimate)
Q.9 (GA Q.9)
If $p, q, r, s$ are distinct integers such that: $f (p, q, r, s) = max (p, q, r, s)$ $g (p, q, r, s) = min (p, q, r, s)$ …
Analytical and Logical Reasoning
General AptitudeMCQ2 marksEasy (estimate)
Q.10 (GA Q.10)
Out of the following four sentences, select the most suitable sentence with respect to grammar and usage:
Verbal Ability and Grammar

Computer Science and Information Technology

55 questions, 85 marks

DatabasesMCQ1 markEasy (estimate)
Q.11 (CS Q.1)
Consider the following transaction involving two bank accounts $x$ and $y$ .…
Transactions, Serializability and Concurrency Control
AlgorithmsMCQ1 markMedium (estimate)
Q.12 (CS Q.2)
Consider two decision problems $Q_{1}, Q_{2}$ such that $Q_{1}$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_{2}$ . Then which one of the following is c...
Asymptotic Analysis and Time/Space Complexity
Engineering MathematicsMCQ1 markEasy (estimate)
Q.13 (CS Q.3)
Consider the following two statements. $S_{1}$ : If a candidate is known to be corrupt, then he will not be elected. $S_{2}$ : If a candidate is kind, he will be elected. Which one of...
Propositional and First-Order Logic
Programming in CMCQ1 markEasy (estimate)Not in current syllabus
Q.14 (CS Q.4)
A software requirements specification (SRS) document should avoid discussing which one of the following?
Functions, Recursion, Scope and Storage Classes
Engineering MathematicsNAT1 markEasy (estimate)
Q.15 (CS Q.5)
The larger of the two eigenvalues of the matrix $[4251]$ is _____.
Linear Algebra
DatabasesNAT1 markMedium (estimate)
Q.16 (CS Q.6)
With reference to the B+ tree index of order 1 shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following query: "...
File Organization, B-Trees and B+ Trees Indexing
Digital LogicNAT1 markEasy (estimate)
Q.17 (CS Q.7)
The minimum number of JK flip-flops required to construct a synchronous counter with the count sequence $(0, 0, 1, 1, 2, 2, 3, 3, 0, 0, \dots)$ is _____.
Sequential Circuits, Counters and Registers
Computer NetworksNAT1 markMedium (estimate)
Q.18 (CS Q.8)
A link has a transmission speed of $1 0^{6}$ bits/sec. It uses data packets of size 1000 bytes each. Assume that the acknowledgment has negligible transmission delay, and that its...
Data Link Layer: Framing, Error Detection and Sliding Window
Engineering MathematicsNAT1 markEasy (estimate)
Q.19 (CS Q.9)
The number of divisors of 2100 is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
Data StructuresNAT1 markEasy (estimate)
Q.20 (CS Q.10)
A binary tree $T$ has 20 leaves. The number of nodes in $T$ having two children is _____.
Binary Trees, Binary Search Trees and Balanced Trees
Programming in CNAT1 markMedium (estimate)
Q.21 (CS Q.11)
Consider the following C function. int fun(int n){ int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun(n-k); return x; } The return value of fun(5) is _____.
Functions, Recursion, Scope and Storage Classes
Engineering MathematicsMCQ1 markEasy (estimate)Not in current syllabus
Q.22 (CS Q.12)
Consider the basic COCOMO model where $E$ is the effort applied in person-months, $D$ is the development time in chronological months, KLOC is the estimated number of delivered...
Combinatorics, Counting, Recurrence Relations and Generating Functions
Computer NetworksMCQ1 markEasy (estimate)
Q.23 (CS Q.13)
Which one of the following statements is NOT correct about HTTP cookies?
Application Layer: DNS, HTTP, SMTP, FTP
Compiler DesignMCQ1 markMedium (estimate)
Q.24 (CS Q.14)
In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Programming in CMCQ1 markEasy (estimate)
Q.25 (CS Q.15)
Consider the following function written in the C programming language. void foo(char *a){ if ( *a && *a != ' ' ){ foo(a+1); putchar(*a); } } The output of the above function on...
Pointers, Arrays and Strings
Engineering MathematicsMCQ1 markEasy (estimate)
Q.26 (CS Q.16)
Let $R$ be the relation on the set of positive integers such that $a R b$ if and only if $a$ and $b$ are distinct and have a common divisor other than 1. Which one of the followin...
Sets, Relations, Functions, Partial Orders and Lattices
Data StructuresMCQ1 markMedium (estimate)
Q.27 (CS Q.17)
Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is
Binary Heaps and Priority Queues
Engineering MathematicsNAT1 markEasy (estimate)
Q.28 (CS Q.18)
The cardinality of the power set of ${0, 1, 2, \dots, 10}$ is _____.
Sets, Relations, Functions, Partial Orders and Lattices
Compiler DesignMCQ1 markEasy (estimate)
Q.29 (CS Q.19)
Match the following compiler phases / tasks with their underlying algorithmic techniques: List-I P. Lexical analysis Q. Parsing R. Register allocation S. Expression evaluati...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Computer NetworksMCQ1 markEasy (estimate)
Q.30 (CS Q.20)
Identify the correct order in which a server process must invoke the function calls accept, bind, listen, and recv according to UNIX socket API
Application Layer: DNS, HTTP, SMTP, FTP
Theory of ComputationMCQ1 markMedium (estimate)
Q.31 (CS Q.21)
Consider the following statements: I. The complement of every Turing decidable language is Turing decidable. II. There exists some language which is in NP but is not Turing deci...
Decidability, Reducibility and Undecidability
AlgorithmsMCQ1 markEasy (estimate)
Q.32 (CS Q.22)
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
Searching and Sorting Algorithms
Operating SystemsMCQ1 markMedium (estimate)
Q.33 (CS Q.23)
A system has 6 identical resources and $N$ processes competing for them. Each process can request at most 2 resources. Which one of the following values of $N$ could lead to a d...
Deadlock Prevention, Avoidance and Detection
Computer Organization and ArchitectureNAT1 markEasy (estimate)
Q.34 (CS Q.24)
Assume that for a certain processor, a read request takes 50 nanoseconds on a cache miss and 5 nanoseconds on a cache hit. Suppose while running a program, it was observed that...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Operating SystemsNAT1 markMedium (estimate)
Q.35 (CS Q.25)
A computer system implements a 40-bit virtual address, page size of 8 kilobytes, and a 128-entry translation look-aside buffer (TLB) organized into 32 sets each having four ways...
Memory Management and Virtual Memory
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.36 (CS Q.26)
Let $f (x) = x^{- (1/3)}$ and $A$ denote the area of the region bounded by $f (x)$ and the X-axis, when $x$ varies from $- 1$ to 1. Which of the following statements is/are TRUE? I)...
Calculus
Engineering MathematicsNAT2 marksEasy (estimate)
Q.37 (CS Q.27)
Perform the following operations on the matrix $371349245105195$ : (i) Add the third row to the second row. (ii) Subtract...
Linear Algebra
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.38 (CS Q.28)
A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on $n$ vertices, $n$ is
Graph Theory
Compiler DesignMCQ2 marksMedium (estimate)
Q.39 (CS Q.29)
Consider the intermediate code given below. (1) i = 1 (2) j = 1 (3) t1 = 5 * i (4) t2 = t1 + j (5) t3 = 4 * t2 (6) t4 = t3 (7) a[t4] = -1 (8) j = j + 1 (9) if j<=5 goto (3) (10)...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Operating SystemsMCQ2 marksEasy (estimate)
Q.40 (CS Q.30)
Consider six memory partitions of sizes 200 KB, 400 KB, 600 KB, 500 KB, 300 KB and 250 KB, where KB refers to kilobyte. These partitions need to be allotted to four processes of...
Memory Management and Virtual Memory
Data StructuresNAT2 marksMedium (estimate)
Q.41 (CS Q.31)
A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$ , and hence there cannot be any entr...
Arrays and Linked Lists
DatabasesMCQ2 marksEasy (estimate)
Q.42 (CS Q.32)
Consider two relations $R_{1} (A, B)$ with the tuples $(1, 5), (3, 7)$ and $R_{2} (A, C)$ with $(1, 7), (4, 9)$ . Assume that $R (A, B, C)$ is the full natural outer join of $R_{1}$ and…
Relational Algebra and Tuple Relational Calculus
Data StructuresMCQ2 marksMedium (estimate)
Q.43 (CS Q.33)
Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for $i$ ranging from 0 to 2020?
Hash Tables and Collision Resolution
Computer NetworksMCQ2 marksMedium (estimate)
Q.44 (CS Q.34)
Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let $α$ be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP win...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Theory of ComputationMCQ2 marksEasy (estimate)
Q.45 (CS Q.35)
Consider the alphabet $Σ = {0, 1}$ , the null/empty string $λ$ and the sets of strings $X_{0}, X_{1}$ , and $X_{2}$ generated by the corresponding non-terminals of a regula...
Regular Expressions, Finite Automata and Regular Languages
AlgorithmsMCQ2 marksEasy (estimate)
Q.46 (CS Q.36)
Given below are some algorithms, and some algorithm design paradigms. List-I 1. Dijkstra's Shortest Path 2. Floyd-Warshall algorithm to compute all pairs shortest path 3. Bi...
Dynamic Programming
Digital LogicNAT2 marksMedium (estimate)
Q.47 (CS Q.37)
The number of min-terms after minimizing the following Boolean expression is _____. $[D^{'} + A B^{'} + A^{'} C + A C^{'} D + A^{'} C^{'} D]^{'}$
Boolean Algebra and Logic Minimization
Programming in CNAT2 marksMedium (estimate)
Q.48 (CS Q.38)
Consider the C program below. #include <stdio.h> int *A, stkTop; int stkFunc(int opcode, int val) { static int size=0, stkTop=0; switch (opcode) { case -1: size = val; break; ca...
Functions, Recursion, Scope and Storage Classes
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.49 (CS Q.39)
The secant method is used to find the root of an equation $f (x) = 0$ . It is started from two distinct estimates $x_{a}$ and $x_{b}$ for the root. It is an iterative procedure involv...
Calculus
Engineering MathematicsNAT2 marksMedium (estimate)
Q.50 (CS Q.40)
The number of onto functions (surjective functions) from set $X = {1, 2, 3, 4}$ to set $Y = {a, b, c}$ is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
Computer NetworksMCQ2 marksMedium (estimate)
Q.51 (CS Q.41)
Consider the following routing table at an IP router: Network No. Net Mask Next Hop 128.96.170.0 255.255.254.0 Interface 0 128.96.168.0 255.255.254.0 Interface 1 128.96.166.0 25...
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.52 (CS Q.42)
Consider a processor with byte-addressable memory. Assume that all registers, including Program Counter (PC) and Program Status Word (PSW), are of size 2 bytes. A stack in the m...
Machine Instructions and Addressing Modes
Programming in CMCQ2 marksEasy (estimate)
Q.53 (CS Q.43)
Which one of the following assertions concerning code inspection and code walkthrough is true?
Functions, Recursion, Scope and Storage Classes
Computer Organization and ArchitectureNAT2 marksHard (estimate)
Q.54 (CS Q.44)
Consider the sequence of machine instructions given below: MUL R5, R0, R1 DIV R6, R2, R3 ADD R7, R5, R6 SUB R8, R7, R4 In the above sequence, R0 to R8 are general purpose regist...
Instruction Pipelining and Hazards
AlgorithmsMCQ2 marksMedium (estimate)
Q.55 (CS Q.45)
Suppose you are provided with the following function declaration in the C programming language: int partition(int a[], int n); The function treats the first element of a[] a...
Searching and Sorting Algorithms
DatabasesMCQ2 marksMedium (estimate)
Q.56 (CS Q.46)
Consider a simple checkpointing protocol and the following set of operations in the log: (start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7);…
Transactions, Serializability and Concurrency Control
Operating SystemsNAT2 marksMedium (estimate)
Q.57 (CS Q.47)
A computer system implements 8 kilobyte pages and a 32-bit physical address space. Each page table entry contains a valid bit, a dirty bit, three permission bits, and the transl...
Memory Management and Virtual Memory
Digital LogicNAT2 marksMedium (estimate)
Q.58 (CS Q.48)
A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AN...
Combinational Circuits
Operating SystemsNAT2 marksMedium (estimate)
Q.59 (CS Q.49)
Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of $50 \times 1 0^{6}$ bytes/sec. If the average seek time of the disk is twice the...
File Systems, I/O and Disk Scheduling
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.60 (CS Q.50)
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
Graph Theory
Theory of ComputationMCQ2 marksMedium (estimate)
Q.61 (CS Q.51)
Which of the following languages is/are regular? $L_{1} = {w x w^{R} ∣ w, x \in {a, b}^{+} and ∣ w ∣, ∣ x ∣ > 0}$ , $w^{R}$ is the reverse of string $w$ …
Regular Expressions, Finite Automata and Regular Languages
Computer NetworksMCQ2 marksMedium (estimate)
Q.62 (CS Q.52)
Host A sends a UDP datagram containing 8880 bytes of user data to host B over an Ethernet LAN. Ethernet frames may carry data up to 1500 bytes (i.e. MTU = 1500 bytes). Size of U...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Theory of ComputationNAT2 marksEasy (estimate)
Q.63 (CS Q.53)
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0 + 1)^{*} (10)$ is _____.
Regular Expressions, Finite Automata and Regular Languages
Engineering MathematicsNAT2 marksEasy (estimate)
Q.64 (CS Q.54)
Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$ . Let $f$ be randomly c...
Probability and Statistics
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.65 (CS Q.55)
Which one of the following well formed formulae is a tautology?
Propositional and First-Order Logic