GATE CS 2011 question paper: all 65 questions with answers and solutions

Computer Science and Information Technology

55 questions, 85 marks

Compiler DesignMCQ1 markEasy (estimate)
Q.1 (CS Q.1)
In a compiler, keywords of a language are recognized during
Lexical Analysis
Computer NetworksMCQ1 markEasy (estimate)
Q.2 (CS Q.2)
A layer-4 firewall (a device that can look at all protocol headers up to the transport layer) CANNOT
Application Layer: DNS, HTTP, SMTP, FTP
Engineering MathematicsMCQ1 markEasy (estimate)
Q.3 (CS Q.3)
If two fair coins are flipped and at least one of the outcomes is known to be a head, what is the probability that both outcomes are heads?
Probability and Statistics
Computer NetworksMCQ1 markEasy (estimate)
Q.4 (CS Q.4)
Consider different activities related to email. $m_{1}$ : Send an email from a mail client to a mail server $m_{2}$ : Download an email from mailbox server to a mail client $m_{3}$ : Che...
Application Layer: DNS, HTTP, SMTP, FTP
AlgorithmsMCQ1 markMedium (estimate)Not in current syllabus
Q.5 (CS Q.5)
A company needs to develop a strategy for software product development for which it has a choice of two programming languages L1 and L2. The number of lines of code (LOC) develo...
Asymptotic Analysis and Time/Space Complexity
Operating SystemsMCQ1 markEasy (estimate)
Q.6 (CS Q.6)
Let the time taken to switch between user and kernel modes of execution be $t_{1}$ while the time taken to switch between two processes be $t_{2}$ . Which of the following is TRUE?
Processes, Threads and System Calls
AlgorithmsMCQ1 markMedium (estimate)
Q.7 (CS Q.7)
A company needs to develop digital signal processing software for one of its newest inventions. The software is expected to have 40000 lines of code. The company needs to determ...
Asymptotic Analysis and Time/Space Complexity
Theory of ComputationMCQ1 markEasy (estimate)
Q.8 (CS Q.8)
Which of the following pairs have DIFFERENT expressive power?
Context-Free Grammars, Pushdown Automata and CFLs
Computer NetworksMCQ1 markEasy (estimate)Not in current syllabus
Q.9 (CS Q.9)
HTML (HyperText Markup Language) has language elements which permit certain actions other than describing the structure of the web document. Which one of the following actions i...
Application Layer: DNS, HTTP, SMTP, FTP
Programming in CMCQ1 markEasy (estimate)Not in current syllabus
Q.10 (CS Q.10)
Which one of the following is NOT desired in a good Software Requirement Specifications (SRS) document?
Data Types, Operators and Control Flow
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.11 (CS Q.11)
A computer handles several interrupt sources of which the following are relevant for this question. - Interrupt from CPU temperature sensor (raises interrupt if CPU temperature...
I/O Interface, Interrupts and DMA
DatabasesMCQ1 markEasy (estimate)
Q.12 (CS Q.12)
Consider a relational table with a single record for each registered student with the following attributes. 1. Registration_Num: Unique registration number of each registered st...
ER Model and Relational Schema Design
Digital LogicMCQ1 markMedium (estimate)
Q.13 (CS Q.13)
Which one of the following circuits is NOT equivalent to a 2-input XNOR (exclusive NOR) gate?
Combinational Circuits
Digital LogicMCQ1 markEasy (estimate)
Q.14 (CS Q.14)
The simplified SOP (Sum of Product) form of the Boolean expression $(P + Q + R) \cdot (P + Q + R) \cdot (P + Q + R)$ is
Boolean Algebra and Logic Minimization
Digital LogicMCQ1 markEasy (estimate)
Q.15 (CS Q.15)
The minimum number of D flip-flops needed to design a mod-258 counter is
Sequential Circuits, Counters and Registers
Operating SystemsMCQ1 markEasy (estimate)
Q.16 (CS Q.16)
A thread is usually defined as a "light weight process" because an operating system (OS) maintains smaller data structures for a thread than for a process. In relation to this,...
CPU Scheduling
Engineering MathematicsMCQ1 markEasy (estimate)
Q.17 (CS Q.17)
$K_{4}$ and $Q_{3}$ are graphs with the following structures. Graphs K4 (complete graph on 4 vertices) and Q3 (3-dimensional hypercube graph with 8 vertices) Which one of the follow...
Graph Theory
Engineering MathematicsMCQ1 markEasy (estimate)
Q.18 (CS Q.18)
If the difference between the expectation of the square of a random variable ( $E [X^{2}]$ ) and the square of the expectation of the random variable ( $(E [X])^{2}$ ) is denoted by $R$ ,...
Probability and Statistics
Compiler DesignMCQ1 markEasy (estimate)
Q.19 (CS Q.19)
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
Lexical Analysis
Operating SystemsMCQ1 markEasy (estimate)
Q.20 (CS Q.20)
Let the page fault service time be 10 ms in a computer with average memory access time being 20 ns. If one page fault is generated for every $1 0^{6}$ memory accesses, what is the...
Memory Management and Virtual Memory
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.21 (CS Q.21)
Consider a hypothetical processor with an instruction of type LW R1, 20(R2), which during execution reads a 32-bit word from memory and stores it in a 32-bit register R1. The...
Machine Instructions and Addressing Modes
Programming in CMCQ1 markEasy (estimate)
Q.22 (CS Q.22)
What does the following fragment of C program print? char c[] = "GATE2011"; char *p = c; printf("%s", p + p[3] - p[1]);
Pointers, Arrays and Strings
Data StructuresMCQ1 markEasy (estimate)
Q.23 (CS Q.23)
A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. Which of the following is a max-heap?
Binary Trees, Binary Search Trees and Balanced Trees
Theory of ComputationMCQ1 markEasy (estimate)
Q.24 (CS Q.24)
Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$ . (For example, let $P$ be the language represented by the regular expression $p^{*} q^{*}$ ...
Regular Expressions, Finite Automata and Regular Languages
AlgorithmsMCQ1 markEasy (estimate)
Q.25 (CS Q.25)
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A [0 : n - 1]$ is given below. Let $L_{i}$ denote the length of the longest mon...
Dynamic Programming
Theory of ComputationMCQ2 marksEasy (estimate)
Q.26 (CS Q.26)
Consider the languages $L_{1}$ , $L_{2}$ and $L_{3}$ as given below. $L_{1} = {0^{p} 1^{q} ∣ p, q \in N}$ $L_{2} = {0^{p} 1^{q} ∣ p, q \in N and p = q}$ …
Context-Free Grammars, Pushdown Automata and CFLs
Compiler DesignMCQ2 marksMedium (estimate)
Q.27 (CS Q.27)
Consider two binary operators ' $↑$ ' and ' $↓$ ' with the precedence of operator $↓$ being lower than that of operator $↑$ . Operator $↑$ is r...
Parsing and Syntax Analysis (LL and LR)
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.28 (CS Q.28)
On a non-pipelined sequential processor, a program segment, which is a part of the interrupt service routine, is given to transfer 500 bytes from an I/O device to memory. ...
I/O Interface, Interrupts and DMA
Data StructuresMCQ2 marksEasy (estimate)
Q.29 (CS Q.29)
We are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary...
Binary Trees, Binary Search Trees and Balanced Trees
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.30 (CS Q.30)
Which one of the following options is CORRECT given three positive integers $x$ , $y$ and $z$ , and a predicate…
Propositional and First-Order Logic
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.31 (CS Q.31)
Given $i = - 1$ , what will be the evaluation of the definite integral $\int_{0}^{π /2} \frac{c o s x + i s i n x}{c o s x - i s i n x} d x ?$
Calculus
DatabasesMCQ2 marksMedium (estimate)
Q.32 (CS Q.32)
Consider a database table $T$ containing two columns $X$ and $Y$ each of type integer. After the creation of the table, one record $(X = 1, Y = 1)$ is inserted in the table. Let…
SQL Queries and Integrity Constraints
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.33 (CS Q.33)
Consider a finite sequence of random values $X = [x_{1}, x_{2}, \dots, x_{n}]$ . Let $μ_{x}$ be the mean and $σ_{x}$ be the standard deviation of $X$ . Let another finite sequence…
Probability and Statistics
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.34 (CS Q.34)
A deck of 5 cards (each carrying a distinct number from 1 to 5) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the...
Probability and Statistics
Operating SystemsMCQ2 marksMedium (estimate)
Q.35 (CS Q.35)
Consider the following table of arrival time and burst time for three processes P0, P1 and P2. Process Arrival time Burst Time P0 0 ms 9 ms P1 1 ms 4 ms P2 2 ms 9 ms The pre-emp...
Process Synchronization and Concurrency
Compiler DesignMCQ2 marksMedium (estimate)
Q.36 (CS Q.36)
Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variabl...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
AlgorithmsMCQ2 marksMedium (estimate)
Q.37 (CS Q.37)
Which of the given options provides the increasing order of asymptotic complexity of functions $f_{1}, f_{2}, f_{3}$ and $f_{4}$ ?…
Asymptotic Analysis and Time/Space Complexity
AlgorithmsMCQ2 marksMedium (estimate)
Q.38 (CS Q.38)
Four matrices $M_{1}, M_{2}, M_{3}$ and $M_{4}$ of dimensions $p \times q$ , $q \times r$ , $r \times s$ and $s \times t$ respectively can be multiplied in several ways with different num...
Dynamic Programming
DatabasesMCQ2 marksEasy (estimate)
Q.39 (CS Q.39)
Consider a relational table $r$ with sufficient number of records, having attributes $A_{1}, A_{2}, \dots, A_{n}$ and let $1 \leq p \leq n$ . Two queries Q1 and Q2 are given below. Q1…
File Organization, B-Trees and B+ Trees Indexing
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.40 (CS Q.40)
Consider the matrix as given below. $100240373$ Which one of the following options provides the CORRECT values of the e...
Linear Algebra
Computer Organization and ArchitectureMCQ2 marksEasy (estimate)
Q.41 (CS Q.41)
Consider an instruction pipeline with four stages (S1, S2, S3 and S4) each with combinational circuit only. The pipeline registers are required between each stage and at the end...
Instruction Pipelining and Hazards
Theory of ComputationMCQ2 marksMedium (estimate)
Q.42 (CS Q.42)
Definition of a language $L$ with alphabet ${a}$ is given as following. $L = {a^{nk} ∣ k > 0, and n is a positive integer constant}$ What is the minimu...
Regular Expressions, Finite Automata and Regular Languages
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.43 (CS Q.43)
An 8KB direct-mapped write-back cache is organized as multiple blocks, each of size 32-bytes. The processor generates 32-bit addresses. The cache controller maintains the tag in...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Operating SystemsMCQ2 marksEasy (estimate)
Q.44 (CS Q.44)
An application loads 100 libraries at startup. Loading each library requires exactly one disk access. The seek time of the disk to a random location is given as 10 ms. Rotationa...
File Systems, I/O and Disk Scheduling
Theory of ComputationMCQ2 marksMedium (estimate)
Q.45 (CS Q.45)
A deterministic finite automaton (DFA) $D$ with alphabet $Σ = {a, b}$ is given below. Deterministic finite automaton D with start state p, state q, trap state r, and acce...
Regular Expressions, Finite Automata and Regular Languages
DatabasesMCQ2 marksEasy (estimate)
Q.46 (CS Q.46)
Database table by name Loan_Records is given below. Borrower Bank_Manager Loan_Amount Ramesh Sunderajan 10000.00 Suresh Ramgopal 5000.00 Mahesh Sunderajan 7000.00 What is the...
SQL Queries and Integrity Constraints
Programming in CMCQ2 marksMedium (estimate)Not in current syllabus
Q.47 (CS Q.47)
The following is the comment written for a C function. /* This function computes the roots of a quadratic equation a.x^2 + b.x + c = 0. The function stores two real roots i...
Data Types, Operators and Control Flow
Programming in CMCQ2 marksEasy (estimate)
Q.48 (CS Q.48)
What is the return value of the function foo when it is called as foo(345, 10)?
Functions, Recursion, Scope and Storage Classes
Programming in CMCQ2 marksEasy (estimate)
Q.49 (CS Q.49)
What is the return value of the function foo when it is called as foo(513, 2)?
Functions, Recursion, Scope and Storage Classes
Digital LogicMCQ2 marksMedium (estimate)
Q.50 (CS Q.50)
If at some instance prior to the occurrence of the clock edge, $P, Q$ and $R$ have a value 0, 1 and 0 respectively, what shall be the value of $P QR$ after the clock edge?
Sequential Circuits, Counters and Registers
Digital LogicMCQ2 marksMedium (estimate)
Q.51 (CS Q.51)
If all the flip-flops were reset to 0 at power on, what is the total number of distinct outputs (states) represented by $P QR$ generated by the counter?
Sequential Circuits, Counters and Registers
Computer NetworksMCQ2 marksMedium (estimate)
Q.52 (CS Q.52)
The cost of link N2-N3 reduces to 2 (in both directions). After the next round of updates, what will be the new distance vector at node, N3?
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF
Computer NetworksMCQ2 marksMedium (estimate)
Q.53 (CS Q.53)
After the update in the previous question, the link N1-N2 goes down. N2 will reflect this change immediately in its distance vector as cost, $\infty$ . After the NEXT ROUND of up...
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF
AlgorithmsMCQ2 marksMedium (estimate)
Q.54 (CS Q.54)
What will be the cost of the minimum spanning tree (MST) of such a graph with $n$ nodes?
Minimum Spanning Trees
AlgorithmsMCQ2 marksMedium (estimate)
Q.55 (CS Q.55)
The length of the path from $v_{5}$ to $v_{6}$ in the MST of previous question with $n = 10$ is
Minimum Spanning Trees

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.56 (GA Q.56)
Which of the following options is the closest in the meaning to the word below: Inexplicable
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.57 (GA Q.57)
If $lo g (P) = \frac{1}{2} lo g (Q) = \frac{1}{3} lo g (R)$ , then which of the following options is TRUE?
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.58 (GA Q.58)
Choose the most appropriate word(s) from the options given below to complete the following sentence. I contemplated _______ Singapore for my vacation but decided against it.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.59 (GA Q.59)
Choose the most appropriate word from the options given below to complete the following sentence. If you are trying to make a strong impression on your audience, you cannot do s...
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.60 (GA Q.60)
Choose the word from the options given below that is most nearly opposite in meaning to the given word: Amalgamate
Verbal Ability and Grammar
General AptitudeMCQ2 marksEasy (estimate)
Q.61 (GA Q.61)
Few school curricula include a unit on how to deal with bereavement and grief, and yet all students at some point in their lives suffer from losses through death and parting. Ba...
Reading Comprehension and Verbal Deduction
General AptitudeMCQ2 marksMedium (estimate)
Q.62 (GA Q.62)
P, Q, R and S are four types of dangerous microbes recently found in a human habitat. The area of each circle with its diameter printed in brackets represents the growth of a si...
Data Interpretation and Graphs
General AptitudeMCQ2 marksEasy (estimate)
Q.63 (GA Q.63)
The variable cost ( $V$ ) of manufacturing a product varies according to the equation $V = 4 q$ , where $q$ is the quantity produced. The fixed cost ( $F$ ) of production of same prod...
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.64 (GA Q.64)
A transporter receives the same number of orders each day. Currently, he has some pending orders (backlog) to be shipped. If he uses 7 trucks, then at the end of the 4th day he...
Quantitative Aptitude
General AptitudeMCQ2 marksEasy (estimate)
Q.65 (GA Q.65)
A container originally contains 10 litres of pure spirit. From this container 1 litre of spirit is replaced with 1 litre of water. Subsequently, 1 litre of the mixture is again...
Quantitative Aptitude