GATE CS 2012 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)
Consider the following logical inferences. $I_{1}$ : If it rains then the cricket match will not be played. The cricket match was played. Inference: There was no rain. $I_{2}$ : If it...
Propositional and First-Order Logic
DatabasesMCQ1 markEasy (estimate)
Q.2 (CS Q.2)
Which of the following is TRUE?
Functional Dependencies and Normalization
Programming in CMCQ1 markMedium (estimate)
Q.3 (CS Q.3)
What will be the output of the following C program segment? char inChar = 'A' ; switch ( inChar ) { case 'A' : printf ("Choice A\ n") ; case 'B' : case 'C' : printf ("Choic...
Data Types, Operators and Control Flow
AlgorithmsMCQ1 markEasy (estimate)
Q.4 (CS Q.4)
Assuming $P \neq = NP$ , which of the following is TRUE?
Asymptotic Analysis and Time/Space Complexity
Data StructuresMCQ1 markEasy (estimate)
Q.5 (CS Q.5)
The worst case running time to search for an element in a balanced binary search tree with $n 2^{n}$ elements is
Binary Trees, Binary Search Trees and Balanced Trees
Digital LogicMCQ1 markEasy (estimate)
Q.6 (CS Q.6)
The truth table $X 0011 Y 0101 f (X, Y) 0011$ represents the Boolean function
Boolean Algebra and Logic Minimization
Digital LogicMCQ1 markEasy (estimate)
Q.7 (CS Q.7)
The decimal value 0.5 in IEEE single precision floating point representation has
Number Representations and Computer Arithmetic
Operating SystemsMCQ1 markEasy (estimate)
Q.8 (CS Q.8)
A process executes the code fork(); fork(); fork(); The total number of child processes created is
Processes, Threads and System Calls
Engineering MathematicsMCQ1 markMedium (estimate)
Q.9 (CS Q.9)
Consider the function $f (x) = sin (x)$ in the interval $x \in [π /4, 7 π /4]$ . The number and location(s) of the local minima of this function are
Calculus
Computer NetworksMCQ1 markEasy (estimate)
Q.10 (CS Q.10)
The protocol data unit (PDU) for the application layer in the Internet stack is
OSI/TCP-IP Layering, Physical Layer and Switching
Engineering MathematicsMCQ1 markMedium (estimate)
Q.11 (CS Q.11)
Let $A$ be the $2 \times 2$ matrix with elements $a_{11} = a_{12} = a_{21} = + 1$ and $a_{22} = - 1$ . Then the eigenvalues of the matrix $A^{19}$ are
Linear Algebra
Theory of ComputationMCQ1 markEasy (estimate)
Q.12 (CS Q.12)
What is the complement of the language accepted by the NFA shown below? Assume $Σ = {a}$ and $ε$ is the empty string. Non-deterministic finite automaton with th...
Regular Expressions, Finite Automata and Regular Languages
Engineering MathematicsMCQ1 markEasy (estimate)
Q.13 (CS Q.13)
What is the correct translation of the following statement into mathematical logic? "Some real numbers are rational"
Propositional and First-Order Logic
DatabasesMCQ1 markEasy (estimate)
Q.14 (CS Q.14)
Given the basic ER and relational models, which of the following is INCORRECT?
Relational Algebra and Tuple Relational Calculus · ER Model and Relational Schema Design
DatabasesMCQ1 markMedium (estimate)
Q.15 (CS Q.15)
Which of the following statements are TRUE about an SQL query? $P$ : An SQL query can contain a HAVING clause even if it does not have a GROUP BY clause $Q$ : An SQL query can con...
SQL Queries and Integrity Constraints
AlgorithmsMCQ1 markEasy (estimate)
Q.16 (CS Q.16)
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with $n$ discs is
Divide and Conquer · Asymptotic Analysis and Time/Space Complexity
Engineering MathematicsMCQ1 markEasy (estimate)
Q.17 (CS Q.17)
Let $G$ be a simple undirected planar graph on 10 vertices with 15 edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is e...
Graph Theory
AlgorithmsMCQ1 markEasy (estimate)
Q.18 (CS Q.18)
Let $W (n)$ and $A (n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$ . Which of the following is ALWAYS TRUE?
Asymptotic Analysis and Time/Space Complexity
Digital LogicMCQ1 markEasy (estimate)
Q.19 (CS Q.19)
The amount of ROM needed to implement a 4 bit multiplier is
Combinational Circuits · Combinational Circuits
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.20 (CS Q.20)
Register renaming is done in pipelined processors
Instruction Pipelining and Hazards · Instruction Pipelining and Hazards
Engineering MathematicsMCQ1 markEasy (estimate)
Q.21 (CS Q.21)
Consider a random variable $X$ that takes values $+ 1$ and $- 1$ with probability $0.5$ each. The values of the cumulative distribution function $F (x)$ at $x = - 1$ and $+ 1$ are
Probability and Statistics
Computer NetworksMCQ1 markEasy (estimate)
Q.22 (CS Q.22)
Which of the following transport layer protocols is used to support electronic mail?
Application Layer: DNS, HTTP, SMTP, FTP · Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Computer NetworksMCQ1 markEasy (estimate)
Q.23 (CS Q.23)
In the IPv4 addressing format, the number of networks allowed under Class C addresses is
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Theory of ComputationMCQ1 markMedium (estimate)
Q.24 (CS Q.24)
Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If $L$ is a context-free language, then, is $L$ also context-free? 3...
Decidability, Reducibility and Undecidability · Regular Expressions, Finite Automata and Regular Languages
Theory of ComputationMCQ1 markEasy (estimate)
Q.25 (CS Q.25)
Given the language $L = {ab, aa, baa}$ , which of the following strings are in $L^{*}$ ? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
Regular Expressions, Finite Automata and Regular Languages · Regular Expressions, Finite Automata and Regular Languages
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.26 (CS Q.26)
Which of the following graphs is isomorphic to the given graph? Given graph with 8 vertices and candidate graphs for isomorphism in options A, B, C, and D Stem graph and options...
Graph Theory
DatabasesMCQ2 marksMedium (estimate)
Q.27 (CS Q.27)
Consider the following transactions with data items $P$ and $Q$ initialized to zero: $T_{1}$ : read ( $P$ ); read ( $Q$ ); if $P = 0$ then $Q := Q + 1$ ; write ( $Q$ ). $T_{2}$ : read ( $Q$ );...
Transactions, Serializability and Concurrency Control
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.28 (CS Q.28)
The bisection method is applied to compute a zero of the function $f (x) = x^{4} - x^{3} - x^{2} - 4$ in the interval $[1, 9]$ . The method converges to a solution after ----- iterations.
Calculus
AlgorithmsMCQ2 marksMedium (estimate)
Q.29 (CS Q.29)
Let $G$ be a weighted graph with edge weights greater than one and $G^{'}$ be the graph constructed by squaring the weights of edges in $G$ . Let $T$ and $T^{'}$ be the minimum spannin...
Greedy Algorithms · Graph Traversals, Topological Sort and Connectivity
Digital LogicMCQ2 marksMedium (estimate)
Q.30 (CS Q.30)
What is the minimal form of the Karnaugh map shown below? Assume that $X$ denotes a don't care term. Four-variable Karnaugh map for variables a, b, c, d with specified 1s and do...
Boolean Algebra and Logic Minimization · Boolean Algebra and Logic Minimization
Operating SystemsMCQ2 marksMedium (estimate)
Q.31 (CS Q.31)
Consider the 3 processes, $P_{1}$ , $P_{2}$ and $P_{3}$ shown in the table. | Process | Arrival time | Time Units Required | | :--- | :--- | :--- | | $P_{1}$ | 0 | 5 | | $P_{2}$ | 1 | 7 |...
CPU Scheduling
Operating SystemsMCQ2 marksMedium (estimate)
Q.32 (CS Q.32)
Fetch_And_Add(X, i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is use...
Process Synchronization and Concurrency
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.33 (CS Q.33)
Suppose a fair six-sided die is rolled once. If the value on the die is 1, 2, or 3, the die is rolled a second time. What is the probability that the sum total of values that tu...
Probability and Statistics
Computer NetworksMCQ2 marksMedium (estimate)
Q.34 (CS Q.34)
An Internet Service Provider (ISP) has the following chunk of CIDR-based IP addresses available with it: 245.248.128.0/20. The ISP wants to give half of this chunk of addresses...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT · IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Data StructuresMCQ2 marksEasy (estimate)
Q.35 (CS Q.35)
Suppose a circular queue of capacity ( $n - 1$ ) elements is implemented with an array of $n$ elements. Assume that the insertion and deletion operations are carried out using REA...
Stacks and Queues
Compiler DesignMCQ2 marksMedium (estimate)
Q.36 (CS Q.36)
Consider the program given below, in a block-structured pseudo-language with lexical scoping and nesting of procedures permitted. Program main; Var ... Procedure A1; V...
Runtime Environments and Parameter Passing
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.37 (CS Q.37)
How many onto (or surjective) functions are there from an $n$ -element ( $n \geq 2$ ) set to a 2-element set?
Combinatorics, Counting, Recurrence Relations and Generating Functions
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.38 (CS Q.38)
Let $G$ be a complete undirected graph on 6 vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length 4 in $G$ is equal to
Graph Theory · Combinatorics, Counting, Recurrence Relations and Generating Functions
AlgorithmsMCQ2 marksMedium (estimate)
Q.39 (CS Q.39)
A list of $n$ strings, each of length $n$ , is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
Searching and Sorting Algorithms · Asymptotic Analysis and Time/Space Complexity
AlgorithmsMCQ2 marksMedium (estimate)
Q.40 (CS Q.40)
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra's shortest path algorit...
Single-Source and All-Pairs Shortest Paths · Greedy Algorithms
Operating SystemsMCQ2 marksEasy (estimate)
Q.41 (CS Q.41)
A file system with 300 GByte disk uses a file descriptor with 8 direct block addresses, 1 indirect block address and 1 doubly indirect block address. The size of each disk block...
File Systems, I/O and Disk Scheduling
Operating SystemsMCQ2 marksMedium (estimate)
Q.42 (CS Q.42)
Consider the virtual page reference string $1, 2, 3, 2, 4, 1, 3, 2, 4, 1$ on a demand paged virtual memory system running on a computer system that has main memory size of 3 p...
Memory Management and Virtual Memory
DatabasesMCQ2 marksEasy (estimate)
Q.43 (CS Q.43)
Suppose $R_{1} (A, B)$ and $R_{2} (C, D)$ are two relation schemas. Let $r_{1}$ and $r_{2}$ be the corresponding relation instances. $B$ is a foreign key that refers to $C$ in $R_{2}$ . If d...
Relational Algebra and Tuple Relational Calculus · Relational Algebra and Tuple Relational Calculus
Computer NetworksMCQ2 marksMedium (estimate)
Q.44 (CS Q.44)
Consider a source computer ( $S$ ) transmitting a file of size $1 0^{6}$ bits to a destination computer ( $D$ ) over a network of two routers ( $R_{1}$ and $R_{2}$ ) and three links ( $L_{1}$ ,...
OSI/TCP-IP Layering, Physical Layer and Switching
Computer NetworksMCQ2 marksMedium (estimate)
Q.45 (CS Q.45)
Consider an instance of TCP's Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the start of the slow start phase is 2 MSS and the threshold at...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Theory of ComputationMCQ2 marksMedium (estimate)
Q.46 (CS Q.46)
Consider the set of strings on {0, 1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All st...
Regular Expressions, Finite Automata and Regular Languages · Regular Expressions, Finite Automata and Regular Languages
Data StructuresMCQ2 marksEasy (estimate)
Q.47 (CS Q.47)
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the he...
Binary Trees, Binary Search Trees and Balanced Trees · Binary Trees, Binary Search Trees and Balanced Trees
Programming in CMCQ2 marksMedium (estimate)
Q.48 (CS Q.48)
What output will be generated by the given code segment?
Functions, Recursion, Scope and Storage Classes · Functions, Recursion, Scope and Storage Classes
Programming in CMCQ2 marksMedium (estimate)
Q.49 (CS Q.49)
What output will be generated by the given code segment if: Line 1 is replaced by auto int a = 1; Line 2 is replaced by register int a = 2;
Functions, Recursion, Scope and Storage Classes · Functions, Recursion, Scope and Storage Classes
DatabasesMCQ2 marksMedium (estimate)
Q.50 (CS Q.50)
How many tuples does the result of the following relational algebra expression contain? Assume that the schema of $A \cup B$ is the same as that of $A$ .…
Relational Algebra and Tuple Relational Calculus
DatabasesMCQ2 marksMedium (estimate)
Q.51 (CS Q.51)
How many tuples does the result of the following SQL query contain? SELECT A.Id FROM A WHERE A.Age > ALL (SELECT B.Age FROM B WHERE B.Name = 'Arun')
SQL Queries and Integrity Constraints
Compiler DesignMCQ2 marksMedium (estimate)
Q.52 (CS Q.52)
The FIRST and FOLLOW sets for the non-terminals A and B are
Parsing and Syntax Analysis (LL and LR)
Compiler DesignMCQ2 marksMedium (estimate)
Q.53 (CS Q.53)
The appropriate entries for E1, E2, and E3 are
Parsing and Syntax Analysis (LL and LR)
Computer Organization and ArchitectureMCQ2 marksEasy (estimate)
Q.54 (CS Q.54)
The number of bits in the tag field of an address is
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.55 (CS Q.55)
The size of the cache tag directory is
Memory Hierarchy: Cache, Main Memory and Secondary Storage

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.56 (GA Q.56)
The cost function for a product in a firm is given by $5 q^{2}$ , where $q$ is the amount of production. The firm can sell the product at a market price of Rs 50 per unit. The numbe...
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.57 (GA Q.57)
Choose the most appropriate alternative from the options given below to complete the following sentence: Despite several -------- the mission succeeded in its attempt to resolve...
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.58 (GA Q.58)
Which one of the following options is the closest in meaning to the word given below? Mitigate
Verbal Ability and Grammar
General AptitudeMCQ1 markMedium (estimate)
Q.59 (GA Q.59)
Choose the grammatically INCORRECT sentence:
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.60 (GA Q.60)
Choose the most appropriate alternative from the options given below to complete the following sentence: Suresh's dog is the one -------- was hurt in the stampede.
Verbal Ability and Grammar
General AptitudeMCQ2 marksEasy (estimate)
Q.61 (GA Q.61)
Wanted Temporary, Part-time persons for the post of Field Interviewer to conduct personal interviews to collect and collate economic data. Requirements: High School-pass, must b...
Verbal Ability and Grammar
General AptitudeMCQ2 marksEasy (estimate)
Q.62 (GA Q.62)
A political party orders an arch for the entrance to the ground in which the annual convention is being held. The profile of the arch follows the equation $y = 2 x - 0.1 x^{2}$ wher...
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.63 (GA Q.63)
An automobile plant contracted to buy shock absorbers from two suppliers $X$ and $Y$ . $X$ supplies 60% and $Y$ supplies 40% of the shock absorbers. All shock absorbers are subje...
Quantitative Aptitude
General AptitudeMCQ2 marksEasy (estimate)
Q.64 (GA Q.64)
Which of the following assertions are CORRECT? $P$ : Adding 7 to each entry in a list adds 7 to the mean of the list $Q$ : Adding 7 to each entry in a list adds 7 to the standard...
Quantitative Aptitude
General AptitudeMCQ2 marksEasy (estimate)
Q.65 (GA Q.65)
Given the sequence of terms, AD CG FK JP, the next term is
Verbal Ability and Grammar