GATE CS 2014 Set 3 question paper: all 65 questions with answers and solutions

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.1 (GA Q.1)
While trying to collect an envelope from under the table, Mr. X fell down and was losing consciousness. Which one of the underlined parts of the sentence is NOT appropriate? I:...
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.2 (GA Q.2)
If she _____ how to calibrate the instrument, she _____ done the experiment.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
Choose the word that is opposite in meaning to the word "coherent".
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.4 (GA Q.4)
Which number does not belong in the series below? 2, 5, 10, 17, 26, 37, 50, 64
Analytical and Logical Reasoning
General AptitudeMCQ1 markMedium (estimate)
Q.5 (GA Q.5)
The table below has question-wise data on the performance of students in an examination. The marks for each question are also listed. There is no negative or partial marking in...
Data Interpretation and Graphs
General AptitudeMCQ2 marksEasy (estimate)
Q.6 (GA Q.6)
A dance programme is scheduled for 10.00 a.m. Some students are participating in the programme and they need to come an hour earlier than the start of the event. These students...
Reading Comprehension and Verbal Deduction
General AptitudeMCQ2 marksEasy (estimate)
Q.7 (GA Q.7)
By the beginning of the $2 0^{th}$ century, several hypotheses were being proposed, suggesting a paradigm shift in our understanding of the universe. However, the clinchin...
Reading Comprehension and Verbal Deduction
General AptitudeMCQ2 marksMedium (estimate)
Q.8 (GA Q.8)
The Gross Domestic Product (GDP) in Rupees grew at 7% during 2012-2013. For international comparison, the GDP is compared in US Dollars (USD) after conversion based on the marke...
Quantitative Aptitude
General AptitudeMCQ2 marksEasy (estimate)
Q.9 (GA Q.9)
The ratio of male to female students in a college for five years is plotted in the following line graph. If the number of female students in 2011 and 2012 is equal, what is the...
Data Interpretation and Graphs
General AptitudeMCQ2 marksEasy (estimate)
Q.10 (GA Q.10)
Consider the equation: $(7526)_{8} - (Y)_{8} = (4364)_{8}$ , where $(X)_{N}$ stands for $X$ to the base $N$ . Find $Y$ .
Quantitative Aptitude

Computer Science and Information Technology

55 questions, 85 marks

Engineering MathematicsMCQ1 markEasy (estimate)
Q.11 (CS Q.1)
Consider the following statements: P: Good mobile phones are not cheap Q: Cheap mobile phones are not good L: P implies Q M: Q implies P N: P is equivalent to Q Which one of the...
Propositional and First-Order Logic
Engineering MathematicsMCQ1 markMedium (estimate)
Q.12 (CS Q.2)
Let $X$ and $Y$ be finite sets and $f : X \to Y$ be a function. Which one of the following statements is TRUE?
Sets, Relations, Functions, Partial Orders and Lattices
Engineering MathematicsNAT1 markEasy (estimate)
Q.13 (CS Q.3)
Let $G$ be a group with 15 elements. Let $L$ be a subgroup of $G$ . It is known that $L \neq = G$ and that the size of $L$ is at least 4. The size of $L$ is _____.
Monoids and Groups
Engineering MathematicsMCQ1 markEasy (estimate)
Q.14 (CS Q.4)
Which one of the following statements is TRUE about every $n \times n$ matrix with only real eigenvalues?
Linear Algebra
Engineering MathematicsNAT1 markEasy (estimate)
Q.15 (CS Q.5)
If $V_{1}$ and $V_{2}$ are 4-dimensional subspaces of a 6-dimensional vector space $V$ , then the smallest possible dimension of $V_{1} \cap V_{2}$ is _____.
Linear Algebra
Engineering MathematicsNAT1 markMedium (estimate)
Q.16 (CS Q.6)
If $\int_{0}^{2 π} ∣ x sin x ∣ d x = k π$ , then the value of $k$ is equal to _____.
Calculus
Digital LogicMCQ1 markEasy (estimate)
Q.17 (CS Q.7)
Consider the following minterm expression for $F$ : $F (P, Q, R, S) = \sum m (0, 2, 5, 7, 8, 10, 13, 15)$ The minterms 2, 7, 8 and 13 are 'do not care' terms. The minimal sum-of-...
Boolean Algebra and Logic Minimization
Digital LogicMCQ1 markEasy (estimate)
Q.18 (CS Q.8)
Consider the following combinational function block involving four Boolean variables $x, y, a, b$ where $x, a, b$ are inputs and $y$ is the output. f (x, y, a, b) { if (x is 1)...
Combinational Circuits
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.19 (CS Q.9)
Consider the following processors (ns stands for nanoseconds). Assume that the pipeline registers have zero latency. P1: Four-stage pipeline with stage latencies 1 ns, 2 ns, 2 n...
Instruction Pipelining and Hazards
Programming in CMCQ1 markMedium (estimate)
Q.20 (CS Q.10)
Let $A$ be a square matrix of size $n \times n$ . Consider the following pseudocode. What is the expected output? C = 100; for i = 1 to n do for j = 1 to n do { Temp = A[i][j] +...
Pointers, Arrays and Strings
AlgorithmsNAT1 markMedium (estimate)
Q.21 (CS Q.11)
The minimum number of arithmetic operations required to evaluate the polynomial $P (X) = X^{5} + 4 X^{3} + 6 X + 5$ for a given value of $X$ , using only one temporary variable is _____.
Asymptotic Analysis and Time/Space Complexity
Data StructuresMCQ1 markMedium (estimate)
Q.22 (CS Q.12)
Consider the following rooted tree with the vertex labeled P as the root: Rooted tree with root P having left child Q and right child R; Q has child S; R has three children T, U...
Binary Trees, Binary Search Trees and Balanced Trees
AlgorithmsNAT1 markHard (estimate)
Q.23 (CS Q.13)
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that...
Graph Traversals, Topological Sort and Connectivity
AlgorithmsMCQ1 markEasy (estimate)
Q.24 (CS Q.14)
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst...
Searching and Sorting Algorithms
Theory of ComputationNAT1 markMedium (estimate)
Q.25 (CS Q.15)
The length of the shortest string NOT in the language (over $Σ = {a, b}$ ) of the following regular expression is _____. $a^{*} b^{*} (ba)^{*} a^{*}$
Regular Expressions, Finite Automata and Regular Languages
Theory of ComputationMCQ1 markEasy (estimate)
Q.26 (CS Q.16)
Let $Σ$ be a finite non-empty alphabet and let $2^{Σ^{*}}$ be the power set of $Σ^{*}$ . Which one of the following is TRUE?
Decidability, Reducibility and Undecidability
Compiler DesignMCQ1 markEasy (estimate)
Q.27 (CS Q.17)
One of the purposes of using intermediate code in compilers is to
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Compiler DesignMCQ1 markMedium (estimate)
Q.28 (CS Q.18)
Which of the following statements are CORRECT? 1) Static allocation of all data areas by a compiler makes it impossible to implement recursion. 2) Automatic garbage collection i...
Runtime Environments and Parameter Passing
Programming in CMCQ1 markEasy (estimate)Not in current syllabus
Q.29 (CS Q.19)
In the context of modular software design, which one of the following combinations is desirable?
Functions, Recursion, Scope and Storage Classes
Operating SystemsNAT1 markEasy (estimate)
Q.30 (CS Q.20)
A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initiall...
Memory Management and Virtual Memory
DatabasesMCQ1 markEasy (estimate)
Q.31 (CS Q.21)
What is the optimized version of the relation algebra expression $π_{A 1} (π_{A 2} (σ_{F 1} (σ_{F 2} (r))))$ , where $A 1, A 2$ are sets of attributes in $r$ with…
Relational Algebra and Tuple Relational Calculus
DatabasesMCQ1 markEasy (estimate)
Q.32 (CS Q.22)
A prime attribute of a relation scheme $R$ is an attribute that appears
Functional Dependencies and Normalization
Computer NetworksMCQ1 markEasy (estimate)
Q.33 (CS Q.23)
In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is
OSI/TCP-IP Layering, Physical Layer and Switching
Computer NetworksMCQ1 markEasy (estimate)
Q.34 (CS Q.24)
A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is
Data Link Layer: Framing, Error Detection and Sliding Window
Computer NetworksMCQ1 markMedium (estimate)
Q.35 (CS Q.25)
Host A (on TCP/IP v4 network A) sends an IP datagram D to host B (also on TCP/IP v4 network B). Assume that no error occurred during the transmission of D. When D reaches B, whi...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Computer NetworksNAT2 marksMedium (estimate)
Q.36 (CS Q.26)
An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address 131.23.151.76. The router's routing table has the following entries: Prefix | Outp...
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF
Computer NetworksNAT2 marksMedium (estimate)
Q.37 (CS Q.27)
Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that ea...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Computer NetworksMCQ2 marksMedium (estimate)
Q.38 (CS Q.28)
An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an IP header of length 20 bytes. The values of the relevant f...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
DatabasesMCQ2 marksMedium (estimate)
Q.39 (CS Q.29)
Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below. T1: r1(X); r1(Z); w1(X); w1(Z) T2: r2(Y); r2(Z); w2(Z) T3: r3(Y); r3(X); w3(Y) S1: r1(X); r3(Y)...
Transactions, Serializability and Concurrency Control
DatabasesMCQ2 marksMedium (estimate)
Q.40 (CS Q.30)
Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at l...
Relational Algebra and Tuple Relational Calculus
Operating SystemsNAT2 marksEasy (estimate)
Q.41 (CS Q.31)
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never aris...
Deadlock Prevention, Avoidance and Detection
Operating SystemsNAT2 marksMedium (estimate)
Q.42 (CS Q.32)
An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival t...
CPU Scheduling
Operating SystemsNAT2 marksEasy (estimate)
Q.43 (CS Q.33)
Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 millisec...
Memory Management and Virtual Memory
Compiler DesignMCQ2 marksMedium (estimate)
Q.44 (CS Q.34)
Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b a = e + b The minimum number of nodes and edges present in the DAG representation of th...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Theory of ComputationMCQ2 marksEasy (estimate)
Q.45 (CS Q.35)
Which one of the following problems is undecidable?
Decidability, Reducibility and Undecidability
Theory of ComputationMCQ2 marksMedium (estimate)
Q.46 (CS Q.36)
Consider the following languages over the alphabet $Σ = {0, 1, c}$ : $L_{1} = {0^{n} 1^{n} ∣ n \geq 0}$ $L_{2} = {w c w^{r} ∣ w \in {0, 1}^{*}}$ …
Context-Free Grammars, Pushdown Automata and CFLs
AlgorithmsNAT2 marksEasy (estimate)
Q.47 (CS Q.37)
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified...
Dynamic Programming
AlgorithmsMCQ2 marksEasy (estimate)
Q.48 (CS Q.38)
Consider the decision problem 2CNFSAT defined as follows: ${Φ ∣ Φ is a satisfiable propositional formula in CNF with at most two literals per clause}$ For e...
Asymptotic Analysis and Time/Space Complexity
Data StructuresNAT2 marksMedium (estimate)
Q.49 (CS Q.39)
Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and…
Binary Trees, Binary Search Trees and Balanced Trees
Data StructuresMCQ2 marksEasy (estimate)
Q.50 (CS Q.40)
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after...
Hash Tables and Collision Resolution
Data StructuresMCQ2 marksMedium (estimate)
Q.51 (CS Q.41)
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling repres...
Binary Trees, Binary Search Trees and Balanced Trees
AlgorithmsMCQ2 marksMedium (estimate)
Q.52 (CS Q.42)
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. int ProcessArray(int *listA, int x, int n) { int i, j...
Searching and Sorting Algorithms
Computer Organization and ArchitectureNAT2 marksHard (estimate)
Q.53 (CS Q.43)
An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and regi...
Instruction Pipelining and Hazards
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.54 (CS Q.44)
The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache, 2 nanoseconds for a write operation wit...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Digital LogicMCQ2 marksMedium (estimate)
Q.55 (CS Q.45)
Synchronous sequential circuit built using three JK flip-flops Q2, Q1, and Q0 with feedback logic Synchronous sequential circuit using JK flip-flops The above synchronous sequen...
Sequential Circuits, Counters and Registers
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.56 (CS Q.46)
With respect to the numerical evaluation of the definite integral, $K = \int_{a}^{b} x^{2} d x$ , where $a$ and $b$ are given, which of the following statements is/are TRUE? I) The v...
Calculus
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.57 (CS Q.47)
The value of the integral given below is $\int_{0}^{π} x^{2} cos x d x$
Calculus
Engineering MathematicsNAT2 marksEasy (estimate)
Q.58 (CS Q.48)
Let $S$ be a sample space and two mutually exclusive events $A$ and $B$ be such that $A \cup B = S$ . If $P (\cdot)$ denotes the probability of the event, the maximum value of…
Probability and Statistics
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.59 (CS Q.49)
Consider the set of all functions $f : {0, 1, \dots, 2014} \to {0, 1, \dots, 2014}$ such that $f (f (i)) = i$ , for all $0 \leq i \leq 2014$ . Consider the following statements: P....
Sets, Relations, Functions, Partial Orders and Lattices
Engineering MathematicsNAT2 marksMedium (estimate)
Q.60 (CS Q.50)
There are two elements $x, y$ in a group $(G, *)$ such that every element in the group can be written as a product of some number of $x$ 's and $y$ 's in some order. It is known t...
Monoids and Groups
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.61 (CS Q.51)
If $G$ is a forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?
Graph Theory
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.62 (CS Q.52)
Let $δ$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $δ \geq 3$ , which one of the following is TRUE?
Graph Theory
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.63 (CS Q.53)
The CORRECT formula for the sentence, "not all rainy days are cold" is
Propositional and First-Order Logic
DatabasesMCQ2 marksEasy (estimate)
Q.64 (CS Q.54)
Consider the following relational schema: employee(empId, empName, empDept) customer(custId, custName, salesRepId, rating) salesRepId is a foreign key referring to e...
SQL Queries and Integrity Constraints
Digital LogicMCQ2 marksEasy (estimate)
Q.65 (CS Q.55)
Let $\oplus$ denote the Exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean expression for $F$ over two variables $P$ and…
Boolean Algebra and Logic Minimization