Computer Science And Information Technology - CS 2017 GATE Paper - 1 (Practice Test) - GATE

Explanation: 

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

Alternate Solution 

Take the prime factor of 162: 162 = 2 * 81 = 2 * 9 * 9 = 2 * 3 * 3 * 3 * 3, now if we add minimum two 2 and two 3, then it will be perfect cube of a number. Therefore, the value of y will be = 2 * 2 * 3 * 3 = 4 * 9 = 36 Note that you can multiple 162 with values in given options, then take cube root with the help of calculator for each option, the answer should be an integer.

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

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.

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 

Alternate Solution 
Case(1): When 0 can not be as left most digit: 
Then sample space = 9 * 10^{k-1} 
Favorable event = 7^{k} 
Required probability = (7^{k}) / (9 * 10^{k-1}). 
None option matches. 
Case(2): When 0 can be as left most digit: 
Then sample space = 10^{k} 
Favorable event = 7^{k} 
Required probability = (7^{k}) / (10^{k}) = (7/10)^{k} = (0.7)^{k}. 
Option (c) matches. 

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.

Let's draw what these statements say:

• 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

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.

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.

Given data - height of all villages

• P = 575
• Q = 525
• R = 475
• S = 425
• T = 500

Villages  below the flood level - 525m are

1. R <500m
2. 425m<= S<=450m
3. 500m <=T<= 525m

Therefore option C is correct.

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

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. 

The given scenario can be illustrated as:

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  q₁ = p₂ * c , q₂ = p₄ + q₃ - In these statements p₂, p₄, q₃ are not initialized anywhere
• d- code is invalid as  q₂ = p + q is incorrect without moving it to register

Therefore, option B is only correct option.

Given

V -> 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

1. V -> W
2. V -> X
3. Y -> V
4. Y -> Z

Therefore, option A is most appropriate. 

Alternate Solution

Irreducible equivalent functional dependency is minimal cover. Given,

{V → W, VW → X, Y → VX, Y → Z}

W extraneous from VW, since we have V → W,

= {V → W, V → X, Y → VX, Y → Z}

X extraneous from VX, since we have V → X,

= {V → W, V → X, Y → V, Y → Z}

Turn Around Time

P1  = 12-0 = 12
P2 = 6-3 = 3
P3 = 17-5 = 12
P4 = 8 - 6 = 2

Waiting Time

P1  = 12-7 = 5
P2 = 3-3 = 0
P3 = 12-5 = 7
P4 = 2 - 2 = 0

Average Waiting time = (7+0+5+0)/4 = 3.0 Therefore, option C is correct 

Alternate Solution

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 

The minimum height of a binary search tree will be when tree is full complete tree:

Now, let h be the height of the binary tree, then, 2^{0}+2^{1}+2^{2}+2^{3}+...+2^{h}=2^{h+1}-1 <= n 
So, Min height of a binary search tree = log₂(n+1) - 1 = log₂(15+1) - 1 = 4 - 1 = 3

The maximum height of a binary search tree will be when the tree is fully skewed: (like below)

Max height of the binary search tree = n-1 = 15 - 1 = 14, where the tree is Skewed tree

Therefore, option B 

(¬ p) => (¬ q) is logically equivalent  ¬ q + p 
I. p => q ≡  ¬ p +  q 
II. q => p ≡ ¬ q + p 
III. (¬ q) ∨ p ≡ ¬ q + p 
IV. (¬ p) ∨ q ≡ ¬ p + q 
Therefore option D, II and III only

Output of Query will be:

Thread share all other  resources of process except local data like  - register , stack.

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. 

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

Alternate Solution

To compute FOLLOW(A) for all non terminals A, apply the following rules until nothing can be added to any FOLLOW set:

• Place $ in FOLLOW(S), where S is the start symbol and $ is the input right end marker.
• If there is a production A → αBβ, then everything in FIRST(β), except for ∈, is placed in FOLLOW(B)
• If there is a production A → αB, or a production A → αBβ where FIRST(β) contains ∈ (i.e., b → ∈), then everything in FOLLOW(A) is in FOLLOW(B).

Therefore, follow(Q) = First(RS) = ( w ) ∪ First(S) = { w } ∪ { y } = { w,y }. 
Note that here, first(S) is not ∈. 

Given, Memory reference/instruction = 1.4 
So, total number of memory references = 1000 * 1.4 = 1400 
No. of  7 misses in L2 cache = 7/1400 = 0.005 
Miss rate of L2=No. of misses in L2/No. of misses in L1 =0.005/0.1 =0.05 
Therefore, option A is correct. 

Alternate Solution 

On Average, 1.4 memory accesses are required for one instruction execution. 
So, for 1000 instructions, 1400 accesses are needed. 
Number of misses occurred in cache L2 for 1000 instruction = 7/1400 = 0.005 
Miss rate of L2 cache = misses occured in L2 cache / miss rate in L1 cache 
= 0.005 / 0.1 = 0.05 (A)

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. 
Therefore, 100/n < 10< log₂n< √n< n 
It can be proven by substituting any big number in all the functions.  

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

The code will run and give output = 10, so option A and B are discarded.

int * x= malloc (sizeof(int));

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. Memory leak occurs when programmers create a memory in heap and forget to delete it. Memory leaks are particularly serious issues for programs like daemons and servers which by definition never terminate. Detailed article on Memory LeakRunning code of the question: [sourcecode language="C"] #include int *assignval (int *x, int val) { *x = val; return x; } void 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 ", *x); free(x); } [/sourcecode]

Solving the above k- map, = ca'(b+b') = ca' This can be implemented using one NOR gate. Therefore, option A is correct  

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

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

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

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

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., 
(A7 . B7)⊕(S7) = (A7 . B7 . S7‘ + A7‘ . B7‘ . S7 = 1 

Another Solution

So, it depends on S7 for overflow. when S7 is 0 while adding two negative numbers and when S7 is 1 while adding two positive numbers A7. B7. S7' + A7'. B7'.S7 = 1 

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.

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 

Alternate solution: We know that minimum spanning tree of a graph is always unique if all the weight are distinct, so statement 1 is correct. Now statement 2 , this might not be 

true in all cases. Consider the graph.

There are two shortest paths from a to b (one is direct and other via node c) So statement 2 is false Hence option a is correct.

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

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.

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

Alternate Solution 
 

• Option (A): If (p → q) → r is false, then (p → q) is true and r is false. 
  
  The possible cases are 
  (i) p is true, q is true, r is false 
  (ii) p is false, q is true, r is false 
  (iii) p is false, q is false, r is false 
  For case (iii), (r → p) → q is false . It is not a tautology . Option (A) is not true.
• Option (B): For case (i) and case (ii), (r → p) → q is true. 
  It is not a contradiction , option (B) is not true.
• Option (C): For case (iii), p is false and (r → p) → q is also false 
  option (C) is not true.
• Option (D): Only for case (i) and case (ii), q is true For both cases, (r →p) →q is true. Option (D) is true

The language generated by grammar G1 is aⁿc*bⁿ where n>=0 
The language generated by grammar G2 is bⁿc*aⁿ where n>=0 
The intersection of two languages will be c* (putting n=0 in both languages)
We know that c* is a regular language and infinite, so option b is correct. 

Alternate Solution

n 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

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

Alternate Solution

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.

Union of context free language is also context free language.
L1 = { aⁿ bⁿ c^m| m >= 0 and n >= 0 } and
L2 = { a^m bⁿcⁿ| n >= 0 and m >= 0 }
L3 = L1 ∪ L2 = { aⁿbⁿc^m∪ a^mbⁿcⁿ| n >= 0, m >= 0 } is also context free.
L1 says number of a’s should be equal to number of b’s and L2 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.
L3 = L1 ∩ L2 = { aⁿbⁿcⁿ| n >= 0 } need not be context free. 

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. 

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. 

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

When we have more than one process or one lock, then process/thread can acquire another lock to proceed further, or other process/thread can acquire lock to proceed further. 

((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. See the code for clarification :http://code.geeksforgeeks.org/hDPNVE

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. 

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 ₂31 = 5. Therefore, option D is correct.

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. 
Alternate Solution:

Alternate Solution:

Alternate solution 
Let a = number divisible by 3
b = number divisible by 5
c = number divisible by 7
n(a) = 166
n(b) = 100
n(c) = 71
n(a∩b) = number divisible by 15 = 33
n(b∩c) = number divisible by 35 = 14
n(a∩c) = number divisible by 21 = 23
n(a∩b∩c) = number divisible by 105 = 4
n(a∪b∪c) = n(a) + n(b) + n(c) - n(a∩b) - n(b∩c) - n(a∩c) + n(a∩b∩c) = 166 + 100 + 71 - 33 - 14 - 23 + 4 = 271 
 

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

Alternate Solution :
The output of query T1 will be the courses enrolled by student SA i.e CA , CB, CC
The output of query T2 will be the names of the students who enrol all the courses that are the output of query T1 (division operator) i.e CA, CB, CC
From the table we can see that SA, SC, SD, SF have enrolled all the courses so the output of T2 will have 4 rows. 
 

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

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

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

Because the presence of mixture of hydrogen and sulphide and brass is a type of thing which has a color very light and mixture is non temperature (hot and cold type of temperature) so it gets discolored.

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 total(i)=23 Therfore, option A is correct Check out the running code with comments: [sourcecode language="CPP"] #include int total(int v) { static int count = 0; while(v) { count += v&1; v >>= 1; } //This count can be used to see number of 1s returned //for every number i //printf("%d", count); return count; } void main() { static int x=0; int i=5; for(; i>0; i--) { //total gets added everytime with total number //of digits in the given number i x = x + total(i); } printf("%d ", x); } [/sourcecode] 

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