GATE-CS-2017 (Set 1)

Q.1

Find the smallest number y such that y x 162 (y multiplied by 162) is a perfect cube.

Ans .

Explanation :

162 = 3 * 3 * 3 * 3 * 2 To make it a perfect cube, we need at least 2 * 2 * 3 * 3 which is 36.

Q.2

Rahul, Murali, Srinivas and Arul are seated around a square table. Rahul is sitting to the left of Murali. Srinivas is sitting to the right of Arul. Which of the following pairs are seated opposite each other ?

Rahul and Murali

Srinivas and Arul

Srinivas and Murali

Srinivas and Rahul

Ans .

Explanation :

Assume, they are looking to the center of circular table, then the possible arrangement is:

Q.3

Research in the workplace reveals thatpeople work for many reasons _______.

money beside

beside money

money besides

besides money

Ans .

Explanation :

Grammatically, besides is an adverb or a preposition, and beside a preposition. Beside means next to. As a preposition, besides means in addition to or apart from. As an adverb,
besides means as well or furthermore. Here, we use "besides" as a preposition meaning  "in addition to". "besides money" is correct choice.

Q.4

The probability that a k-digit number does NOT contain the digits 0, 5 or 9 is

0.3^k

0.6^k

0.7^k

0.9^k

Ans .

Explanation :

For 10 digits(0 to 9) total possible cases = (10)^k 
Excluding digits 0, 5, 9, total possible cases = (7)^k with numbers 1,2,3,4,6,7,8 
Required probability = (7)^k/(10)^k= (0.7)^k 
Therefore option C is correct.

Q.5

After Rajendra Chola returned from his voyage to Indonesia, he ______ to visit the temple in Tanjavur.

was wishing

is wishing

wished

had wished

Ans .

Explanation :

According to the rule : when the main clause is in the past or past perfect tense, the subordinate clause must be in the past or past perfect tense.

Q.6

Six people are seated around a circular table. There are at least two men and two women. There are at least three right-handed persons. Every woman has a left-handed person to her immediate right. None of the women are right-handed. The number of women at the table is

Can not be determined

Ans .

Explanation :

There are atleast Two Men and Two Women.
There are atleast 3 Right Handed People
No women are Right Handed - infers there are three right handed men
Every woman has a left-handed person to her immediate right - Means women circled in red needs to have a left handed person on her right and that too a man as on right side of ?? there is a right handed man.
So,  ?? - will be a left handed man

 Therefore, option A (only 2 women) is correct.

Q.7

"The hold of the nationalist imagination on our colonial past is such that anything 
inadequately or improperly natinalist is just not history"

Which of the following statements best reflects the author's opinion?

Nationalists are highly imaginative

History is viewed through the filter of nationalism

Our colonial past never happened

Nationalism has to be both adequately and properly imagined

Ans .

Explanation :

The author is trying to say that everything related to colonial past has a hold of nationalism in people’s imagination.
It is not necessary that anything which is represented inadequately is the history. History and nationalism has a 
strong connection, but sometimes history is viewed with nationalism in mind. This is the author’s opinion.

Q.8

The expression [ (x + y) - |x - y| ] / 2 is equal to

the maximum of x and y

the minimum of x and y

None of thw above

Ans .

Explanation :

As we know that, if x > y, then |x - y| = x - y and 
if x < y then |x - y| = y - x , because value of |x - y| is always non-negative. 
Therefore,
Case 1: If x > y : (x + y) - |x - y| ] / 2 =  (x + y) - (x - y) ] / 2 = 2y / 2 = y (Minimum of x , y)
Case 2: If x < y : (x + y) - |x - y| ] / 2 = (x + y) - (y - x) ] / 2 = 2x / 2 = x (Minimum of x , y)
Therefore in both the case we get minimum of (x,y). So, option B 
Note that you can take some random values of x and y, then verify given options.

Q.9

A contour line joins locations having the same height above the mean sea level. The following is a contour plot of a geographical region. Contour lines are shown at 25 m intervals in this plot.

If in a flood, the water level rises to 525 m, which of the villages P, Q, R, S, T get submerged?

P,Q

P,Q,T

R,S,T

Q,R,S

Ans .

Explanation :

Given data - height of all villages
P = 575
Q = 525
R = 475
S = 425
T = 500
Villages  below the flood level - 525m are
R <500m
425m<= S<=450m
500m <=T<= 525m
Therefore option C is correct.

Q.10

Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislikes the colour white. Gulab and Neel like all the colours. In how many different ways can they choose the shirts so that no one has a shirt with a colour he or she dislikes?

Ans .

Explanation :

Total number of Shirts = 4 , Total candidates =4
So total combination of possibilities = 4 X 4 = 16
No.of ways  'Arun chooses red' + No.of ways Shwetha chooses white '=  2
Therefore, Answer is 16-2 = 14.

Q.11

Let X be a Gaussian random variable with mean 0 and variance σ². Let Y = max(X,0) where max(a,b) is the maximum of a and b. The median of Y is _______. Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

Here, half of the values of Y are to the left of the mean X = 0 and the remaining half of the values of Y lies to the right of the mean X = 0. hence,The median of Y = 0.

Q.12

Consider a TCP client and a TCP server running on two different machines. After completing data transfer, the TCP client calls close to terminate the connection and a FIN segment is sent to the TCP server. Server-side TCP responds by sending an ACK which is received by the client-side TCP. As per the TCP connection state diagram(RFC 793), in which state does the client side TCP connection wait for the FIN from the server-side TCP?

LAST-ACK

TIME-WAIT

FIN-WAIT-1

FIN-WAIT-2

Ans .

Explanation :

Client has sent FIN segment to the server and moves to FIN-WAIT-1, i.e. waiting for the ACK for own FIN segment. There are two possibilities here :
  1.If Client receives ACK for its FIN then client will move to FIN-WAIT-2 and will wait for matching FIN from server side. After receiving the FIN from server, client will send ACK and move to TIME-WAIT state.
  2.Client has sent FIN segment but didn’t get ACK till the time. Instead of ACK, client received FIN from server side. Client will acknowledge this FIN and move to CLOSE state. Here Client will wait for the ACK for its own FIN. After receiving ACK, client will move to TIME-WAIT state. Here we encounter First Case.
So, the solution is (D).

Q.13

A sender S sends a message m to receiver R, which is digitally signed by S with its private key. In this scenario, one or more of the following security violations can take place. (I) S can launch a birthday attack to replace m with a fraudulent message. (II) A third party attacker can launch a birthday attack to replace m with a fraudulent message. (III) R can launch a birthday attack to replace m with a fraudulent message.

(I) and (II) only

(I) only

(II) only

(II) and (III) only

Ans .

Explanation :

First let’s know what is Birthday attack : Using Birthday Attack, some fraudulent message can be generated which has same hash value and digital signature as the original message.
But this question is more about Private Key. Let’s analyse each option one by one - I. Instead of intended message, Sender can take some fraudulent message and encrypt it with
own private key and then receiver’s public key. This is POSSIBLE. II. Third party don’t have that Private Key to encrypt the message. So this is NOT possible. III. And the same
way R also don’t have that Private key to encrypt the message. So, the only possibility is - (I) S can launch a birthday attack to replace m with a fraudulent message.
Option (B) is correct.

Q.14

Consider the following intermediate program in three address code

p  = a - b
q = p * c
p = u * v
q = p + q

Which one of the following corresponds to a static single assignment from the above code
A)

p1 = a - b
q 1 = p1 * c
p1 = u * v
q1 = p1 + q1

p3 = a - b
q4 = p3 * c
p4 = u * v
q5 = p4 + q4

p 1 = a - b
q1 = p2   * c
p3 = u * v
q2 = p4 + q3

p1 = a - b
q1 = p * c
p2 = u * v
q2 = p + q

Ans .

Explanation :

According to Static Single Assignment
1. A variable cannot be used more than once in the LHS
2. A variable should be initialized atmost once.
Now looking at the given options
* a - code violates condition 1 as p1 is initialized again in this statement: p1 = u * v
* c- code is not valid as  q1 = p2 * c , q2 = p4 + q3 - In these statements p2, p4, q3 are not initialized anywhere
* d- code is invalid as  q2 = p + q is incorrect without moving it to register
Therefore,Option (B) is correct.

Q.15

The following functional dependencies hold true for the relational schema R{V, W, X, Y, Z}:

V -> W
VW -> X
Y -> VX
Y -> Z

Which of the following is irreducible equivalent for this set of functional dependencies?
Gate paper solved

Ans .

Explanation :

GivenV -> W
VW -> X
Y -> VX
Y -> Z
We need to find the minimal cover of these FDs 
Option B. W->X can  not implied by the given FDs, so incorrect 
Option C. Y->X can be implied from Y->V and V->X, hence redundant 
Option D. W->X can  not implied by the given FDs, so incorrect 
Option A. Minimal cover of dependencies that can be extracted out as
V -> W
V -> X
Y -> V
Y -> Z
Therefore, option A is most appropriate

Q.16

Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:
Gate paper solved
If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is _______ milliseconds. Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

Given, with arrival time and burst time:

Using (preemptive) shortest remaining time first algorithm, gantt chart is:

Therefore, Average waiting time = ( 5 + 0 + 7 + 0 ) / 4 = 12 / 4 = 3

Q.17

Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:
Note: The height of a tree with a single node is 0.

4 and 15 respectively

3 and 14 respectively

4 and 14 respectively

3 and 15 respectively

Ans .

Explanation :

* The minimum height of a binary search tree will be when tree is full complete tree:
So, Min height of a binary search tree = log2(n+1) - 1 = log2(15+1) - 1 = 4 - 1 = 3
* The maximum height of a binary search tree will be when the tree is fully skewed
So, Max height of the binary search tree = n-1 = 15 - 1 = 14.

Q.18

The statement (¬ p) → (¬ q) is logically equivalent to which of the statements below?
I. p → q
II. q → p
III. (¬ q) ∨ p
IV. (¬ p) ∨ q

I only

I and IV only

II only

II and III only

Ans .

Explanation :

Given, (¬ p) → (¬ q) = ¬ (¬ p) ∨ (¬ q) { since x → y = ¬ (x) ∨ y } = (¬ ¬ p) ∨ (¬ q) = (p) ∨ (¬ q) 
{Using double negation rule} = (¬ q) ∨ (p) 
(it is equivalent to statement (iii)) = (q) → (p) { since x → y = ¬ (x) ∨ y } 
(it is equivalent to statement (ii)) 
So, option (D) is correct

Q.19

Consider a database that has the relation schema EMP (EmpId, EmpName, and DeptName). An instance of the schema EMP and a SQL query on it are given below.

The output of executing the SQL query is _______. Note: This questions appeared as Numerical Answer Type.

1.2

2.3

2.6

3.1

Ans .

Explanation :

Output of Query will be:

DeptName     Number

AA             4

AB             3

AC             3

AD             2

AE             1

4 + 3 + 3 + 2 + 1 = 13 / 5 = 2.6

Q.20

Threads of a process share

global variables but not heap

heap but not global variables

neither global variables nor heap

both heap and global variables

Ans .

Explanation :

Thread share all other  resources of process except local data like  - register , stack. 
So, option (D) is correct

Q.21

Let c¹, cⁿ be scalars not all zero. Such that the following expression holds:

where a_i is column vectors in Rⁿ. Consider the set of linear equations.Ax = B, where A = [a₁.......a_n] and

Then, Set of equations has

a unique solution has x = j_n where j denotes n dimensional vector for all 1.

no solution

infinitely many solution

finitely many solution

Ans .

Explanation :

The vectors a1, a2, …, an are linearly dependent. 
For the system AX = B, 
Rank of coefficient matrix A = Rank of augmented matrix (A / B) = k (k< n) 
Hence, the system has infinitely many solutions.

Q.22

Consider the first-order logic sentence
F: ∀ x (∃ y R(x,y)). Assuming non-empty logical domains, which of the sentences below are implied by F? I. ∃y (~∀x R(x,y)) II. ∃y (∀x R(x,y)) III. ∀y (∃x R(x,y)) IV. ∼∃x (∀y R(x,y))

IV only

I and IV only

II only

II and III only

Ans .

Explanation :

Given, first order logic sentence 
F: ∀x (∃y R(x, y)) with following sentences: 
(i) ∃y (∃x R(x, y)) is true. Because we have ∀x (∃y R(x, y)) → ∃x (∃y R(x, y)) → ∃y (∃x R(x, y)). 
(ii) ∃y (∀x R(x, y)) is false. Because we have ∀x (∃y R(x, y)) ← ∃y (∀x R(x, y)). 
(iii) ∀y (∃x R(x, y)) is false. Because for ∃y can not imply ∀y.
(iv) ∼∃x (∀y ∼R(x, y)) is true. Because ∼∃x (∀y ∼R(x, y)) = ∀x (∼ ∃y ∼R(x, y)) = ∀x (∃y ∼∼R(x, y)) = ∀x (∃y R(x, y)).

Q.23

Consider the following grammar
p --> xQRS
Q --> yz|z
R --> w|∈
S -> y
Which is FOLLOW(Q)?

{R}

{w}

{w, y}

{w, ∉}

Ans .

Explanation :

Follow of Q is first of R so we get {w} 
but since R can be Null so we have to check first of S which is {y} 
so FOLLOW Q={w,y}

Q.24

Consider a two-level cache hierarchy L1 and L2 caches. An application incurs 1.4 memory accesses per instruction on average. For this application, the miss rate of L1 cache 0.1, the L2 cache experience on average. 7 misses per 1000 instructions. The miss rate of L2 expressed correct to two decimal places is ______________.
Note: This questions appeared as Numerical Answer Type.

0.05

0.06

0.07

0.08

Ans .

Explanation :

Miss rate of L2 cache = (memory references generated by L2 cache) / (memory references generated by L1 cache) = 7 / 140 = 0.05

Q.25

Consider the following functions from positives integers to real numbers 10, √n, n, log₂n, 100/n. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

log₂n, 100/n, 10, √n, n

100/n, 10, log₂n, √n, n

10, 100/n ,√n, log₂n, n

100/n, log₂n, 10 ,√n, n

Ans .

Explanation :

For the large number, value of inverse of number is less than a constant and value of constant is less than value of square root. 10 is constant, not affected by value of n. 
√n Square root and log₂n is logarithmic. So log₂n is definitely less than √n. n has linear growth and 100/n grows inversely with value of n. For bigger value of n, 
we can consider it 0, so 100/n is least and n is max. So the increasing order of asymptotic complexity will be :

100/n < 10 < log₂n < √n < n

Q.26

Consider the C struct defines below:

struct data { 
    int marks [100] ; 
    char grade; 
    int cnumber; 
};
 
struct data student;

The base address of student is available in register R1. The field student.grade can be accessed efficiently using

Post-increment addressing mode. (R1)+

Pre-decrement addressing mode, -(R1)

Index addressing mode, X(R1), where X is an offset represented in 2’s complement 16-bit representation.

Ans .

Explanation :

The address of student grade can only be accessed by using the base address of Student.
* Post-increment addressing mode. (R1)+ - Will give the next address and not the desired grade address
* Pre-decrement addressing mode, -(R1) - Will give the previous address and not the desired grade address
* Register direct addressing mode, R1 : In this mode, the address of the operand is embedded in the instruction code.
* Index addressing mode: It is the only mode which gives access to next address by adding displacement in base address using displacement mode.
* Base register contains a pointer to a memory location. An integer (constant) is also referred to as a displacement. 
* The address of the operand is obtained by adding the contents of the base register plus the constant.
Therefore, option D is correct

Q.27

Consider the following C code:

#include 

int * assignval (int *x, int val)
{
    *x = val;
    return x;
}

int main()
{
    int *x = malloc(sizeof(int));
    if (NULL == x) return;
    x = assignval(x, 0);
    if(x)
    {
        x = (int*) malloc(sizeof (int));
        if (NULL == x) return;
        x = assignval (x, 10);
    }
    printf("%d\n", *x);
    free(x);
}

The code suffers from which one of the following problems:

compiler error as the return of malloc is not typecast appropriately.

compiler error because the comparison should be made as x==NULL and not as shown.

compiles successfully but execution may result in dangling pointer.

compiles successfully but execution may result in memory leak.

Ans .

Explanation :

This statement assigns a location to x. 
Now,
(int*)malloc(sizeof(int));
again assigns a new location to x , previous memory location is lost because now we have no reference to that location resulting in memory leak.
Therefore, option D is correct

Q.28

Consider the Karnaugh map given below, where X represents “ don’t care” and blank represents 0.

Assume for all inputs (a,c,d) the respective complements (a', b', c', d')are also available. The above logic is implemented 2-input NOR gates only. The minimum number of gates required is ____________. Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

Solving the above k- map = ca = ac = (a' + c')' Since complement of variables are also available. So, this can be implemented using one NOR gate. Therefore, option A is correct

Q.29

Consider the following table
Gate paper solved
Match the algorithm to design paradigms they are based on:

P-(ii), Q-(iii), R-(i)

P-(iii), Q-(i), R-(ii)

P-(ii), Q-(i), R-(iii)

P-(i), Q-(ii), R-(iii)

Ans .

Explanation :

Kruskal’s  is a greedy technique of Minimum Spanning Tree Algorithm to find an edge of the least possible weight that connects any two trees in the forest.
QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.
Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph.

Q.30

Consider the C code fragment given below.

typedef struct node
{
    int data;
    node* next ;
} node;

void join(node* m, node* n)
{
    node* p = n;
    while (p->next != NULL)
    {
        p = p->next;
    }
    p–>next = m;
}

Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will

append list m to the end of list n for all inputs

either cause a null pointer dereference or append list m to the end of list n

cause a null pointer dereference for all inputs.

append list n to the end of list m for all inputs.

Ans .

Explanation :

As it is stated in the question, that m and n are valid Lists but not explicitly specified if the lists are empty or not. We can have two cases:
 1. Case 1: If lists are not NULL : Invocation of join will append list m to the end of list n if the lists are not NULL. For Example:Before join operation : m =1->2->3->4->5->null n =6->7->8->9->nullAfter join operation : 6->7->8->9->1->2->3->4->5->null
 2. Case 2: If lists are NULL : If the list n is empty and itself NULL, then joining and referencing would obviously create NULL pointer issue.
Therefore option B is correct

Q.31

Consider the language L given by the regular expression (a + b) *b(a +b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ______.

Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :






NFA to DFA Conversion: 
In the STT below you can see 4 states are there but before confirming the ans lets try to minimize, It cant be minimized further because A goes to Nonfinal & AB 
goes to Final hence can not be merged. Similarly *AC goes NF & *ABC goes to F hence can not be merged.
Hence 4 is the final ans.

Q.32

The n-bit fixed-point representation of an unsigned real number X uses f bits for the fraction part. Let i = n - f. The range of decimal values for X in this representation is

2^-f

2^-f to 2ⁱ - 2^-f

0 to 2^-i

0 to 2ⁱ - 2^-f

Ans .

Explanation :

Since given number is in unsigned bit representation, its decimal value starts with 0. 
We have i bit in integral part so maximum value will be 2ⁱ 
Thus integral value will be from 0 to 2ⁱ - 1
We know fraction part of binary representation are calculated as (1/0)*2^-f 
Thus with f bit maximum number possible = sum of GP series with a = 1/2 and r = 1/2
Thus fmax = {1/2(1 – (1/2)^f}/(1 – 1/2)
                = 1 – 2^-f
Thus maximum fractional value possible = 2ⁱ – 1 + (1 – 2^-f )
                                       = 2ⁱ - 2^-f

Q.33

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _____. Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

Given, v= Total vertices = 10 e = v - 1 =9 Degree = 2 * e = 18 Therefore, option A is correct

Q.34

Consider the following context-free grammar over the alphabet ∑ = {a, b, c} with S as the start symbol:
S → abScT | abcT
T → bT | b
Which of the following represents the language generated by the above grammar?

{(ab)ⁿ(cb)ⁿ | n >= 1 }

{(abⁿcb^m₁cb^m₂...cb^m_n | n, m₁, m₂, ....., m_n >= 1 }

{(ab)ⁿ(cb^m)ⁿ | n >= 1 }

{(ab)ⁿ(cbⁿ)^m | m, n >= 1 }

Ans .

Explanation :

Let’s generate a string from given grammar : 
S → abScT 
  → ab abScT cT 
  → abab abcT cTcT 
  → abababc bT cTcT 
  → abababcb bT cTcT
  → abababcbb bT cTcT 
  → abababcbbbb cTcT 
  → abababcbbbbc b cT 
  → abababcbbbbcbc bT 
  → abababcbbbbcbcbb. 
This string can rule out all wrong options. Now let’s try to analyse this string.
abababcbbbbcbcbb → {(abⁿcb^m₁cb^m₂...cb^m_n | n, m₁, m₂, ....., m_n >= 1 } We can clearly rule out option (A), (C) and (D) with help of the string generated by given grammar. 
Only option (B) is correct.

Q.35

When two 8-bit numbers A₇ ... A₀ and B₇ ... B₀ in 2's complement representation (with A₀ and B₀ as the least significant bits) are added using ripple-carry adder. the sum bits obtained are S₇ ... S₀ and the carry bits are C₇ ... C₀. An overflow is said to have occured if

the carry bit C₇ is 1

all the carry bits (C₇, ... , C₀ ) are 1

(A₇ . B₇ . S₇' + A₇' . B₇' . S₇) is 1

(A₀ . B₀ . S₀' + A₀' . B₀' . S₀) is 1

Ans .

Explanation :

Overflow indicates that the result was too large or too small to fit in the original data type.
Overflow flag indicates an overflow condition for a signed operation. Signed numbers are represented in two's complement representation. 
The overflow occurs only when two positive number are added and the result is negative or two negative number are added and the result is positive. Otherwise, the sum has not overflowed.
Therefore, a XOR operation can quickly determine if an overflow condition exists. i.e., 
(A₇ . B₇ )⊕(S₇) = (A₇ . B₇ . S₇‘ + A₇‘ . B₇‘ . S₇ = 1

Q.36

Consider a database that has the relation schemas EMP (EmpId, EmpName, DepId), and DEPT(DeptName, DeptId). Note that the DepId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.
I. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∀ v ∈ DEPT (t[DeptId] ≠ DeptId]))}
II. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] ≠ DeptId]))}
III. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] = DeptId]))}

I and II only

I and III only

II and III only

I, II, and III

Ans .

Explanation :

A SAFE EXPRESSION is one that is guaranteed to yield a finite number of tuples as its results. Otherwise, it is called UNSAFE Given, DepId can be permitted to be NULL 

I. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∀ v ∈ DEPT (t[DeptId] ≠ DeptId]))} : Gives empnames who donot belong to any department 
II. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] ≠ DeptId]))} : Gives empnames who donot belong to some department 
III. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] = DeptId]))}: Gives empnames who donot belong to same department 
All of these queries are giving some results which are finite and thus all are safe expressions. 

Therefore, option D is correct.

Q.37

Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive any distinct. Consider the following statements:
I. Minimum Spanning Tree of G is always unique.
II. Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?

I only

II only

both I and II

neither I and II

Ans .

Explanation :

I. Minimum Spanning Tree of G is always unique - MST will wlways be distinct if the edges are unique so Correct 
II. Shortest path between any two vertices of G is 
always unique - Shortest path between any two vertices can be same so incorrect. 

Therefore, option A is correct.

Q.38

Consider the expression (a-1) * ((( b + c ) / 3 )) + d)). Let X be the minimum number of registers required by an optimal code generation (without any register spill) algorithm for a load/store architecture, in which (i) only load and store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands The value of X is ________.

Note : This questions appeared as Numerical Answer Type.

Ans .

Explanation :

The assembly code using the load/store architecture can be written as follows:

Load R1, b

Load R2, c

ADD R1, R2

Div R1, 3

Load R2, d

Add R1, R2

Load R2, a

Sub R2, 1

Mul R2, R1

Hence minimum 2 registers required.

Q.39

Consider the C functions foo and bar given below:

int foo(int val)
{
    int x = 0;
    while (val > 0)
    {
        x = x + foo(val--);
    }
    return val;
}

int bar(int val)
{
    int x = 0;
    while (val > 0)
    {
        x = x + bar(val-1);
    }
    return val;
}

Invocations of foo(3) and bar(3) will result in:

Return of 6 and 6 respectively

Infinite loop and abnormal termination respectively

Abnomal termination and infinite loop respectively

Both terminating abnormally

Ans .

Explanation :

In the function foo every time in the while foo is called with the value 3 because val is passed with post decrement operator so the value 3 is passed and val is decremented
later. Every time the function is called a new variable is created as the passed variable is passed by value, with the value 3. So the function will close abruptly without 
returning any value. In the function bar, in the while loop value the value of val variable is not decrementing, it remains 3 only. Bar function in the while loop is called
with val-1 i.e 2 but value of val is not decremented, so it will result in infinite loop.

Q.40

Let p, q, and r be the propositions and the expression (p -> q) -> r be a contradiction. Then, the expression (r -> p)-> q is

a tautology

a contradiction

always TRUE when p is FALSE

always TRUE when q is TRUE

Ans .

Explanation :

The expression (r → p) → q is always true when q is true, regardless of the value of the expression (p → q) → r.

Q.41

Consider a RISC machine where each instruction is exactly 4 bytes long. Conditional and unconditional branch instructions use PC- relative addressing mode with Offset specified in bytes to the target location of the branch instruction. Further the Offset is always with respect to the address of the next instruction in the program sequence. Consider the following instruction sequence Gate paper solved
If the target of the branch instruction is i, then the decimal value of the Offest is __________.
Note: This questions appeared as Numerical Answer Type.

-16

-18

Ans .

Explanation :

Instruction 	        Bytes
i			0-3
i+1			4-7
i+2			8-11
i+3			12-15
Next Instruction	16

According to PC Relative Mode,

Effective PC address = next instruction address + offset 
           0(i)      =  16  + offset
	   0-16      =	offset
Offset = -16

Q.42

Consider the following grammar over the alphabet {a,b,c} given below, S and T are non-terminals.

G1: S-->aSb|T
T--> cT|∈

G2: S-->bSa|T
T--> cT|∈

The language L1(G1) ∩ L2(G2).

Finite

Non-finite but regular

Context-free but not regular

Recursive but not context-free

Ans .

Explanation :

Q.43

If G is grammar with productions
S → SaS | aSb | bSa | SS | ∈
where S is the start variable, then which one of the following is not generated by G?

abab

aaab

abbaa

babba

Ans .

Explanation :

If we notice the productions of this grammar

S->aSb | bSa | SS | ∈

these productions will always produce number of a's and b's equal.

Also , S-> SaS this production may add more number of a's to  number of a's and b's produced by the productions above.

So all, in all this grammar is generating Number of a's = Number of b's or Number of a's are greater than number of b's 

If we check option (d), it has more number of b's than a which surely cannot in no way be generated by this grammar.

Q.44

In a RSA cryptosystem a particular A uses two prime numbers p = 13 and q =17 to generate her public and private keys. If the public key of Ais 35. Then the private key of A is ____________.
Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

In an RSA cryptosystem, for public key: 
GCD( ϕ(n) , e) = 1 

And, for private key:
(e * d) mod ϕ(n) = 1 

Where, 
ϕ(n) = (p -1)*(q - 1) = (13 - 1)(17 - 1) =12*16 = 192 
Such that 1 < e, d < ϕ(n)

Therefore, the private key is:
(35 * d) mod ϕ(n) = 1
d = 11

Q.45

Let A be m×n real valued square symmetric matrix of rank 2 with expression given below. Gate paper solved
Consider the following statements

(i)  One eigenvalue must be in [-5, 5].
(ii) The eigenvalue with the largest magnitude 
     must be strictly greater than 5.

Which of the above statements about engenvalues of A is/are necessarily CORRECT?

Both (i) and (ii)

(i) only

(ii) only

Neither (i) nor (ii)

Ans .

Explanation :

Q.46

In a database system, unique time stamps are assigned to each transaction using Lamport’s logical clock. Let TS(T1) and TS(T2) be the time stamps of transactions T1 and T2 respectively. Besides, T1 holds a lock on the resource R, and T2 has requested a conflicting lock on the same resource R. The following algorithm is used to prevent deadlocks in the database assuming that a killed transaction is restarted with the same timestamp.

if  TS(T2) < TS(T1) then
      T1 is killed
else T2  waits.

Assume any transactions that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?

The database system is both deadlock-free and starvation- free.

The database system is deadlock- free, but not starvation-free.

The database system is starvation-free but not deadlock- free.

The database system is neither deadlock- free nor starvation-free.

Ans .

Explanation :

Given, if TS(T2) < TS(T1) then T1 is killed else T2 waits.
 *	T1 holds a lock on the resource R
 *	T2 has requested a conflicting lock on the same resource R
 
According to algo, TS(T2) < TS(T1) then T1 is killed else T2 will wait. So in both cases neither deadlock will happen nor starvation. Therefore, option A is correct

Q.47

The values of parameters for the Stop-and – Wait ARQ protocol are as given below.

Bit rate of the transmission channel = 1Mbps

Propagation delay from sender to receiver = 0.75 ms
 
Time to process a frame = 0.25ms
 
Number of bytes in the information frame = 1980
   
Number of bytes in the acknowledge frame = 20
 
Number of overhead bytes in the information frame = 20

Assume that there are no transmission errors. Then the transmission efficiency ( expressed in percentage) of the Stop-and – Wait ARQ protocol for the above parameters is _________( correct to 2 decimal place) .
Note: This questions appeared as Numerical Answer Type.

A number between 86.5 and 87.5

A number between 82.4 and 82.5

A number between 92.4 and 95.5

A number between 96.4 and 97.5

Ans .

Explanation :

Given, Number of bytes in the information frame = 1980 
       Number of bytes in the acknowledge frame = 20
       Number of overhead bytes in the information frame = 20
Therefore, useful Data = Total Data – Overhead 
                       = 1980 - 20 = 1960 Tt(Data)
                       = (1960*8) / 10^6 = 15.68 millisecond Tt(ACK) 
                       = 20*8 / 10^6 = 0.16 millisecond 
Two way round trip time = 2 * Tp = 2*0.75 
                        = 1.5 millisecond 
T(precess) = 0.25(for info) + 0.25(for ack) 
           = 0.5 millisecond Efficiency  
           = Useful Time / (Tt(info) + + Tt(ACK) + 2* Tp + Tprocess )  
           = 15.68 / (15.84 + 0.16 + 2*0.75+ 0.5 ) 
           = 0.8711111 
           = 87% 
  Option (A) is correct.

Q.48

The value of the given expression Gate paper solved

-1

Does not exist

Ans .

Explanation :

Q.49

Consider the following two functions

void fun1(int n){ 

     if(n == 0) return; 
     printf(“%d”, n); 
     fun2(n-2);
     printf(“%d”, n);  
}

void fun2(int n){ 

     if(n == 0) return; 
     printf(“%d”, n); 
     fun1(++n);
     printf(“%d”, n);  
}

The output printed when fun1 (5) is called is

53423122233445

53423120112233

53423122132435

53423120213243

Ans .

Explanation :

Q.50

Consider a 2-way set associative cache with 256 blocks and uses LRU replacement, Initially the cache is empty. Conflict misses are those misses which occur due the contention of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The following sequence of accesses to memory blocks

(0,128,256,128,0,128,256,128,1,129,257,129,1,129,257,129)

is repeated 10 times. The number of conflict misses experienced by the cache is ___________.
Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

In first iteration there are 4 conflict misses and 6 compulsory misses.

In second iteration, there are 4+4 = 8 conflict misses and this is the same for iterations 3..10. So, totally 8×9+4=76 conflict misses.

Q.51

A computer network uses polynomial over GF(2) for error checking with 8 bits as information bits and uses x³ + x + 1 as the generator polynomial to generate the check bits. In this network, the message 01011011 is transmitted as

01011011010

01011011011

01011011101

01011011100

Ans .

Explanation :

We add (n-1) 0's to the LSB of dividend(message) and divided by given GF

The remainder will be CRC, it will be added to the LSB of the original message, that should be transmitted to the receiver. That is: 01011011101.

Q.52

Consider the following languages over the alphabet ∑= {a,b,c}. Let L₁ = {aⁿ bⁿc^m | m, n >= 0 } and L₂ = {a^mbⁿcⁿ| m, n >= 0}. Which of the following are context-free languages ?
I. L1 ∪ L2
II. L1 ∩ L2

I only

II only

I and II

Neither I nor II

Ans .

Explanation :

Union of context free language is also context free language.
L₁ = {aⁿ bⁿc^m | m, n >= 0 } and
L₂ = {a^mbⁿcⁿ| m, n >= 0}
L₃ = L₁ ∪ L₂ = { aⁿ bⁿc^m ∪ a^mbⁿcⁿ| n >= 0, m >= 0 } is also context free.
L₁ says number of a’s should be equal to number of b’s and L₂ says number of b’s should be equal to number of c’s. Their union says either of two conditions to be true. So it is also context free language.
Intersection of CFG may or may not be CFG.
L₃ = L₁ ∩ L₂ = { aⁿ bⁿcⁿ| n >= 0 } need not be context free.

Q.53

Consider the following grammar:

stmt  -> if expr then else expr; stmt | ε
expr -> term relop term | term
term -> id | number
id ->  a | b | c
number -> [0-9]

where relop is a relational operate (e.g < >, ….), ε refers to the empty statement, and if ,then, else are terminals. Consider a program P following the above grammar containing ten if terminals. The number of control flows paths in P is ____________. For example, the program

 if e1 then e2 else e3

has 2 control flow paths, e1 -> e2 and e1 -> e3

1024

2048

Ans .

Explanation :

Number of control flow paths for 10 if terminals
if then else ; stmt
if then else ; if then else ; stmt
..............
10 times. Observe that there is a semi-colon after every if structure. Since, every if structure has 2 control flows. Therefore, 1st terminal has 2 control flows, 2nd terminal has 2 control flows,
3rd terminal has 2 control flows, ........... 9th terminal has 2 control flows, and 10th terminal has 2 control flows. Using multiplication law of counting, we get = 2*2*2*2*2......10 times = 2^10 = 1024
number of control flow paths for 10 if terminals. 1024 is correct answer.

Q.54

A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

x = 1, y = 2

x = 2, y = 1

x = 2, y = 2

x = 1, y = 1

Ans .

Explanation :

1)Reentrant (Recursive) locks allow a thread to reacquire the lock. That means same process can claim the lock multiple times without blocking on itself. 
  This prevents the thread from deadlocking itself. This is main advantage of reentrant locks over non-reentrant locks. 

2)Non-reentrant (Non- recursive) locks not allow a thread to reacquire the lock. That means same process can not claim the lock multiple times without releasing it. 
  So, if a thread/process is unable to acquire a lock, it blocks until the lock becomes available. This situation is deadlocked. 

3)Therefore, only one thread and only one lock can cause deadlock, if thread does try to reacquire lock.

Q.55

Consider the following C program.

 #include 
#include 

void printlength (char *s, char *t)
{ 
  unsigned int c = 0;
  int len = ((strlen (s) - strlen (t)) > c) ? strlen (s) : strlen (t);
  printf("%d\n", len);
}

void main()
{ 
  char *x = "abc";
  char *y = "defgh";
  printlength(x, y);
}

Recall that strlen is defined in string.h as returning a value of type size_t, which is an unsigned int . The output of the program is _________. Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

((strlen(s) - strlen(t)) > c) ? strlen (s) : strlen (t) = (3 - 5 > 0) = (-2 > 0) Important point here is while comparing -2 with c,  result will be a positive number as c
is unsigned. So, out of these two , strlen (s) will be printed. 
Therefore, option B is correct.

Q.56

A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as direct mapped cache, the length of the TAG field is 10 bits. If the cache unit is now designed as a 16-way set-associative cache, the length of the TAG field is ______ bits.
Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

Type of mapping is direct map; for this direct map, 10 bits are required in itss Tag. 
It is updated to 16 way set Associative map then new tag field size = 10 + log₂16 = 14 bits, because for k way set associative map design, log₂k bits are additionally
required to the number of bits in tag field for Direct map design.

Q.57

Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is________. Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

The best way to solve such a problem is by using Binary Search. Search the sorted array by repeatedly dividing the search interval in half. Begin with an interval covering 
the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper 
half. Find mid element
-Is mid = 1 ?
-Is mid >1?(not possible here)
-Is mid < 1 ?
Proceed accordingly, Worst case of this problem will be 1 at the end of the array i.e 00000.....1 OR 1.......0000. It will take log n time worst case. n=31, Hence log 231 = 5.
Therefore, option D is correct.

Q.58

The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is ______. Note: This questions appeared as Numerical Answer Type.

269

270

271

272

Ans .

Explanation :

The general formula for the union of 3 sets is: 
(A union B union C) = A + B + C - (A intersect B) - (A intersect C) - (B intersect C) + (A intersect B intersect C).
Assuming, 
A = 3, B = 5, C = 7 
= 500/3 + 500/5 + 500/7 - 500/3*5 - 500/5*7 - 500/7*3 + 500/105 
= 271 
Therefore, option C is correct.

Q.59

Consider a database that has the relation schema CR(StudentName, CourseName). An instance of the schema CR is as given below.
Gate paper solved
The following query is made on the database. T1 ← πCourseName(σStudentName=’SA’(CR)) T2 ← CR ÷ T1 The number of rows in T2 is ________. Note: This questions appeared as Numerical Answer Type.

Ans .

Explanation :

Result of T1: CA CB CC 
Result of T2 = CR/T1 SA SC SD SF 
Total = 4 
Therefore, option C is correct

Q.60

Consider a combination of T and D flip-flops connected as shown below. The output of the D flipflop is connected to the input of the T flip-flop and the output of the T flip-flop is connected to the input of the D flip-flop.

Gate paper solved
Initially, both Q₀ and Q₁ are set to 1 (before the 1st clock cycle). The outputs

Q₁ Q₀ after the 3rd cycle are 11 and after the 4th cycle are 00 respectively

Q₁ Q₀ after the 3rd cycle are 11 and after the 4th cycle are 01 respectively

Q₁ Q₀ after the 3rd cycle are 00 and after the 4th cycle are 11 respectively

Q₁ Q₀ after the 3rd cycle are 01 and after the 4th cycle are 01 respectively

Ans .

Explanation :


It can be observed from the diagram that : Q1 Q0 after the 3rd cycle are 11 and after the 4th cycle are 01 
Therefore, option B is correct

Q.61

Let u and v be two vectors in R2 whose Euclidean norms satisfy |u| = 2|v|. What is the value α such that w = u + αv bisects the angle between u and v ?

1/2

-1/2

Ans .

Explanation :

|u| = 2|v| =|2v|. So u and 2v are vectors of the same length in directions of u and v, so their sum u+2v bisects the angle. 
w = u + αv = u + 2 v 
That is α = 2 
Because, If we have two vectors with equal magnitude in the direction of given vectors, then their sum will bisect the angle between them.

Q.62

Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total functional from A* to B* .We say f is computable if there exists a Turning machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denotes the language {x#f(x)|x∈A*}. Which of the following statements is true?

f if computable if and only if Lf is recursive.

f if computable if and only if Lf is recursive enumerable.

if f is computable then Lf is recursive, but not conversely.

if f is computable then Lf is recursively enumerable, but not conversely.

Ans .

Explanation :

This definition is given as Halting of Turing Machine. Every recursive language is computable, but converse may not be true.

Q.63

Recall that Belady’s anomaly is that the pages-fault rate may increase as the number of allocated frames increases. Now consider the following statements:

S1: Random page replacement algorithm (where
    a page chosen at random is replaced) 
    suffers from Belady’s anomaly.

S2: LRU page replacement algorithm suffers
    from Belady’s anomaly .

Which of the following is CORRECT?

S1 is true, S2 is true

S1 is true, S2 is false

S1 is false , S2 is true

S1 is false, S2 is false

Ans .

Explanation :

Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm. For example, if we consider reference string 3 2 1 0 3 2 4 3 2 1 0 4 and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10 page faults. 

S1: Random page replacement algorithm (where a page chosen at random is replaced) suffers from Belady’s anomaly. -> Random page replacement algorithm can be any including FIFO so its true 

S2: LRU page replacement algorithm suffers from Belady’s anomaly . -> LRU does'nt suffer from Belady’s anomaly . 

Therefore, option B is correct

Q.64

The output of executing the following C program is ________.

# include 

int total(int v) 
{ 
   static int count = 0; 
   while (v) { 
     count += v & 1; 
     v >>= 1; 
   } 
   return count; 
} 

void main() 
{ 
   static int x = 0; 
   int i = 5; 
   for (; i> 0; i--) { 
       x = x + total(i); 
   } 
   printf (“%d\n”, x) ; 
}

Ans .

Explanation :

Digits : 5-0101, 4-0100, 3-0011, 2-0010, 1-0000 
Countof 1s : 2, 3, 5, 6, 7 
Total: 2+3+5+6+7 = 23  
Therfore, option A is correct

Q.65

Instruction execution in a processor is divided into 5 stages. Instruction Fetch(IF), Instruction Decode (ID), Operand Fetch(OF), Execute(EX), and Write Back(WB), These stages take 5,4,20, 10 and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns. Two pipelined implementations of the processor are contemplated:
(i) a naïve pipeline implementation (NP) with 5 stages and
(ii) an efficient pipeline (EP) where the OF stage id divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively.

The speedup (correct to two decimals places) achieved by EP over NP in executing 20 independent instructions with no hazards is ________________.
Note: This questions appeared as Numerical Answer Type.

1.50-1.51

1.51-1.52

1.52-1.53

1.53-1.54

Ans .

Explanation :

Given, total number of instructions (n) = 20 
For naive pipeline (NP):
Number of stages(k) = 5
Clock time (Tp) = max { (stage delay+buffer delay) } = { 7, 6, 22, 12, 5 } = 22 nsec
Execution time (Enp) = ( k + n - 1 )*Tp = ( 5 + 20 - 1 )*22 = 528 nsec

For efficient pipeline (EP):
number of stages(k) = 6 ( delay with 20 nsec stage is divided into 12 nsec and 8 nsec )
Clock time (Tp) = max { (stage delay+buffer delay) } = { 7, 6, 14, 10, 14, 5 } = 14 nsec
Execution time (Eep) =  ( k + n - 1 )*Tp = ( 6 + 20 - 1 )*14 = 350 nsec

Therefore, Speedup = (Enp) / (Eep) = 528 / 350 = 1.508

upscfever.com

Journey of a Thousand Miles begins with One Click!!!

GATE-CS-2017 (Set 1)

UPSCFEVER - POPULAR PAGES

Join The Movement

Discussions and Comments