GATE CS 2015 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)
If ROAD is written as URDG, then SWAN should be written as:
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.2 (GA Q.2)
The Tamil version of _____ John Abraham-starrer Madras Cafe _____ cleared by the Censor Board with no cuts last week, but the film's distributors _____ no takers among the exhib...
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
Extreme focus on syllabus and studying for tests has become such a dominant concern of Indian students that they close their minds to anything _____ to the requirements of the e...
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.4 (GA Q.4)
Select the pair that best expresses a relationship similar to that expressed in the pair: Children : Pediatrician
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.5 (GA Q.5)
A function $f (x)$ is linear and has a value of 29 at $x = - 2$ and 39 at $x = 3$ . Find its value at $x = 5$ .
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.6 (GA Q.6)
Alexander turned his attention towards India, since he had conquered Persia. Which one of the statements below is logically valid and can be inferred from the above sentence?
Verbal Ability and Grammar
General AptitudeMCQ2 marksMedium (estimate)
Q.7 (GA Q.7)
The head of a newly formed government desires to appoint five of the six selected members P, Q, R, S, T, and U to portfolios of Home, Power, Defense, Telecom, and Finance. U doe...
Analytical and Logical Reasoning
General AptitudeMCQ2 marksMedium (estimate)
Q.8 (GA Q.8)
Choose the most appropriate equation for the function drawn as a thick line, in the plot below. Plot of function with a ray along the positive y-axis and a ray through (2, -1) i...
Quantitative Aptitude
General AptitudeMCQ2 marksMedium (estimate)
Q.9 (GA Q.9)
Most experts feel that in spite of possessing all the technical skills required to be a batsman of the highest order, he is unlikely to be so due to lack of requisite temperamen...
Verbal Ability and Grammar
General AptitudeNAT2 marksMedium (estimate)
Q.10 (GA Q.10)
The exports and imports (in crores of Rs.) of a country from the year 2000 to 2007 are given in the following bar chart. In which year is the combined percentage increase in imp...
Data Interpretation and Graphs

Computer Science and Information Technology

55 questions, 85 marks

Operating SystemsMCQ1 markEasy (estimate)
Q.11 (CS Q.1)
The maximum number of processes that can be in Ready state for a computer system with $n$ CPUs is
Processes, Threads and System Calls · CPU Scheduling
Digital LogicMCQ1 markEasy (estimate)
Q.12 (CS Q.2)
Let $#$ be a binary operator defined as $X # Y = X^{'} + Y^{'}$ where $X$ and $Y$ are Boolean variables. Consider the following two statements. (S1)…
Boolean Algebra and Logic Minimization
DatabasesMCQ1 markEasy (estimate)
Q.13 (CS Q.3)
Consider the following relation $Cinema (theater, address, capacity)$ Which of the following options will be needed at the end of the SQL query ...
SQL Queries and Integrity Constraints · Relational Algebra and Tuple Relational Calculus
AlgorithmsMCQ1 markEasy (estimate)
Q.14 (CS Q.4)
Consider the equality $\sum_{i = 0}^{n} i^{3} = X$ and the following choices for $X$ …
Asymptotic Analysis and Time/Space Complexity
Engineering MathematicsNAT1 markMedium (estimate)
Q.15 (CS Q.5)
The number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set ${1, 2, 3}$ is _____.
Combinatorics, Counting, Recurrence Relations and Generating Functions
Computer NetworksMCQ1 markEasy (estimate)
Q.16 (CS Q.6)
Consider a CSMA/CD network that transmits data at a rate of 100 Mbps ( $1 0^{8}$ bits per second) over a 1 km (Kilometer) cable with no repeaters. If the minimum frame size required...
Medium Access Control (ALOHA, CSMA/CD) and Ethernet/Switching
Programming in CMCQ1 markEasy (estimate)
Q.17 (CS Q.7)
Consider the following C program segment. #include <stdio.h> int main() { char s1[7] = "1234", *p; p = s1 + 2; *p = '0'; printf("%s", s1); } What will be printed by the...
Pointers, Arrays and Strings
Computer NetworksMCQ1 markMedium (estimate)Not in current syllabus
Q.18 (CS Q.8)
In a web server, ten WebPages are stored with the URLs of the form http://www.yourname.com/var.html; where, var is a different number from 1 to 10 for each Webpage. Suppose,...
Application Layer: DNS, HTTP, SMTP, FTP
Engineering MathematicsMCQ1 markEasy (estimate)
Q.19 (CS Q.9)
The value of $lim_{x \to \infty} (1 + x^{2})^{e^{- x}}$ is
Calculus
Operating SystemsMCQ1 markMedium (estimate)
Q.20 (CS Q.10)
Two processes X and Y need to access a critical section. Consider the following synchronization construct used by both the processes /* Process X */ while (true) { varP = t...
Process Synchronization and Concurrency
Engineering MathematicsNAT1 markMedium (estimate)Not in current syllabus
Q.21 (CS Q.11)
Consider a software program that is artificially seeded with 100 faults. While testing this program, 159 faults are detected, out of which 75 faults are from those artificially...
Probability and Statistics
Data StructuresMCQ1 markEasy (estimate)
Q.22 (CS Q.12)
The result evaluating the postfix expression $105 + 606 / * 8 -$ is
Stacks and Queues
Data StructuresMCQ1 markEasy (estimate)
Q.23 (CS Q.13)
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
Binary Trees, Binary Search Trees and Balanced Trees
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.24 (CS Q.14)
Consider a machine with a byte addressable main memory of $2^{20}$ bytes, block size of 16 bytes and a direct mapped cache having $2^{12}$ cache lines. Let the addresses of two...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Engineering MathematicsMCQ1 markEasy (estimate)
Q.25 (CS Q.15)
In the given matrix $101 - 1 12 201$ one of the eigenvalues is 1. The eigenvectors corresponding to the eigenvalue 1 are
Linear Algebra
Compiler DesignMCQ1 markEasy (estimate)
Q.26 (CS Q.16)
Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most po...
Parsing and Syntax Analysis (LL and LR)
Data StructuresNAT1 markEasy (estimate)
Q.27 (CS Q.17)
Given a hash table $T$ with 25 slots that stores 2000 elements, the load factor $α$ for $T$ is _____.
Hash Tables and Collision Resolution
Theory of ComputationMCQ1 markMedium (estimate)
Q.28 (CS Q.18)
Let $L$ be the language represented by the regular expression $Σ^{*} 0011 Σ^{*}$ where $Σ = {0, 1}$ . What is the minimum number of states in a DFA that recognizes…
Regular Expressions, Finite Automata and Regular Languages
Data StructuresMCQ1 markMedium (estimate)
Q.29 (CS Q.19)
Consider the following array of elements $⟨ 89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100 ⟩$ The minimum number of interchanges needed to convert it into a max-he...
Binary Heaps and Priority Queues
DatabasesMCQ1 markEasy (estimate)
Q.30 (CS Q.20)
Consider the relation $X (P, Q, R, S, T, U)$ with the following set of functional dependencies $F = {{P, R} \to {S, T}, {P, S, U} \to {Q, R}}$ Which of the followi...
Functional Dependencies and Normalization
Engineering MathematicsNAT1 markMedium (estimate)Not in current syllabus
Q.31 (CS Q.21)
Consider a software project with the following information domain characteristics for calculation of function point metric.…
Combinatorics, Counting, Recurrence Relations and Generating Functions
Computer NetworksMCQ1 markEasy (estimate)
Q.32 (CS Q.22)
Consider the following statements. I. TCP connections are full duplex II. TCP has no option for selective acknowledgement III. TCP connections are message streams Which of the f...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Engineering MathematicsMCQ1 markEasy (estimate)
Q.33 (CS Q.23)
Suppose $U$ is the power set of the set $S = {1, 2, 3, 4, 5, 6}$ . For any $T \in U$ , let $∣ T ∣$ denote the number of elements in $T$ and $T^{'}$ denote the complement of $T$ . For...
Sets, Relations, Functions, Partial Orders and Lattices
Engineering MathematicsMCQ1 markMedium (estimate)
Q.34 (CS Q.24)
In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in tha...
Propositional and First-Order Logic
Data StructuresNAT1 markEasy (estimate)
Q.35 (CS Q.25)
Consider a binary tree $T$ that has 200 leaf nodes. Then, the number of nodes in $T$ that have exactly two children are _____.
Binary Trees, Binary Search Trees and Balanced Trees
Programming in CNAT2 marksMedium (estimate)
Q.36 (CS Q.26)
Consider the following C program. #include <stdio.h> int main() { static int a[] = {10, 20, 30, 40, 50}; static int *p[] = {a, a + 3, a + 4, a + 1, a + 2}; int **ptr = p; p...
Pointers, Arrays and Strings
AlgorithmsMCQ2 marksMedium (estimate)
Q.37 (CS Q.27)
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a proble...
Searching and Sorting Algorithms · Asymptotic Analysis and Time/Space Complexity
Computer NetworksNAT2 marksMedium (estimate)
Q.38 (CS Q.28)
Consider a network connecting two systems located 8000 kilometers apart. The bandwidth of the network is $500 \times 1 0^{6}$ bits per second. The propagation speed of the media is...
Data Link Layer: Framing, Error Detection and Sliding Window
DatabasesMCQ2 marksMedium (estimate)
Q.39 (CS Q.29)
Consider the following partial Schedule $S$ involving two transactions $T 1$ and $T 2$ . Only the read and the write operations have been shown. The read operation on data item $P$ ...
Transactions, Serializability and Concurrency Control
Programming in CMCQ2 marksMedium (estimate)
Q.40 (CS Q.30)
Consider the following two C code segments. $Y$ and $X$ are one and two dimensional arrays of size $n$ and $n \times n$ respectively, where $2 \leq n \leq 10$ . Assume that in both...
Pointers, Arrays and Strings · Memory Hierarchy: Cache, Main Memory and Secondary Storage
Compiler DesignMCQ2 marksEasy (estimate)
Q.41 (CS Q.31)
Consider the following grammar $G$ $S F H \to F ∣ H \to p ∣ c \to d ∣ c$ where $S, F,$ and $H$ are non-terminal symbols…
Parsing and Syntax Analysis (LL and LR)
Theory of ComputationMCQ2 marksMedium (estimate)
Q.42 (CS Q.32)
Which of the following languages are context-free?…
Context-Free Grammars, Pushdown Automata and CFLs
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.43 (CS Q.33)
If the following system has non-trivial solution, $p x + q y + r z q x + r y + p z r x + p y + q z = 0 = 0 = 0$ then which one of the...
Linear Algebra
Operating SystemsMCQ2 marksMedium (estimate)
Q.44 (CS Q.34)
For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time? Process Arrival Time Processing Time A 0...
CPU Scheduling
Digital LogicNAT2 marksMedium (estimate)
Q.45 (CS Q.35)
Consider the equation $(43)_{x} = (y 3)_{8}$ where $x$ and $y$ are unknown. The number of possible solutions is _____.
Number Representations and Computer Arithmetic
Computer NetworksNAT2 marksHard (estimate)
Q.46 (CS Q.36)
Two hosts are connected via a packet switch with $1 0^{7}$ bits per second links. Each link has a propagation delay of 20 microseconds. The switch begins forwarding a packet 35 mic...
OSI/TCP-IP Layering, Physical Layer and Switching
Engineering MathematicsNAT2 marksEasy (estimate)
Q.47 (CS Q.37)
Suppose $X_{i}$ for $i = 1, 2, 3$ are independent and identically distributed random variables whose probability mass functions are $Pr [X_{i} = 0] = Pr [X_{i} = 1] = 1/2$ for…
Probability and Statistics
Computer NetworksNAT2 marksMedium (estimate)
Q.48 (CS Q.38)
In the network 200.10.11.144/27, the fourth octet (in decimal) of the last IP address of the network which can be assigned to a host is _____.
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Programming in CMCQ2 marksMedium (estimate)
Q.49 (CS Q.39)
Consider the following recursive C function. void get(int n) { if (n < 1) return; get(n - 1); get(n - 3); printf("%d", n); } If get(6) function is being called in…
Functions, Recursion, Scope and Storage Classes
AlgorithmsNAT2 marksEasy (estimate)
Q.50 (CS Q.40)
Let $G$ be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of $G$ is 500. When the weight of each edge of $G$ is increased by f...
Minimum Spanning Trees
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.51 (CS Q.41)
Let $R$ be a relation on the set of ordered pairs of positive integers such that $((p, q), (r, s)) \in R$ if and only if $p - s = q - r$ . Which one of the following is true abou...
Sets, Relations, Functions, Partial Orders and Lattices
AlgorithmsMCQ2 marksMedium (estimate)
Q.52 (CS Q.42)
Let $f (n) = n$ and $g (n) = n^{1 + s i n n}$ , where $n$ is a positive integer. Which of the following statements is/are correct? I. $f (n) = O (g (n))$ II. $f (n) = Ω (g (n))$
Asymptotic Analysis and Time/Space Complexity
Digital LogicNAT2 marksMedium (estimate)
Q.53 (CS Q.43)
The total number of prime implicants of the function $f (w, x, y, z) = \sum (0, 2, 4, 5, 6, 10)$ is _____.
Boolean Algebra and Logic Minimization
Digital LogicMCQ2 marksEasy (estimate)
Q.54 (CS Q.44)
Given the function $F = P^{'} + QR$ , where $F$ is a function in three Boolean variables $P, Q$ and $R$ and $P^{'} = \neg P$ , consider the following statements. (S1)…
Boolean Algebra and Logic Minimization
Engineering MathematicsMCQ2 marksHard (estimate)
Q.55 (CS Q.45)
If for non-zero $x$ , $a f (x) + b f (\frac{1}{x}) = \frac{1}{x} - 25$ where $a \neq = b$ then $\int_{1}^{2} f (x) d x$ is
Calculus
DatabasesNAT2 marksMedium (estimate)
Q.56 (CS Q.46)
Consider a B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of k...
File Organization, B-Trees and B+ Trees Indexing
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.57 (CS Q.47)
Consider the following code sequence having five instructions $I_{1}$ to $I_{5}$ . Each of these instructions has the following format. OP Ri, Rj, Rk where operation OP is perfor...
Instruction Pipelining and Hazards
Programming in CNAT2 marksMedium (estimate)
Q.58 (CS Q.48)
Consider the following C program: #include <stdio.h> int main() { int i, j, k = 0; j = 2 * 3 / 4 + 2.0 / 5 + 8 / 5; k -= --j; for (i = 0; i < 5; i++) { switch (i + k) { cas...
Data Types, Operators and Control Flow
Engineering MathematicsNAT2 marksEasy (estimate)
Q.59 (CS Q.49)
Suppose $c = (c [0], \dots, c [k - 1])$ is an array of length $k$ , where all the entries are from the set ${0, 1}$ . For any positive integers $a$ and $n$ , consider the following...
Combinatorics, Counting, Recurrence Relations and Generating Functions · Asymptotic Analysis and Time/Space Complexity
Engineering MathematicsNAT2 marksMedium (estimate)
Q.60 (CS Q.50)
The velocity $v$ (in kilometer/minute) of a motorbike which starts from rest, is given at fixed intervals of time $t$ (in minutes) as follows: t 2 4 6 8 10 12 14 16 18 20 v 10 1...
Calculus
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.61 (CS Q.51)
Consider the following reservation table for a pipeline having three stages $S_{1}, S_{2}$ and $S_{3}$ : Stage \ Time 1 2 3 4 5 S1 X X S2 X X S3 X The minimum average latency (MAL) is...
Instruction Pipelining and Hazards
Operating SystemsMCQ2 marksEasy (estimate)
Q.62 (CS Q.52)
Consider the following policies for preventing deadlock in a system with mutually exclusive resources: I. Processes should acquire all their resources at the beginning of execut...
Deadlock Prevention, Avoidance and Detection
AlgorithmsMCQ2 marksMedium (estimate)
Q.63 (CS Q.53)
Language $L_{1}$ is polynomial time reducible to language $L_{2}$ . Language $L_{2}$ is polynomial time reducible to $L_{3}$ , which in turn is polynomial time reducible to language $L_{4}$ ...
Asymptotic Analysis and Time/Space Complexity
Programming in CNAT2 marksMedium (estimate)
Q.64 (CS Q.54)
Consider the following C program. #include <stdio.h> int f1(void); int f2(void); int f3(void); int x = 10; int main() { int x = 1; x += f1() + f2() + f3() + f2(); printf("%...
Functions, Recursion, Scope and Storage Classes
Engineering MathematicsMCQ2 marksMedium (estimate)Not in current syllabus
Q.65 (CS Q.55)
Consider three software items: Program-X, Control Flow Diagram of Program-Y and Control Flow Diagram of Program-Z as shown below. Program-X: sumcal(int maxint, int value) {...
Graph Theory