Previous year paper
GATE CS 2013
GATE 2013 Computer Science and Information Technology (CS)
Computer Science and Information Technology
55 questions, 85 marks
Q.1 (CS Q.1)
A binary operation on a set of integers is defined as . Which one of the following statements is TRUE about ?
Monoids and Groups
Q.2 (CS Q.2)
Suppose is the number of cars per minute passing through a certain road junction between 5 PM and 6 PM, and has a Poisson distribution with mean 3. What is the probabili...
Probability and Statistics
Q.3 (CS Q.3)
Which one of the following does NOT equal ?
Linear Algebra
Q.4 (CS Q.4)
The smallest integer that can be represented by an 8-bit number in 2’s complement form is
Number Representations and Computer Arithmetic
Q.5 (CS Q.5)
In the following truth table, if and only if the input is valid. What function does the truth table represent? D0 D1 D2 D3 X0 X1 V 0 0 0 0 x x 0 1 0 0 0 0 0 1 x 1 0 0 0...
Combinational Circuits
Q.6 (CS Q.6)
Which one of the following is the tightest upper bound that represents the number of swaps required to sort numbers using selection sort?
Searching and Sorting Algorithms
Q.7 (CS Q.7)
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of nodes?
Binary Trees, Binary Search Trees and Balanced Trees
Q.8 (CS Q.8)
Consider the languages and . Which one of the following represents ?
Regular Expressions, Finite Automata and Regular Languages
Q.9 (CS Q.9)
What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production (i.e., of type and…
Parsing and Syntax Analysis (LL and LR)
Q.10 (CS Q.10)
A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates...
CPU Scheduling
Q.11 (CS Q.11)
Match the problem domains in GROUP I with the solution technologies in GROUP II. GROUP I: (P) Service oriented computing (Q) Heterogeneous communicating systems (R) Information...
Functions, Recursion, Scope and Storage Classes
Q.12 (CS Q.12)
The transport layer protocols used for real time multimedia, file transfer, DNS and email, respectively are
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Q.13 (CS Q.13)
Using public key cryptography, X adds a digital signature to message , encrypts , and sends it to Y, where it is decrypted. Which one of t...
Application Layer: DNS, HTTP, SMTP, FTP
Q.14 (CS Q.14)
Assume that source S and destination D are connected through two intermediate routers labeled R. Determine how many times each packet has to visit the network layer and the data...
OSI/TCP-IP Layering, Physical Layer and Switching
Q.15 (CS Q.15)
An index is clustered, if
File Organization, B-Trees and B+ Trees Indexing
Q.16 (CS Q.16)
Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on...
Process Synchronization and Concurrency
Q.17 (CS Q.17)
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable la...
Turing Machines and Chomsky Hierarchy
Q.18 (CS Q.18)
Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether ther...
Turing Machines and Chomsky Hierarchy
Q.19 (CS Q.19)
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of vertices?
Single-Source and All-Pairs Shortest Paths
Q.20 (CS Q.20)
In a -way set associative cache, the cache is divided into sets, each of which consists of lines. The lines of a set are placed in sequence one after another. The lin...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Q.21 (CS Q.21)
Which one of the following expressions does NOT represent exclusive NOR of and ?
Boolean Algebra and Logic Minimization
Q.22 (CS Q.22)
Which one of the following functions is continuous at ?
Calculus
Q.23 (CS Q.23)
Function is known at the following points…
Calculus
Q.24 (CS Q.24)
Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is . What is the expected number of unordered cycles...
Probability and Statistics
Q.25 (CS Q.25)
Which of the following statements is/are TRUE for undirected graphs? P: Number of odd degree vertices is even. Q: Sum of degrees of all vertices is even.
Graph Theory
Q.26 (CS Q.26)
The line graph of a simple graph is defined as follows: - There is exactly one vertex in for each edge in . - For any two edges and in…
Graph Theory
Q.27 (CS Q.27)
What is the logical translation of the following statement? "None of my friends are perfect."
Propositional and First-Order Logic
Q.28 (CS Q.28)
Consider the following sequence of micro-operations. …
I/O Interface, Interrupts and DMA
Q.29 (CS Q.29)
Consider a hard disk with 16 recording surfaces (0-15) having 16384 cylinders (0-16383) and each cylinder contains 64 sectors (0-63). Data storage capacity in each sector is 512...
File Systems, I/O and Disk Scheduling
Q.30 (CS Q.30)
The number of elements that can be sorted in time using heap sort is
Searching and Sorting Algorithms
Q.31 (CS Q.31)
Consider the following function: int unknown(int n){ int i, j, k=0; for (i=n/2; i<=n; i++) for (j=2; j<=n; j=j*2) k = k + n/2; return (k); } The return value of the fun...
Data Types, Operators and Control Flow
Q.32 (CS Q.32)
Consider the following languages. Which one of the following statements is FALSE?
Context-Free Grammars, Pushdown Automata and CFLs
Q.33 (CS Q.33)
Consider the DFA A given below. Deterministic finite automaton with three states and transitions on symbols 0 and 1 Which of the following are FALSE? 1. Complement of is...
Regular Expressions, Finite Automata and Regular Languages
Q.34 (CS Q.34)
A shared variable , initialized to zero, is operated on by four concurrent processes as follows. Each of the processes and reads from memory, increme...
Process Synchronization and Concurrency
Q.35 (CS Q.35)
Consider the following relational schema. …
Relational Algebra and Tuple Relational Calculus
Q.36 (CS Q.36)
Determine the maximum length of the cable (in km) for transmitting data at a rate of 500 Mbps in an Ethernet LAN with frames of size 10,000 bits. Assume the signal speed in the...
Medium Access Control (ALOHA, CSMA/CD) and Ethernet/Switching
Q.37 (CS Q.37)
In an IPv4 datagram, the M bit is 0, the value of HLEN is 10, the value of total length is 400 and the fragment offset value is 300. The position of the datagram, the sequence n...
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Q.38 (CS Q.38)
The following figure represents access graphs of two modules M1 and M2. The filled circles represent methods and the unfilled circles represent attributes. If method m is moved...
Functions, Recursion, Scope and Storage Classes
Q.39 (CS Q.39)
A certain computation generates two arrays and such that for and for . Suppose this computation is decomposed int...
Process Synchronization and Concurrency
Q.40 (CS Q.40)
Consider the following two sets of LR(1) items of an LR(1) grammar.…
Parsing and Syntax Analysis (LL and LR)
Q.41 (CS Q.41)
Which of the following is/are undecidable? 1. is a CFG. Is ? 2. is a CFG. Is ? 3. is a Turing machine. Is regular? 4. is a D...
Decidability, Reducibility and Undecidability
Q.42 (CS Q.42)
What is the return value of
f(p, p), if the value ofpis initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second paramete...Functions, Recursion, Scope and Storage Classes
Q.43 (CS Q.43)
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
Binary Trees, Binary Search Trees and Balanced Trees
Q.44 (CS Q.44)
Consider the following operation along with Enqueue and Dequeue operations on queues, where is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and...
Stacks and Queues
Q.45 (CS Q.45)
Consider an instruction pipeline with five stages without any branch prediction: Fetch Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction (EI) an...
Instruction Pipelining and Hazards
Q.46 (CS Q.46)
A RAM chip has a capacity of 1024 words of 8 bits each (). The number of decoders with enable line needed to construct a ...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Q.47 (CS Q.47)
Which one of the following is NOT logically equivalent to ?
Propositional and First-Order Logic
Q.48 (CS Q.48)
Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Q.49 (CS Q.49)
What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any op...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Q.50 (CS Q.50)
The tester now tests the program on all input strings of length five consisting of characters 'a', 'b', 'c', 'd' and 'e' with duplicates allowed. If the tester carries out this...
Data Types, Operators and Control Flow
Q.51 (CS Q.51)
If array A is made to hold the string "abcde", which of the above four test cases will be successful in exposing the flaw in this procedure?
Data Types, Operators and Control Flow
Q.52 (CS Q.52)
What is the size of a page in KB in this computer?
Memory Management and Virtual Memory
Q.53 (CS Q.53)
What is the minimum number of page colours needed to guarantee that no two synonyms map to different sets in the processor cache of this computer?
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Q.54 (CS Q.54)
How many candidate keys does the relation R have?
Functional Dependencies and Normalization
Q.55 (CS Q.55)
The relation R is
Functional Dependencies and Normalization
General Aptitude
10 questions, 15 marks
Q.56 (GA Q.56)
Which one of the following options is the closest in meaning to the word given below? Nadir
Verbal Ability and Grammar
Q.57 (GA Q.57)
Complete the sentence: Universalism is to particularism as diffuseness is to _______________.
Verbal Ability and Grammar
Q.58 (GA Q.58)
What will be the maximum sum of ?
Quantitative Aptitude
Q.59 (GA Q.59)
Were you a bird, you ___________________ in the sky.
Verbal Ability and Grammar
Q.60 (GA Q.60)
Choose the grammatically INCORRECT sentence:
Verbal Ability and Grammar
Q.61 (GA Q.61)
Find the sum of the expression
Quantitative Aptitude
Q.62 (GA Q.62)
Out of all the 2-digit integers between 1 and 100, a 2-digit number has to be selected at random. What is the probability that the selected number is not divisible by 7?
Quantitative Aptitude
Q.63 (GA Q.63)
After several defeats in wars, Robert Bruce went in exile and wanted to commit suicide. Just before committing suicide, he came across a spider attempting tirelessly to have its...
Reading Comprehension and Verbal Deduction
Q.64 (GA Q.64)
A tourist covers half of his journey by train at 60 km/h, half of the remainder by bus at 30 km/h and the rest by cycle at 10 km/h. The average speed of the tourist in km/h duri...
Quantitative Aptitude
Q.65 (GA Q.65)
The current erection cost of a structure is Rs. 13,200. If the labour wages per day increase by 1/5 of the current wages and the working hours decrease by 1/24 of the current pe...
Quantitative Aptitude