GATE 2014 CS (Set 1) PYQ: all 65 questions with official answers

Q1 · General Aptitude · Numerical · 1 mark

If

\left(z+\frac{1}{z}\right)^2 = 98,

compute

z^2+\frac{1}{z^2}.

(Answer in integer)

Answer (official key): 96

Worked solution: in your report after you take this paper.

Q2 · General Aptitude · MCQ · 1 mark

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 conditions.

(A)
adopt to
(B)
adapt to
(C)
adept in
(D)
accept with

Answer (official key): B

Worked solution: in your report after you take this paper.

Q3 · General Aptitude · MCQ · 1 mark

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 thought that her performance was quite __________.

(A)
superb
(B)
medium
(C)
mediocre
(D)
exhilarating

Answer (official key): C

Worked solution: in your report after you take this paper.

Q4 · General Aptitude · MCQ · 1 mark

In a press meet on the recent scam, the minister said, “The buck stops here”. What did the minister convey by the statement?

(A)
He wants all the money
(B)
He will return the money
(C)
He will assume final responsibility
(D)
He will resist all enquiries

Answer (official key): C

Worked solution: in your report after you take this paper.

Q5 · General Aptitude · MCQ · 1 mark

The roots of

ax^2+bx+c=0

are real and positive. Here $a$ , $b$ , and $c$ are real.

Then

ax^2+b|x|+c=0

has

(A)
no roots
(B)
2 real roots
(C)
3 real roots
(D)
4 real roots

Answer (official key): D

Read the worked solution

Q6 · General Aptitude · MCQ · 2 marks

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 exact reasons for the formation of this gap are not clear. It results in the neighbouring regions of Tamil Nadu getting more rainfall from the South West monsoon and the neighbouring regions of Kerala having higher summer temperatures.

What can be inferred from this passage?

(A)
The Palghat gap is caused by high rainfall and high temperatures in southern Tamil Nadu and Kerala
(B)
The regions in Tamil Nadu and Kerala that are near the Palghat Gap are low-lying
(C)
The low terrain of the Palghat Gap has a significant impact on weather patterns in neighbouring parts of Tamil Nadu and Kerala
(D)
Higher summer temperatures result in higher rainfall near the Palghat Gap area

Answer (official key): C

Read the worked solution

Q7 · General Aptitude · Numerical · 2 marks

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 are tabulated below.

Category	Men	Women
Own vehicle - Car	40	34
Own vehicle - Scooter	30	20
Own vehicle - Both	60	46
Do not own vehicle	20	50

What percent of respondents do not own a scooter?

(Answer in integer)

Answer (official key): 48

Worked solution: in your report after you take this paper.

Q8 · General Aptitude · MCQ · 2 marks

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 able to eradicate these diseases through early identification and gene therapy.

On which of the following assumptions does the statement above rely?

(A)
Strategies are now available for eliminating psychiatric illnesses
(B)
Certain psychiatric illnesses have a genetic basis
(C)
All human diseases can be traced back to genes and how they are expressed
(D)
In the future, genetics will become the only relevant field for identifying psychiatric illnesses

Answer (official key): B

Worked solution: in your report after you take this paper.

Q9 · General Aptitude · Numerical · 2 marks

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 lines?

(Answer in integer)

Answer (official key): 6

Worked solution: in your report after you take this paper.

Q10 · General Aptitude · Numerical · 2 marks

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 one-way single person fare is Rs. 100, a group of 5 tourists purchasing round-trip tickets will be charged Rs. _________.

(Answer in integer)

Answer (official key): 850

Worked solution: in your report after you take this paper.

Q11 · Theory of Computation · MCQ · 1 mark

Which one of the following is TRUE?

(A)
The language $L=\{a^n b^n \mid n\ge 0\}$ is regular.
(B)
The language $L=\{a^n \mid n \text{ is prime}\}$ is regular.
(C)
The language $L=\{w \mid w \text{ has } 3k+1 \text{ b's for some } k\in \mathbb{N},\ \Sigma=\{a,b\}\}$ is regular.
(D)
The language $L=\{ww \mid w\in\Sigma^*,\ \Sigma=\{0,1\}\}$ is regular.

Answer (official key): C

Worked solution: in your report after you take this paper.

Q12 · Algorithms · MCQ · 1 mark

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 matrix?

(A)
$\Theta(n)$
(B)
$\Theta(n+m)$
(C)
$\Theta(n^2)$
(D)
$\Theta(m^2)$

Answer (official key): C

Worked solution: in your report after you take this paper.

Q13 · Computer Networks · MCQ · 1 mark

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 overhead in link state protocols is higher than in distance vector protocols.
S2: A distance vector protocol with split horizon avoids persistent routing loops, but not a link state protocol.
S3: After a topology change, a link state protocol will converge faster than a distance vector protocol.

Which one of the following is correct about S1, S2, and S3?

(A)
S1, S2, and S3 are all true.
(B)
S1, S2, and S3 are all false.
(C)
S1 and S2 are true, but S3 is false.
(D)
S1 and S3 are true, but S2 is false.

Answer (official key): D

Worked solution: in your report after you take this paper.

Q14 · Programming and Data Structures · MCQ · 1 mark

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 statements is TRUE?

(A)
Compilation fails.
(B)
Execution results in a run-time error.
(C)
On execution, the value printed is 5 more than the address of variable i.
(D)
On execution, the value printed is 5 more than the integer value entered.

Answer (official key): D

Worked solution: in your report after you take this paper.

Q15 · Algorithms · MCQ · 1 mark

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 inputs $[1,2,3,4,5]$ and $[4,1,5,3,2]$ , respectively. Which one of the following holds?

(A)
$t_1 = 5$
(B)
$t_1 < t_2$
(C)
$t_1 > t_2$
(D)
$t_1 = t_2$

Answer (official key): C

Worked solution: in your report after you take this paper.

Q16 · Discrete Mathematics · MCQ · 1 mark

Consider the directed graph given below.

Which one of the following is TRUE?

(A)
The graph does not have any topological ordering.
(B)
Both PQRS and SRQP are topological orderings.
(C)
Both PSRQ and SPRQ are topological orderings.
(D)
PSRQ is the only topological ordering.

Answer (official key): C

Worked solution: in your report after you take this paper.

Q17 · Databases · MCQ · 1 mark

Consider the relation scheme

R=(E,F,G,H,I,J,K,L,M,N)

and the set of functional dependencies:

\{\{E,F\}\to\{G\},\ \{F\}\to\{I,J\},\ \{E,H\}\to\{K,L\},\ \{K\}\to\{M\},\ \{L\}\to\{N\}\}

on $R$ . What is the key for $R$ ?

(A)
$\{E,F\}$
(B)
$\{E,F,H\}$
(C)
$\{E,F,H,K,L\}$
(D)
$\{E\}$

Answer (official key): B

Worked solution: in your report after you take this paper.

Q18 · Operating System · Numerical · 1 mark

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, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.

Answer (official key): 3

Worked solution: in your report after you take this paper.

Q19 · Algorithms · MCQ · 1 mark

Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and $E$ is the set of edges. Then which one of the following graphs has the same strongly connected components as $G$ ?

(A)
$G_1=(V,E_1)$ where $E_1=\{(u,v)\mid (u,v)\notin E\}$
(B)
$G_2=(V,E_2)$ where $E_2=\{(u,v)\mid (v,u)\in E\}$
(C)
$G_3=(V,E_3)$ where $E_3=\{(u,v)\mid \text{there is a path of length } \le 2 \text{ from } u \text{ to } v \text{ in } E\}$
(D)
$G_4=(V_4,E)$ where $V_4$ is the set of vertices in $G$ which are not isolated

Answer (official key): B

Worked solution: in your report after you take this paper.

Q20 · Computer Organization and Architecture · Numerical · 1 mark

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 immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is ____________.

Answer (official key): 16383

Worked solution: in your report after you take this paper.

Q21 · Linear Algebra · Numerical · 1 mark

The value of the dot product of the eigenvectors corresponding to any pair of different eigenvalues of a $4 \times 4$ symmetric positive definite matrix is _____________________.

Answer (official key): 0

Worked solution: in your report after you take this paper.

Q22 · Computer Networks · MCQ · 1 mark

Identify the correct order in which the following actions take place in an interaction between a web browser and a web server.

The web browser requests a webpage using HTTP.
The web browser establishes a TCP connection with the web server.
The web server sends the requested webpage using HTTP.
The web browser resolves the domain name using DNS.

(A)
4, 2, 1, 3
(B)
1, 2, 3, 4
(C)
4, 1, 2, 3
(D)
2, 4, 1, 3

Answer (official key): A

Worked solution: in your report after you take this paper.

Q23 · Programming and Data Structures · Numerical · 1 mark

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 $O(n^a\log^b n)$ . The value of $a+10b$ is ________.

Answer (official key): 1

Worked solution: in your report after you take this paper.

Q24 · Theory of Computation · MCQ · 1 mark

Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?

(A)
$\{q_0,q_1,q_2\}$
(B)
$\{q_0,q_1\}$
(C)
$\{q_0,q_1,q_2,q_3\}$
(D)
$\{q_3\}$

Answer (official key): A

Worked solution: in your report after you take this paper.

Q25 · Discrete Mathematics · MCQ · 1 mark

Consider the statement:

“Not all that glitters is gold.”

Predicate $\mathrm{glitters}(x)$ is true if $x$ glitters and predicate $\mathrm{gold}(x)$ is true if $x$ is gold. Which one of the following logical formulae represents the above statement?

(A)
$\forall x:\ \mathrm{glitters}(x) \Rightarrow \neg \mathrm{gold}(x)$
(B)
$\forall x:\ \mathrm{gold}(x) \Rightarrow \mathrm{glitters}(x)$
(C)
$\exists x:\ \mathrm{gold}(x) \land \neg \mathrm{glitters}(x)$
(D)
$\exists x:\ \mathrm{glitters}(x) \land \neg \mathrm{gold}(x)$

Answer (official key): D

Worked solution: in your report after you take this paper.

Q26 · Probability and Statistics · Numerical · 1 mark

Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________.

Answer (official key): 0.24 to 0.27

Read the worked solution

Q27 · Databases · MCQ · 1 mark

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 form the primary key, the following is a valid table definition.

CREATE TABLE S (
  a INTEGER,
  d INTEGER,
  e INTEGER,
  PRIMARY KEY (d),
  FOREIGN KEY (a) references R
);

Which one of the following statements is CORRECT?

(A)
S1 is TRUE and S2 is FALSE.
(B)
Both S1 and S2 are TRUE.
(C)
S1 is FALSE and S2 is TRUE.
(D)
Both S1 and S2 are FALSE.

Answer (official key): D

Read the worked solution

Q28 · Programming and Data Structures · MCQ · 1 mark

Match the following:

Model	Description
1) Waterfall model	a) Specifications can be developed incrementally
2) Evolutionary model	b) Requirements compromises are inevitable
3) Component-based software engineering	c) Explicit recognition of risk
4) Spiral development	d) Inflexible partitioning of the project into stages

(A)
1-a, 2-b, 3-c, 4-d
(B)
1-d, 2-a, 3-b, 4-c
(C)
1-d, 2-b, 3-a, 4-c
(D)
1-c, 2-a, 3-b, 4-d

Answer (official key): B

Worked solution: in your report after you take this paper.

Q29 · Computer Networks · MCQ · 1 mark

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

(A)
P and R only
(B)
Q and R only
(C)
Q and S only
(D)
R and S only

Answer (official key): C

Worked solution: in your report after you take this paper.

Q30 · Calculus · MCQ · 1 mark

Let the function

f(\theta)= \begin{vmatrix} \sin\theta & \cos\theta & \tan\theta \\ \sin(\pi/6) & \cos(\pi/6) & \tan(\pi/6) \\ \sin(\pi/3) & \cos(\pi/3) & \tan(\pi/3) \end{vmatrix}

where $\theta \in [\pi/6,\pi/3]$ and $f'(\theta)$ denotes the derivative of $f$ with respect to $\theta$ .

Which of the following statements is/are TRUE?

(I) There exists $\theta\in(\pi/6,\pi/3)$ such that $f'(\theta)=0$ .
(II) There exists $\theta\in(\pi/6,\pi/3)$ such that $f'(\theta)\ne 0$ .

(A)
I only
(B)
II only
(C)
Both I and II
(D)
Neither I nor II

Answer (official key): C

Worked solution: in your report after you take this paper.

Q31 · Digital Logic · MCQ · 1 mark

Consider the following Boolean expression for $F$ :

F(P,Q,R,S)=PQ+\overline{P}QR+\overline{P}Q\overline{R}S

The minimal sum-of-products form of $F$ is

(A)
$PQ+QR+QS$
(B)
$P+Q+R+S$
(C)
$\overline{P}+\overline{Q}+\overline{R}+\overline{S}$
(D)
$\overline{P}R+\overline{P}\overline{R}S+P$

Answer (official key): A

Worked solution: in your report after you take this paper.

Q32 · Compiler Design · MCQ · 1 mark

Which one of the following is FALSE?

(A)
A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end.
(B)
Available expression analysis can be used for common subexpression elimination.
(C)
Live variable analysis can be used for dead code elimination.
(D)
$x=4*5 \Rightarrow x=20$ is an example of common subexpression elimination.

Answer (official key): D

Worked solution: in your report after you take this paper.

Q33 · Linear Algebra · Numerical · 1 mark

Consider the following system of equations:

3x + 2y = 1

4x + 7z = 1

x + y + z = 3

x - 2y + 7z = 0

The number of solutions for this system is __________________.

Answer (official key): 1

Worked solution: in your report after you take this paper.

Q34 · Operating System · MCQ · 1 mark

Which one of the following is FALSE?

(A)
User level threads are not scheduled by the kernel.
(B)
When a user level thread is blocked, all other threads of its process are blocked.
(C)
Context switching between user level threads is faster than context switching between kernel level threads.
(D)
Kernel level threads cannot share the code segment.

Answer (official key): D

Worked solution: in your report after you take this paper.

Q35 · Digital Logic · Numerical · 1 mark

The base, or radix, of the number system such that the following equation holds is __________.

\frac{312}{20}=13.1

Answer (official key): 5

Worked solution: in your report after you take this paper.

Q36 · Calculus · MCQ · 2 marks

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?

(A)
There exists a $y$ in the interval $(0,1)$ such that $f(y)=f(y+1)$ .
(B)
For every $y$ in the interval $(0,1)$ , $f(y)=f(2-y)$ .
(C)
The maximum value of the function in the interval $(0,2)$ is 1.
(D)
There exists a $y$ in the interval $(0,1)$ such that $f(y)=-f(2-y)$ .

Answer (official key): A

Worked solution: in your report after you take this paper.

Q37 · Discrete Mathematics · Numerical · 2 marks

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 possible 1-pennants is $\{(1)\}$ , the set of all possible 2-pennants is $\{(2),(1,1)\}$ , and the set of all 3-pennants is $\{(2,1),(1,1,1),(1,2)\}$ . Note that the pennant $(1,2)$ is not the same as the pennant $(2,1)$ .

The number of 10-pennants is ______________.

Answer (official key): 88.9 to 89.1

Worked solution: in your report after you take this paper.

Q38 · Operating System · Numerical · 2 marks

Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.

Process	Arrival Time	Execution Time
A	0	6
B	3	2
C	5	4
D	7	6
E	10	3

Using the shortest remaining time first scheduling algorithm, the average process turnaround time, in msec, is ____________________.

Answer (official key): 7.2

Worked solution: in your report after you take this paper.

Q39 · Algorithms · MCQ · 2 marks

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 * 3

(A)
Half of the product of the 3 consecutive integers.
(B)
One-third of the product of the 3 consecutive integers.
(C)
One-sixth of the product of the 3 consecutive integers.
(D)
None of the above.

Answer (official key): C

Worked solution: in your report after you take this paper.

Q40 · Compiler Design · MCQ · 2 marks

A canonical set of items is given below:

S \to L . > R

Q \to R .

On input symbol <, the set has

(A)
a shift-reduce conflict and a reduce-reduce conflict.
(B)
a shift-reduce conflict but not a reduce-reduce conflict.
(C)
a reduce-reduce conflict but not a shift-reduce conflict.
(D)
neither a shift-reduce nor a reduce-reduce conflict.

Answer (official key): D

Worked solution: in your report after you take this paper.

Q41 · Algorithms · MCQ · 2 marks

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 correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

(A)
(B)
(C)
(D)

Answer (official key): D

Read the worked solution

Q42 · Theory of Computation · MCQ · 2 marks

Let $L$ be a language and $\overline{L}$ be its complement. Which one of the following is NOT a viable possibility?

(A)
Neither $L$ nor $\overline{L}$ is recursively enumerable.
(B)
One of $L$ and $\overline{L}$ is recursively enumerable but not recursive; the other is not recursively enumerable.
(C)
Both $L$ and $\overline{L}$ are recursively enumerable but not recursive.
(D)
Both $L$ and $\overline{L}$ are recursive.

Answer (official key): C

Worked solution: in your report after you take this paper.

Q43 · Computer Organization and Architecture · MCQ · 2 marks

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 the same block address is bounded above by $k$ . What is the miss ratio if the access sequence is passed through a cache of associativity $A \ge k$ exercising least-recently-used replacement policy?

(A)
$n/N$
(B)
$1/N$
(C)
$1/A$
(D)
$k/n$

Answer (official key): A

Worked solution: in your report after you take this paper.

Q44 · Databases · MCQ · 2 marks

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 one of them is conflict serializable?

(A)
$r_1(x); r_2(x); w_1(x); r_3(x); w_2(x)$
(B)
$r_2(x); r_1(x); w_2(x); r_3(x); w_1(x)$
(C)
$r_3(x); r_2(x); r_1(x); w_2(x); w_1(x)$
(D)
$r_2(x); w_2(x); r_3(x); r_1(x); w_1(x)$

Answer (official key): D

Worked solution: in your report after you take this paper.

Q45 · Computer Networks · Numerical · 2 marks

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 utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.

Answer (official key): 5

Worked solution: in your report after you take this paper.

Q46 · Databases · MCQ · 2 marks

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 of functional dependencies $AB \to C,\ D \to E,\ AB \to E,\ E \to C$ .

Which one of the following is CORRECT?

(A)
S1 is TRUE and S2 is FALSE.
(B)
Both S1 and S2 are TRUE.
(C)
S1 is FALSE and S2 is TRUE.
(D)
Both S1 and S2 are FALSE.

Answer (official key): A

Worked solution: in your report after you take this paper.

Q47 · Computer Organization and Architecture · Numerical · 2 marks

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 this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is ______________________.

Answer (official key): 4

Worked solution: in your report after you take this paper.

Q48 · Discrete Mathematics · Numerical · 2 marks

Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is

\{(i,j):1\le i\le 12,\ 1\le j\le 12\}.

There is an edge between $(a,b)$ and $(c,d)$ if

|a-c|\le 1

and

|b-d|\le 1.

The number of edges in this graph is __________.

Answer (official key): 506

Worked solution: in your report after you take this paper.

Q49 · Databases · MCQ · 2 marks

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 display the last names and hire dates of all latest hires in their respective departments in the location ID 1700. You issue the following query:

SELECT last-name, hire-date
FROM employees
WHERE (dept-id, hire-date) IN
(
  SELECT dept-id, MAX(hire-date)
  FROM employees JOIN departments USING(dept-id)
  WHERE location-id = 1700
  GROUP BY dept-id
);

What is the outcome?

(A)
It executes but does not give the correct result.
(B)
It executes and gives the correct result.
(C)
It generates an error because of pairwise comparison.
(D)
It generates an error because the GROUP BY clause cannot be used with table joins in a sub-query.

Answer (official key): B

Worked solution: in your report after you take this paper.

Q50 · Discrete Mathematics · Numerical · 2 marks

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

\log_2 \log_2 N

is ______.

Answer (official key): 16

Worked solution: in your report after you take this paper.

Q51 · Programming and Data Structures · MCQ · 2 marks

Consider a hash table with 9 slots. The hash function is

h(k)=k\bmod 9.

Collisions are resolved by chaining. The following 9 keys are inserted in the order:

5, 28, 19, 15, 20, 33, 12, 17, 10.

The maximum, minimum, and average chain lengths in the hash table, respectively, are

(A)
3, 0, and 1
(B)
3, 3, and 3
(C)
4, 0, and 1
(D)
3, 0, and 2

Answer (official key): A

Worked solution: in your report after you take this paper.

Q52 · Discrete Mathematics · MCQ · 2 marks

An ordered $n$ -tuple

(d_1,d_2,\ldots,d_n)

with

d_1\ge d_2\ge \cdots \ge d_n

is called graphic if there exists a simple undirected graph with $n$ vertices having degrees

d_1,d_2,\ldots,d_n

respectively. Which of the following 6-tuples is NOT graphic?

(A)
$(1,1,1,1,1,1)$
(B)
$(2,2,2,2,2,2)$
(C)
$(3,3,3,1,0,0)$
(D)
$(3,2,1,1,1,0)$

Answer (official key): C

Worked solution: in your report after you take this paper.

Q53 · Discrete Mathematics · Numerical · 2 marks

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, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is _______.

Answer (official key): 12

Worked solution: in your report after you take this paper.

Q54 · Computer Networks · Numerical · 2 marks

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 10^8$ m/s and the token transmission time is ignored. If each station is allowed to hold the token for $2\,\mu s$ , the minimum time for which the monitoring station should wait, in $\mu s$ , before assuming that the token is lost is _______.

Answer (official key): 28 to 30

Worked solution: in your report after you take this paper.

Q55 · Computer Organization and Architecture · Numerical · 2 marks

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 time but incurs 20% more CPI (clock cycles per instruction) as compared to the program running on $P_1$ . If the clock frequency of $P_1$ is 1 GHz, then the clock frequency of $P_2$ , in GHz, is _________.

Answer (official key): 1.6

Worked solution: in your report after you take this paper.

Q56 · Calculus · Numerical · 2 marks

The function

f(x)=x\sin x

satisfies the following equation:

f''(x)+f(x)+t\cos x=0.

The value of $t$ is ______.

Answer (official key): -2

Worked solution: in your report after you take this paper.

Q57 · Operating System · Numerical · 2 marks

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 replacement policy is __________.

Answer (official key): 7

Worked solution: in your report after you take this paper.

Q58 · Probability and Statistics · Numerical · 2 marks

Four fair six-sided dice are rolled. The probability that the sum of the results is 22 is $\frac{X}{1296}$ .

The value of $X$ is __________.

Answer (official key): 10

Worked solution: in your report after you take this paper.

Q59 · Algorithms · Numerical · 2 marks

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________________.

Answer (official key): 147.1 to 148.1

Worked solution: in your report after you take this paper.

Q60 · Discrete Mathematics · MCQ · 2 marks

Which one of the following propositional logic formulas is TRUE when exactly two of $p$ , $q$ , and $r$ are TRUE?

(A)
$((p\leftrightarrow q)\land r)\lor(p\land q\land \neg r)$
(B)
$(\neg(p\leftrightarrow q)\land r)\lor(p\land q\land \neg r)$
(C)
$((p\to q)\land r)\lor(p\land q\land \neg r)$
(D)
$(\neg(p\leftrightarrow q)\land r)\land(p\land q\land \neg r)$

Answer (official key): B

Worked solution: in your report after you take this paper.

Q61 · Programming and Data Structures · MCQ · 2 marks

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 < size; i++)
      Y = Y + E[i];

  for(i = 0; i < size; i++)
      for(j = i; j < size; j++)
      {
         Z = 0;
         for(k = i; k <= j; k++)
             Z = Z + E[k];

         if (Z > Y)
             Y = Z;
      }

  return Y;
}

The value returned by the function MyX is the

(A)
maximum possible sum of elements in any sub-array of array E.
(B)
maximum element in any sub-array of array E.
(C)
sum of the maximum elements in all possible sub-arrays of array E.
(D)
sum of all the elements in the array E.

Answer (official key): A

Worked solution: in your report after you take this paper.

Q62 · Operating System · MCQ · 2 marks

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$ .

Current system state:

Process	Allocation X	Allocation Y	Allocation Z	Max X	Max Y	Max Z
P0	0	0	1	8	4	3
P1	3	2	0	6	2	0
P2	2	1	1	3	3	3

Available resources are:

X=3,\quad Y=2,\quad Z=2.

The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:

REQ1: $P0$ requests 0 units of $X$ , 0 units of $Y$ , and 2 units of $Z$ .

REQ2: $P1$ requests 2 units of $X$ , 0 units of $Y$ , and 0 units of $Z$ .

Which one of the following is TRUE?

(A)
Only REQ1 can be permitted.
(B)
Only REQ2 can be permitted.
(C)
Both REQ1 and REQ2 can be permitted.
(D)
Neither REQ1 nor REQ2 can be permitted.

Answer (official key): B

Worked solution: in your report after you take this paper.

Q63 · Theory of Computation · MCQ · 2 marks

Which of the regular expressions given below represent the following DFA?

I. $0^*1(1+00^*1)^*$

II. $0^*1^*1+11^*0^*1$

III. $(0+1)^*1$

(A)
I and II only
(B)
I and III only
(C)
II and III only
(D)
I, II, and III

Answer (official key): B

Worked solution: in your report after you take this paper.

Q64 · Digital Logic · MCQ · 2 marks

Consider the 4-to-1 multiplexer with two select lines $S_1$ and $S_0$ given below.

The minimal sum-of-products form of the Boolean expression for the output $F$ of the multiplexer is

(A)
$\overline{P}Q + Q\overline{R} + P\overline{Q}R$
(B)
$\overline{P}Q + \overline{P}Q\overline{R} + PQR + P\overline{Q}R$
(C)
$PQR + P\overline{Q}R + Q\overline{R} + P\overline{Q}R$
(D)
$PQ\overline{R}$

Answer (official key): A

Worked solution: in your report after you take this paper.

Q65 · Computer Networks · Numerical · 2 marks

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. The time taken, in msec, by the TCP connection to get back to 32 KB congestion window is _________.

Answer (official key): 1100 to 1300

Worked solution: in your report after you take this paper.

All 65 questions of GATE 2014 CS (Set 1)

Q1 · General Aptitude · Numerical · 1 mark

Q2 · General Aptitude · MCQ · 1 mark

Q3 · General Aptitude · MCQ · 1 mark

Q4 · General Aptitude · MCQ · 1 mark

Q5 · General Aptitude · MCQ · 1 mark

Q6 · General Aptitude · MCQ · 2 marks

Q7 · General Aptitude · Numerical · 2 marks

Q8 · General Aptitude · MCQ · 2 marks

Q9 · General Aptitude · Numerical · 2 marks

Q10 · General Aptitude · Numerical · 2 marks

Q11 · Theory of Computation · MCQ · 1 mark

Q12 · Algorithms · MCQ · 1 mark

Q13 · Computer Networks · MCQ · 1 mark

Q14 · Programming and Data Structures · MCQ · 1 mark

Q15 · Algorithms · MCQ · 1 mark

Q16 · Discrete Mathematics · MCQ · 1 mark

Q17 · Databases · MCQ · 1 mark

Q18 · Operating System · Numerical · 1 mark

Q19 · Algorithms · MCQ · 1 mark

Q20 · Computer Organization and Architecture · Numerical · 1 mark

Q21 · Linear Algebra · Numerical · 1 mark

Q22 · Computer Networks · MCQ · 1 mark

Q23 · Programming and Data Structures · Numerical · 1 mark

Q24 · Theory of Computation · MCQ · 1 mark

Q25 · Discrete Mathematics · MCQ · 1 mark

Q26 · Probability and Statistics · Numerical · 1 mark

Q27 · Databases · MCQ · 1 mark

Q28 · Programming and Data Structures · MCQ · 1 mark

Q29 · Computer Networks · MCQ · 1 mark

Q30 · Calculus · MCQ · 1 mark

Q31 · Digital Logic · MCQ · 1 mark

Q32 · Compiler Design · MCQ · 1 mark

Q33 · Linear Algebra · Numerical · 1 mark

Q34 · Operating System · MCQ · 1 mark

Q35 · Digital Logic · Numerical · 1 mark

Q36 · Calculus · MCQ · 2 marks

Q37 · Discrete Mathematics · Numerical · 2 marks

Q38 · Operating System · Numerical · 2 marks

Q39 · Algorithms · MCQ · 2 marks

Q40 · Compiler Design · MCQ · 2 marks

Q41 · Algorithms · MCQ · 2 marks

Q42 · Theory of Computation · MCQ · 2 marks

Q43 · Computer Organization and Architecture · MCQ · 2 marks

Q44 · Databases · MCQ · 2 marks

Q45 · Computer Networks · Numerical · 2 marks

Q46 · Databases · MCQ · 2 marks

Q47 · Computer Organization and Architecture · Numerical · 2 marks

Q48 · Discrete Mathematics · Numerical · 2 marks

Q49 · Databases · MCQ · 2 marks

Q50 · Discrete Mathematics · Numerical · 2 marks

Q51 · Programming and Data Structures · MCQ · 2 marks

Q52 · Discrete Mathematics · MCQ · 2 marks

Q53 · Discrete Mathematics · Numerical · 2 marks

Q54 · Computer Networks · Numerical · 2 marks

Q55 · Computer Organization and Architecture · Numerical · 2 marks

Q56 · Calculus · Numerical · 2 marks

Q57 · Operating System · Numerical · 2 marks

Q58 · Probability and Statistics · Numerical · 2 marks

Q59 · Algorithms · Numerical · 2 marks

Q60 · Discrete Mathematics · MCQ · 2 marks

Q61 · Programming and Data Structures · MCQ · 2 marks

Q62 · Operating System · MCQ · 2 marks

Q63 · Theory of Computation · MCQ · 2 marks

Q64 · Digital Logic · MCQ · 2 marks

Q65 · Computer Networks · Numerical · 2 marks