GATE CS 2015 Set 1 question paper: all 65 questions with answers and solutions

General Aptitude

10 questions, 15 marks

General AptitudeMCQ1 markEasy (estimate)
Q.1 (GA Q.1)
Didn't you buy _____ when you went shopping?
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.2 (GA Q.2)
Which of the following options is the closest in meaning to the sentence below? She enjoyed herself immensely at the party.
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
Given Set $A = {2, 3, 4, 5}$ and Set $B = {11, 12, 13, 14, 15}$ , two numbers are randomly selected, one from each set. What is the probability that the sum of the two number...
Quantitative Aptitude
General AptitudeMCQ1 markEasy (estimate)
Q.4 (GA Q.4)
Based on the given statements, select the most appropriate option to solve the given question. If two floors in a certain building are $9$ feet apart, how many steps are there i...
Analytical and Logical Reasoning
General AptitudeMCQ1 markEasy (estimate)
Q.5 (GA Q.5)
Which one of the following combinations is incorrect?
Verbal Ability and Grammar
General AptitudeMCQ2 marksMedium (estimate)
Q.6 (GA Q.6)
The number of students in a class who have answered correctly, wrongly, or not attempted each question in an exam, are listed in the table below. The marks for each question are...
Data Interpretation and Graphs
General AptitudeMCQ2 marksEasy (estimate)
Q.7 (GA Q.7)
Select the alternative meaning of the underlined part of the sentence. The chain snatchers took to their heels when the police party arrived.
Verbal Ability and Grammar
General AptitudeMCQ2 marksEasy (estimate)
Q.8 (GA Q.8)
The given statement is followed by some courses of action. Assuming the statement to be true, decide the correct option. Statement: There has been a significant drop in the...
Analytical and Logical Reasoning
General AptitudeNAT2 marksMedium (estimate)
Q.9 (GA Q.9)
The pie chart below has the breakup of the number of students from different departments in an engineering college for the year 2012. The proportion of male to female students i...
Data Interpretation and Graphs
General AptitudeMCQ2 marksMedium (estimate)
Q.10 (GA Q.10)
The probabilities that a student passes in Mathematics, Physics and Chemistry are $m, p,$ and $c$ respectively. Of these subjects, the student has $75%$ chance of passing in at...
Quantitative Aptitude

Computer Science and Information Technology

55 questions, 85 marks

Programming in CMCQ1 markEasy (estimate)Not in current syllabus
Q.11 (CS Q.1)
Match the following: | | Testing Technique | | Testing Category | | :--- | :--- | :--- | :--- | | (P) | Condition coverage | (i) | Black-box testing | | (Q) | Equivalence class...
Functions, Recursion, Scope and Storage Classes
AlgorithmsMCQ1 markEasy (estimate)
Q.12 (CS Q.2)
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting $n$ ( $n \geq 2$ ) numbers? In the recurrence equati...
Asymptotic Analysis and Time/Space Complexity
Theory of ComputationMCQ1 markMedium (estimate)
Q.13 (CS Q.3)
For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is context-free and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessarily true? I.…
Decidability, Reducibility and Undecidability
Engineering MathematicsMCQ1 markEasy (estimate)
Q.14 (CS Q.4)
$lim_{x \to \infty} x^{1/ x}$ is:
Calculus
Engineering MathematicsMCQ1 markMedium (estimate)
Q.15 (CS Q.5)
If $g (x) = 1 - x$ and $h (x) = \frac{x}{x - 1}$ , then $\frac{g ( h ( x ))}{h ( g ( x ))}$ is:
Sets, Relations, Functions, Partial Orders and Lattices
AlgorithmsMCQ1 markEasy (estimate)
Q.16 (CS Q.6)
Match the following: | | Algorithm | | Design Paradigm | | :--- | :--- | :--- | :--- | | (P) | Prim's algorithm for minimum spanning tree | (i) | Backtracking | | (Q) | Floyd-Wa...
Greedy Algorithms
DatabasesMCQ1 markEasy (estimate)
Q.17 (CS Q.7)
SELECT operation in SQL is equivalent to:
SQL Queries and Integrity Constraints
Computer Organization and ArchitectureMCQ1 markEasy (estimate)
Q.18 (CS Q.8)
For computers based on three-address instruction formats, each address field can be used to specify which of the following: (S1) A memory operand (S2) A processor register (S3)...
Machine Instructions and Addressing Modes
Operating SystemsNAT1 markMedium (estimate)
Q.19 (CS Q.9)
The following two functions P1 and P2 that share a variable B with an initial value of $2$ execute concurrently. P1() { C = B - 1; B = 2 * C; } P2() { D = 2...
Process Synchronization and Concurrency
Data StructuresMCQ1 markEasy (estimate)
Q.20 (CS Q.10)
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? I. $3, 5, 7, 8, 15, 19, 25$ II. $5, 8, 9, 12, 10, 15, 25$ III.…
Binary Trees, Binary Search Trees and Balanced Trees
Programming in CNAT1 markEasy (estimate)
Q.21 (CS Q.11)
The output of the following C program is _____. #include <stdio.h> void f1(int a, int b) { int c; c = a; a = b; b = c; } void f2(int *a, int *b) { int c; c = *a; *a = *b; *...
Pointers, Arrays and Strings
Operating SystemsNAT1 markEasy (estimate)
Q.22 (CS Q.12)
Consider a system with byte-addressable memory, 32-bit logical addresses, $4 kilobyte$ page size and page table entries of $4 bytes$ each. The size of the page tab...
Memory Management and Virtual Memory
Compiler DesignMCQ1 markMedium (estimate)
Q.23 (CS Q.13)
Which one of the following is TRUE at any valid state in shift-reduce parsing?
Parsing and Syntax Analysis (LL and LR)
Engineering MathematicsMCQ1 markEasy (estimate)
Q.24 (CS Q.14)
Which one of the following is NOT equivalent to $p \leftrightarrow q$ ?
Propositional and First-Order Logic
Computer NetworksMCQ1 markEasy (estimate)Not in current syllabus
Q.25 (CS Q.15)
Which of the following statements is/are FALSE? I. XML overcomes the limitations in HTML to support a structured way of organizing content. II. XML specification is not case sen...
Application Layer: DNS, HTTP, SMTP, FTP
Engineering MathematicsMCQ1 markMedium (estimate)
Q.26 (CS Q.16)
For a set $A$ , the power set of $A$ is denoted by $2^{A}$ . If $A = {5, {6}, {7}}$ , which of the following options are TRUE? I. $\emptyset \in 2^{A}$ II.…
Sets, Relations, Functions, Partial Orders and Lattices
Computer NetworksMCQ1 markEasy (estimate)
Q.27 (CS Q.17)
In one of the pairs of protocols given below, both the protocols can use multiple TCP connections between the same client and the server. Which one is that?
Application Layer: DNS, HTTP, SMTP, FTP
Engineering MathematicsNAT1 markEasy (estimate)
Q.28 (CS Q.18)
In the LU decomposition of the matrix $[2429]$ , if the diagonal elements of $U$ are both $1$ , then the lower diagonal entry $l_{22}$ of $L$ ...
Linear Algebra
Computer NetworksMCQ1 markMedium (estimate)
Q.29 (CS Q.19)
Suppose two hosts use a TCP connection to transfer a large file. Which of the following statements is/are FALSE with respect to the TCP connection? I. If the sequence number of...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Digital LogicMCQ1 markEasy (estimate)
Q.30 (CS Q.20)
Consider a 4-bit Johnson counter with an initial value of $0000$ . The counting sequence of this counter is:
Sequential Circuits, Counters and Registers
Computer NetworksMCQ1 markEasy (estimate)
Q.31 (CS Q.21)
Suppose that everyone in a group of $N$ people wants to communicate secretly with the $N - 1$ others using symmetric key cryptographic system. The communication between any two pe...
Application Layer: DNS, HTTP, SMTP, FTP
Computer NetworksMCQ1 markEasy (estimate)
Q.32 (CS Q.22)
Which one of the following fields of an IP header is NOT modified by a typical IP router?
IPv4/IPv6 Addressing, Subnetting, CIDR, ARP, ICMP and NAT
Data StructuresMCQ1 markEasy (estimate)
Q.33 (CS Q.23)
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?
Binary Trees, Binary Search Trees and Balanced Trees
DatabasesMCQ1 markEasy (estimate)
Q.34 (CS Q.24)
A file is organized so that the ordering of data records is the same as or close to the ordering of data entries in some index. Then that index is called:
File Organization, B-Trees and B+ Trees Indexing
Data StructuresMCQ1 markEasy (estimate)
Q.35 (CS Q.25)
The height of a tree is the length of the longest root-to-leaf path in it. The maximum and minimum number of nodes in a binary tree of height $5$ are:
Binary Trees, Binary Search Trees and Balanced Trees
Engineering MathematicsNAT2 marksEasy (estimate)
Q.36 (CS Q.26)
$\sum_{x = 1}^{99} \frac{1}{x ( x + 1 )}$ The value of the summation is _____.
Calculus
DatabasesNAT2 marksEasy (estimate)
Q.37 (CS Q.27)
Consider the following relations: Student | Roll No | Student Name | | :---: | :---: | | 1 | Raj | | 2 | Rohit | | 3 | Raj | Performance | Roll No | Course | Marks | | :...
SQL Queries and Integrity Constraints
Digital LogicMCQ2 marksEasy (estimate)
Q.38 (CS Q.28)
The binary operator $\neq =$ is defined by the following truth table: | $p$ | $q$ | $p \neq = q$ | | :---: | :---: | :---: | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | Wh...
Boolean Algebra and Logic Minimization
Computer NetworksNAT2 marksMedium (estimate)
Q.39 (CS Q.29)
Consider a LAN with four nodes $S_{1}, S_{2}, S_{3}$ and $S_{4}$ . Time is divided into fixed-size slots, and a node can begin its transmission only at the beginning of a slot. A collisi...
Medium Access Control (ALOHA, CSMA/CD) and Ethernet/Switching
Operating SystemsNAT2 marksMedium (estimate)
Q.40 (CS Q.30)
Suppose the following disk request sequence (track numbers) for a disk with $100$ tracks is given: $45, 20, 90, 10, 50, 60, 80, 25, 70$ . Assume that the initial position of the...
File Systems, I/O and Disk Scheduling
AlgorithmsMCQ2 marksMedium (estimate)
Q.41 (CS Q.31)
Consider the following C function: int fun1(int n) { int i, j, k, p, q = 0; for (i = 1; i < n; ++i) { p = 0; for (j = n; j > 1; j = j / 2) ++p; for (k = 1; k < p; k = k * 2...
Asymptotic Analysis and Time/Space Complexity
Data StructuresMCQ2 marksEasy (estimate)
Q.42 (CS Q.32)
Consider a max heap, represented by the array: | Array Index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---...
Binary Heaps and Priority Queues
Programming in CMCQ2 marksEasy (estimate)
Q.43 (CS Q.33)
Consider the following pseudo code, where $x$ and $y$ are positive integers: begin q := 0 r := x while r >= y do begin r := r - y q := q + 1 end end The post conditi...
Data Types, Operators and Control Flow
Engineering MathematicsMCQ2 marksHard (estimate)
Q.44 (CS Q.34)
Suppose $L = {p, q, r, s, t}$ is a lattice represented by the following Hasse diagram: For any $x, y \in L$ , not necessarily distinct, $x \lor y$ and $x \land y$ are join and...
Sets, Relations, Functions, Partial Orders and Lattices
Programming in CMCQ2 marksMedium (estimate)
Q.45 (CS Q.35)
What is the output of the following C code? Assume that the address of x is $2000$ (in decimal) and an integer requires four bytes of memory. #include <stdio.h> int main(...
Pointers, Arrays and Strings
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.46 (CS Q.36)
Consider the following $2 \times 2$ matrix $A$ where two elements are unknown and are marked by $a$ and $b$ . The eigenvalues of this matrix are $- 1$ and $7$ . What are the values...
Linear Algebra
Digital LogicMCQ2 marksMedium (estimate)
Q.47 (CS Q.37)
A positive edge-triggered D flip-flop is connected to a positive edge-triggered JK flip-flop as follows. The Q output of the D flip-flop is connected to both the J and K inputs...
Sequential Circuits, Counters and Registers
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.48 (CS Q.38)
Consider a non-pipelined processor with a clock rate of $2.5 gigahertz$ and average cycles per instruction of four. The same processor is upgraded to a pipelined processo...
Instruction Pipelining and Hazards
Digital LogicMCQ2 marksMedium (estimate)
Q.49 (CS Q.39)
Consider the operations: $f (X, Y, Z) = X^{'} Y Z + X Y^{'} + Y^{'} Z^{'} and g (X, Y, Z) = X^{'} Y Z + X^{'} Y Z^{'} + X Y .$ Which one of the following is correct?
Boolean Algebra and Logic Minimization
Data StructuresMCQ2 marksHard (estimate)
Q.50 (CS Q.40)
An algorithm performs $(lo g N)^{1/2}$ find operations, $N$ insert operations, $(lo g N)^{1/2}$ delete operations, and $(lo g N)^{1/2}$ decrease-key operations on a set of data...
Arrays and Linked Lists
DatabasesNAT2 marksMedium (estimate)
Q.51 (CS Q.41)
Consider an Entity-Relationship (ER) model in which entity sets $E_{1}$ and $E_{2}$ are connected by an $m : n$ relationship $R_{12}$ . $E_{1}$ and $E_{3}$ are connected by a $1 : n$ ( $1$ on...
ER Model and Relational Schema Design
Programming in CNAT2 marksMedium (estimate)Not in current syllabus
Q.52 (CS Q.42)
Consider the following C program segment. while (first <= last) { if (array[middle] < search) first = middle + 1; else if (array[middle] == search) found = TRUE; else last = mid...
Data Types, Operators and Control Flow
AlgorithmsNAT2 marksHard (estimate)
Q.53 (CS Q.43)
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D...
Minimum Spanning Trees
Engineering MathematicsNAT2 marksEasy (estimate)
Q.54 (CS Q.44)
$\int_{1/ π}^{2/ π} \frac{c o s ( 1/ x )}{x ^{2}} d x$ The value of the integral is _____.
Calculus
AlgorithmsMCQ2 marksMedium (estimate)
Q.55 (CS Q.45)
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$ , let $d (x)$ denote the shortest distance in $G$ from $s$ to...
Graph Traversals, Topological Sort and Connectivity
Operating SystemsNAT2 marksMedium (estimate)
Q.56 (CS Q.46)
Consider a uniprocessor system executing three tasks $T_{1}$ , $T_{2}$ and $T_{3}$ , each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically a...
CPU Scheduling
Operating SystemsMCQ2 marksMedium (estimate)
Q.57 (CS Q.47)
Consider a main memory with five page frames and the following sequence of page references: $3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3$ . Which one of the following is true wit...
Memory Management and Virtual Memory
Computer Organization and ArchitectureNAT2 marksEasy (estimate)
Q.58 (CS Q.48)
Consider a disk pack with a seek time of $4$ milliseconds and rotational speed of $10000$ rotations per minute (RPM). It has $600$ sectors per track and each sector can store…
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.59 (CS Q.49)
Let $a_{n}$ represent the number of bit strings of length $n$ containing two consecutive 1s. What is the recurrence relation for $a_{n}$ ?
Combinatorics, Counting, Recurrence Relations and Generating Functions
Compiler DesignMCQ2 marksMedium (estimate)
Q.60 (CS Q.50)
A variable $x$ is said to be live at a statement $S_{i}$ in a program if the following three conditions hold simultaneously: i. There exists a statement $S_{j}$ that uses $x$ ii. Th...
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Theory of ComputationMCQ2 marksMedium (estimate)
Q.61 (CS Q.51)
Consider the NPDA $(Q = {q_{0}, q_{1}, q_{2}}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q_{0}, ⊥, F = {q_{2}})$ , where (as per usual convention) $Q$ is the set of states...
Context-Free Grammars, Pushdown Automata and CFLs
Theory of ComputationNAT2 marksEasy (estimate)
Q.62 (CS Q.52)
Consider the DFAs $M$ and $N$ given below. State transition diagrams for DFAs M and N, accepting strings ending in a and b respectively State transition diagrams of DFAs M and N...
Regular Expressions, Finite Automata and Regular Languages
Computer NetworksNAT2 marksMedium (estimate)
Q.63 (CS Q.53)
Suppose that the stop-and-wait protocol is used on a link with a bit rate of $64$ kilobits per second and $20$ milliseconds propagation delay. Assume that the transmission time...
Data Link Layer: Framing, Error Detection and Sliding Window
Engineering MathematicsNAT2 marksEasy (estimate)
Q.64 (CS Q.54)
Let $G$ be a connected planar graph with $10$ vertices. If the number of edges on each face is three, then the number of edges in $G$ is _____.
Graph Theory
Compiler DesignNAT2 marksMedium (estimate)
Q.65 (CS Q.55)
The least number of temporary variables required to create a three-address code in static single assignment form for the expression $q + r /3 + s - t * 5 + u * v / w$ is _____.
Intermediate Code Generation, Data Flow Analysis and Code Optimization