GATE CS 2014 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)
Which of the following options is the closest in meaning to the phrase underlined in the sentence below? It is fascinating to see life forms cope with varied environmental condi...
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.2 (GA Q.2)
Choose the most appropriate word from the options given below to complete the following sentence. He could not understand the judges awarding her the first prize, because he tho...
Verbal Ability and Grammar
General AptitudeMCQ1 markEasy (estimate)
Q.3 (GA Q.3)
In a press meet on the recent scam, the minister said, "The buck stops here". What did the minister convey by the statement?
Verbal Ability and Grammar
General AptitudeNAT1 markEasy (estimate)
Q.4 (GA Q.4)
If $(z + 1/ z)^{2} = 98$ , compute $(z^{2} + 1/ z^{2})$ .
Quantitative Aptitude
General AptitudeMCQ1 markMedium (estimate)
Q.5 (GA Q.5)
The roots of $a x^{2} + b x + c = 0$ are real and positive. $a$ , $b$ and $c$ are real. Then $a x^{2} + b ∣ x ∣ + c = 0$ has
Quantitative Aptitude
General AptitudeMCQ2 marksEasy (estimate)
Q.6 (GA Q.6)
The Palghat Gap (or Palakkad Gap), a region about 30 km wide in the southern part of the Western Ghats in India, is lower than the hilly terrain to its north and south. The exac...
Reading Comprehension and Verbal Deduction
General AptitudeMCQ2 marksEasy (estimate)
Q.7 (GA Q.7)
Geneticists say that they are very close to confirming the genetic roots of psychiatric illnesses such as depression and schizophrenia, and consequently, that doctors will be ab...
Reading Comprehension and Verbal Deduction
General AptitudeNAT2 marksEasy (estimate)
Q.8 (GA Q.8)
Round-trip tickets to a tourist destination are eligible for a discount of 10% on the total fare. In addition, groups of 4 or more get a discount of 5% on the total fare. If the...
Quantitative Aptitude
General AptitudeNAT2 marksEasy (estimate)
Q.9 (GA Q.9)
In a survey, 300 respondents were asked whether they own a vehicle or not. If yes, they were further asked to mention whether they own a car or scooter or both. Their responses...
Data Interpretation and Graphs
General AptitudeNAT2 marksMedium (estimate)
Q.10 (GA Q.10)
When a point inside of a tetrahedron (a solid with four triangular surfaces) is connected by straight lines to its corners, how many (new) internal planes are created with these...
Spatial Aptitude

Computer Science and Information Technology

55 questions, 85 marks

Engineering MathematicsMCQ1 markEasy (estimate)
Q.11 (CS Q.1)
Consider the statement $“Not all that glitters is gold”$ Predicate $g l i tt er s (x)$ is true if $x$ glitters and predicate $g o l d (x)$ is true if $x$ is gold. Which one of th...
Propositional and First-Order Logic
Engineering MathematicsNAT1 markMedium (estimate)
Q.12 (CS Q.2)
Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________ .
Probability and Statistics
AlgorithmsMCQ1 markEasy (estimate)
Q.13 (CS Q.3)
Let $G = (V, E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected components as...
Graph Traversals, Topological Sort and Connectivity
Engineering MathematicsNAT1 markMedium (estimate)
Q.14 (CS Q.4)
Consider the following system of equations: $3 x + 2 y = 1$ $4 x + 7 z = 1$ $x + y + z = 3$ $x - 2 y + 7 z = 0$ The number of solutions for this system is __________________
Linear Algebra
Engineering MathematicsNAT1 markEasy (estimate)
Q.15 (CS Q.5)
The value of the dot product of the eigenvectors corresponding to any pair of different eigenvalues of a 4-by-4 symmetric positive definite matrix is _____________________.
Linear Algebra
Engineering MathematicsMCQ1 markMedium (estimate)
Q.16 (CS Q.6)
Let the function…
Calculus
Digital LogicMCQ1 markEasy (estimate)
Q.17 (CS Q.7)
Consider the following Boolean expression for $F$ : $F (P, Q, R, S) = P Q + P ˉ QR + P ˉ Q R ˉ S$ The minimal sum-of-products form of $F$ is
Boolean Algebra and Logic Minimization
Digital LogicNAT1 markEasy (estimate)
Q.18 (CS Q.8)
The base (or radix) of the number system such that the following equation holds is____________. $\frac{312}{20} = 13.1$
Number Representations and Computer Arithmetic
Computer Organization and ArchitectureNAT1 markMedium (estimate)
Q.19 (CS Q.9)
A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immedi...
Machine Instructions and Addressing Modes
Programming in CMCQ1 markEasy (estimate)
Q.20 (CS Q.10)
Consider the following program in C language: #include <stdio.h> main() { int i; int *pi = &i; scanf("%d", pi); printf("%d\n", i + 5); } Which one of the following stat...
Pointers, Arrays and Strings
AlgorithmsMCQ1 markEasy (estimate)
Q.21 (CS Q.11)
Let $G$ be a graph with $n$ vertices and $m$ edges. What is the tightest upper bound on the running time of Depth First Search on $G$ , when $G$ is represented as an adjacency ma...
Graph Traversals, Topological Sort and Connectivity
Data StructuresNAT1 markMedium (estimate)
Q.22 (CS Q.12)
Consider a rooted $n$ node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is…
Binary Trees, Binary Search Trees and Balanced Trees
AlgorithmsMCQ1 markEasy (estimate)
Q.23 (CS Q.13)
Consider the directed graph given below. Directed graph on four vertices P, Q, R, and S Which one of the following is TRUE?
Graph Traversals, Topological Sort and Connectivity
AlgorithmsMCQ1 markMedium (estimate)
Q.24 (CS Q.14)
Let $P$ be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let $t_{1}$ and $t_{2}$ be the number of comparisons made by $P$ for the inpu...
Searching and Sorting Algorithms
Theory of ComputationMCQ1 markEasy (estimate)
Q.25 (CS Q.15)
Which one of the following is TRUE?
Regular Expressions, Finite Automata and Regular Languages
Theory of ComputationMCQ1 markEasy (estimate)
Q.26 (CS Q.16)
Consider the finite automaton in the following figure. Non-deterministic finite automaton with four states q0, q1, q2, and q3 What is the set of reachable states for the input s...
Regular Expressions, Finite Automata and Regular Languages
Compiler DesignMCQ1 markEasy (estimate)
Q.27 (CS Q.17)
Which one of the following is FALSE?
Intermediate Code Generation, Data Flow Analysis and Code Optimization
Programming in CMCQ1 markEasy (estimate)Not in current syllabus
Q.28 (CS Q.18)
Match the following: 1) Waterfall model: a) Specifications can be developed incrementally 2) Evolutionary model: b) Requirements compromises are inevitable 3) Component-based so...
Functions, Recursion, Scope and Storage Classes
Operating SystemsNAT1 markEasy (estimate)
Q.29 (CS Q.19)
Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 10...
File Systems, I/O and Disk Scheduling
Operating SystemsMCQ1 markEasy (estimate)
Q.30 (CS Q.20)
Which one of the following is FALSE?
Processes, Threads and System Calls
DatabasesMCQ1 markEasy (estimate)
Q.31 (CS Q.21)
Consider the relation scheme $R = (E, F, G, H, I, J, K, L, M, N)$ and the set of functional dependencies…
Functional Dependencies and Normalization
DatabasesMCQ1 markMedium (estimate)
Q.32 (CS Q.22)
Given the following statements: S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL. S2: Given the table R(a,b,c) where a and b together...
SQL Queries and Integrity Constraints
Computer NetworksMCQ1 markMedium (estimate)
Q.33 (CS Q.23)
Consider the following three statements about link state and distance vector routing protocols, for a large network with 500 network nodes and 4000 links. [S1] The computational...
Routing Algorithms (Distance Vector, Link State) and BGP/OSPF
Computer NetworksMCQ1 markEasy (estimate)
Q.34 (CS Q.24)
Which of the following are used to generate a message digest by the network security protocols? (P) RSA (Q) SHA-1 (R) DES (S) MD5
Application Layer: DNS, HTTP, SMTP, FTP
Computer NetworksMCQ1 markEasy (estimate)
Q.35 (CS Q.25)
Identify the correct order in which the following actions take place in an interaction between a web browser and a web server. 1. The web browser requests a webpage using HTTP....
Application Layer: DNS, HTTP, SMTP, FTP
Computer NetworksNAT2 marksMedium (estimate)
Q.36 (CS Q.26)
Consider a token ring network with a length of 2 km having 10 stations including a monitoring station. The propagation speed of the signal is $2 \times 1 0^{8}$ m/s and the token t...
Medium Access Control (ALOHA, CSMA/CD) and Ethernet/Switching
Computer NetworksNAT2 marksHard (estimate)
Q.37 (CS Q.27)
Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 msec and the maximum segment size used is 2 KB...
Transport Layer: UDP, TCP Flow and Congestion Control, Sockets
Computer NetworksNAT2 marksMedium (estimate)
Q.38 (CS Q.28)
Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilizati...
Data Link Layer: Framing, Error Detection and Sliding Window
DatabasesMCQ2 marksMedium (estimate)
Q.39 (CS Q.29)
Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which...
Transactions, Serializability and Concurrency Control
DatabasesMCQ2 marksMedium (estimate)
Q.40 (CS Q.30)
Given the following two statements: S1: Every table with two single-valued attributes is in 1NF, 2NF, 3NF and BCNF. S2: AB $\to$ C, D $\to$ E, E $\to$ C is a minimal cover for the set...
Functional Dependencies and Normalization
Operating SystemsMCQ2 marksMedium (estimate)
Q.41 (CS Q.31)
An operating system uses the Banker’s algorithm for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The ta...
Deadlock Prevention, Avoidance and Detection
Operating SystemsNAT2 marksMedium (estimate)
Q.42 (CS Q.32)
Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds. Process Name Arrival Time Execution Time A 0 6 B 3 2...
CPU Scheduling
Operating SystemsNAT2 marksEasy (estimate)
Q.43 (CS Q.33)
Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal repla...
Memory Management and Virtual Memory
Compiler DesignMCQ2 marksMedium (estimate)
Q.44 (CS Q.34)
A canonical set of items is given below $S \to L . > R$ $Q \to R .$ On input symbol $<$ the set has
Parsing and Syntax Analysis (LL and LR)
Theory of ComputationMCQ2 marksEasy (estimate)
Q.45 (CS Q.35)
Let $L$ be a language and $L ˉ$ be its complement. Which one of the following is NOT a viable possibility?
Decidability, Reducibility and Undecidability
Theory of ComputationMCQ2 marksMedium (estimate)
Q.46 (CS Q.36)
Which of the regular expressions given below represent the following DFA? Deterministic finite automaton with two states accepting binary strings I) $0^{*} 1 (1 + 0 0^{*} 1)^{*}$ II)…
Regular Expressions, Finite Automata and Regular Languages
Engineering MathematicsNAT2 marksEasy (estimate)
Q.47 (CS Q.37)
There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 1...
Combinatorics, Counting, Recurrence Relations and Generating Functions
Theory of ComputationMCQ2 marksMedium (estimate)
Q.48 (CS Q.38)
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correc...
Turing Machines and Chomsky Hierarchy
AlgorithmsNAT2 marksMedium (estimate)
Q.49 (CS Q.39)
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.
Searching and Sorting Algorithms
Data StructuresMCQ2 marksEasy (estimate)
Q.50 (CS Q.40)
Consider a hash table with 9 slots. The hash function is $h (k) = k mod 9$ . The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19,...
Hash Tables and Collision Resolution
Programming in CMCQ2 marksMedium (estimate)
Q.51 (CS Q.41)
Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) { int Y = 0; int Z; int i, j, k; for(i = 0; i <...
Data Types, Operators and Control Flow
AlgorithmsMCQ2 marksMedium (estimate)
Q.52 (CS Q.42)
Consider the following pseudo code. What is the total number of multiplications to be performed? D = 2 for i = 1 to n do for j = i to n do for k = j + 1 to n do D = D *...
Asymptotic Analysis and Time/Space Complexity
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.53 (CS Q.43)
Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on...
Instruction Pipelining and Hazards
Computer Organization and ArchitectureMCQ2 marksMedium (estimate)
Q.54 (CS Q.44)
An access sequence of cache block addresses is of length $N$ and contains $n$ unique block addresses. The number of unique block addresses between two consecutive accesses to th...
Memory Hierarchy: Cache, Main Memory and Secondary Storage
Digital LogicMCQ2 marksMedium (estimate)
Q.55 (CS Q.45)
Consider the 4-to-1 multiplexer with two select lines $P$ and $Q$ given below. 4-to-1 Multiplexer with inputs 0, 1, R, R-bar, select lines P, Q, and output F The minimal sum-of-...
Combinational Circuits
Engineering MathematicsNAT2 marksEasy (estimate)
Q.56 (CS Q.46)
The function $f (x) = x sin x$ satisfies the following equation: $f^{''} (x) + f (x) + t cos x = 0$ . The value of $t$ is ______.
Calculus
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.57 (CS Q.47)
A function $f (x)$ is continuous in the interval $[0, 2]$ . It is known that $f (0) = f (2) = - 1$ and $f (1) = 1$ . Which one of the following statements must be true?
Calculus
Engineering MathematicsNAT2 marksMedium (estimate)
Q.58 (CS Q.48)
Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is $X /1296$ . The value of $X$ is ______________.
Probability and Statistics
Engineering MathematicsNAT2 marksMedium (estimate)
Q.59 (CS Q.49)
A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all poss...
Combinatorics, Counting, Recurrence Relations and Generating Functions
Engineering MathematicsNAT2 marksEasy (estimate)
Q.60 (CS Q.50)
Let $S$ denote the set of all functions $f : {0, 1}^{4} \to {0, 1}$ . Denote by $N$ the number of functions from $S$ to the set ${0, 1}$ . The value of $lo g_{2} lo g_{2} N$ is ______.
Sets, Relations, Functions, Partial Orders and Lattices
Engineering MathematicsNAT2 marksMedium (estimate)
Q.61 (CS Q.51)
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is ${(i, j) : 1 \leq i \leq 12, 1 \leq j \leq 12}$ . There is an edge between $(a, b)$ and…
Graph Theory
Engineering MathematicsMCQ2 marksMedium (estimate)
Q.62 (CS Q.52)
An ordered $n$ -tuple $(d_{1}, d_{2}, \dots, d_{n})$ with $d_{1} \geq d_{2} \geq \dots \geq d_{n}$ is called graphic if there exists a simple undirected graph with vertices having degrees…
Graph Theory
Engineering MathematicsMCQ2 marksEasy (estimate)
Q.63 (CS Q.53)
Which one of the following propositional logic formulas is TRUE when exactly two of $p$ , $q$ , and $r$ are TRUE?
Propositional and First-Order Logic
DatabasesMCQ2 marksMedium (estimate)
Q.64 (CS Q.54)
Given the following schema: employees(emp-id, first-name, last-name, hire-date, dept-id, salary) departments(dept-id, dept-name, manager-id, location-id) You want to...
SQL Queries and Integrity Constraints
Computer Organization and ArchitectureNAT2 marksMedium (estimate)
Q.65 (CS Q.55)
Consider two processors $P_{1}$ and $P_{2}$ executing the same instruction set. Assume that under identical conditions, for the same input, a program running on $P_{2}$ takes 25% less...
ALU, Datapath and Control Unit