GATE-CS-2015 (Set 3)

Q.1

If ROAD is written as URDG, then SWAN should be written as:

VXDQ

VZDQ

VZDP

UXDQ

Ans .

Explanation :
In ROAD to URDG transformation, every character is replaced by next third character in alphabetic sequence. (R by U, O by R, A by D and D by G) Applying same, SWAN becomes VZDQ

Q.2

The Tamil version of ________ John Abraham-starrer Madras Cafe _____ cleared by the Censor Board with no cuts last week, but the film’s distributors ______ no takers among the exhibitors for a release in Tamil Nadu _________ this Friday.

Mr., was, found, on

a, was, found, at

the, was, found, on

a, being, find at

Ans .

Explanation :
Refer use of the here.

Q.3

Extreme focus on syllabus and studying for tests has become such a dominant concern of Indian students that they close their minds to anything ________ to the requirements of the exam

extraneous

outside

useful

Ans .

Explanation :
Refer http://dictionary.reference.com/browse/extraneous

Q. 4

Select the pair that best expresses a relationship similar to that expressed in the pair: Children : Pediatrician

Adult : Orthopaedist

Females : Gynaecologist

Kidney : Nephrologist

Skin : Dermatologist

Ans .

Explanation :
Pediatrician is a doctor for children. Gynaecologist is a doctor for Females.

Q.5 A function f(x) is linear and has a value of 29 at x =2 and 39 at x = 3. Find its value at x = 5.

Ans .

Explanation :
f(x) = 2x+33

Q.6

Alexander turned his attention towards India, since he had conquered Persia. Which one of the statements below is logically valid and can be inferred from the above sentence?

Alexander would not have turned his attention towards India had he not conquered Persia

Alexander was not ready to rest on his laurels, and wanted to march to India

Alexander was completely in control of his army and could command it to move towards India.

Since Alexander's kingdom extended to India borders after the conquest of Persia, he was keen to move further

Ans .

Explanation :
Conquering Persia was the reason for Alexander turning his attention towards India

Q. 7

The head of a newly formed government desires to appoint five of the six selected members P, Q, R, S, T and U to portfolios of Home, Power, Defence, Telecom, and Finance. U does not want any portfolio if S gets one of the five. R wants either Home or Finance or no portfolio. Q says that if S gets either Power of telecom, then she must get the other one. T insists on a portfolio if P gets one Which is the valid distribution of portfolios?

P-Home, Q-Power, R-Defence, S-Telecom, T-Finance

R-Home, S-Power, P-Defence, Q-Telecom, T-Finance

P-Home, Q-Power, T-Defence, S-Telecom, U-Finance

Q-Home, U-Power, T-Defence, R-Telecom, P-Finance

Ans .

Explanation :
Six selected members are P, Q, R, S, T and U Portfolios are Home, Power, Defence, Telecom, and Finance. U does not want any portfolio if S gets one of the five. R wants either Home or Finance or no portfolio. Q says that if S gets either Power of telecom, then she must get the other one. T insists on a portfolio if P gets one Which is the valid distribution of portfolios? A) P-Home, Q-Power, R-Defence, S-Telecom, T-Finance Not valid as R doesn't get home or finance here R-Home, S-Power, P-Defence, Q-Telecom, T-Finance Is valid and satisfies all conditions. C) P-Home, Q-Power, T-Defence, S-Telecom, U-Finance Not valid as U is not satisfied. Condition for U is, S should not get any portfolio. D) Q-Home, U-Power, T-Defence, R-Telecom, P-Finance Like A, not valid as R doesn't get home or finance here

Q. 8

Choose the most appropriate equation for the function drawn as a thick line, in the plot below.

Ans .

Explanation :
3rd course of action is not correct. Banning water supply can not solve the problem.

Q. 9 Most experts feel that in spite of possessing all the technical skills required to be a batsman of the highest order, he is unlikely to be so due to lack of requisite temperament. He was guilty of throwing away his wicket several times after working hard to lay a strong foundation. His critics pointed out that until he addressed this problem, success at the highest level will continue to elude him. Which of the statements(s) below is/are logically valid and can be inferred from the above passage? (i) He was already a successful batsman at the highest level. (ii) He has to improve his temperament in order to become a great batsman. (iii) He failed to make many of his good starts count. (iv) Improving his technical skills will guarantee success.

(iii) and (iv)

(ii) and (iii)

(i), (ii) and (iii)

(ii) only

Ans .

Explanation :
i) is incorrect "He was guilty of throwing away his wicket several times after working hard to lay a strong foundation. " (ii) is correct, "His critics pointed out that until he addressed this problem, success at the highest level will continue to elude him." (iii) is correct, "His critics pointed out that until he addressed this problem, success at the highest level will continue to elude him." (iv) is incorrect "Temperament is also required"

Q. 10The probabilities that a student passes in Mathematics, Physics and Chemistry are m, p and c respectively. Of these subjects, the student has 75% chance of passing in at least one, a 50% chance of passing in at least two and a 40% chance of passing in exactly two. Following relations are drawn in m, p and c: 1. p + m + c = 27/20 2. p + m + c = 13/20 3. (p) * (m) * (c) = 1/10

Only relation 1 is true

Only relation 2 is true

Relations 2 and 3 are true

Relations 1 and 3 are true

Ans .

Explanation :
1 - (1 - m) (1 - p) (1 - c) = 0.75 -------(1) (1 - m)pc + (1 - p)mc + (1 - c)mp + mpc = 0.5 -------(2) (1 - m)pc + (1 - p)mc + (1 - c)mp = 0.4 -------(3) From last 2 equations, we can derive mpc = 0.1 After simplifying equation 1, we get. p + c + m - (mp + mc + pc) + mpc = 0.75 p + c + m - (mp + mc + pc) = 0.65 -------(4) After simplifying equation 3, we get pc + mc + mp - 3mpc = 0.4 Putting value of mpc, we get pc + mc + mp = 0.7 After putting above value in equation 4, we get p + c + m - 0.7 = 0.65 p + c + m = 1.35 = 27/20

Q.11

The maximum number of processes that can be in Ready state for a computer system with n CPUs is

N^{2}

independnt of N

Ans .

Explanation :
The size of ready queue doesn't depend on number of processes. A single processor system may have a large number of processes waiting in ready queue.

Q. 12

Let # be a binary operator defined as X # Y = X' + Y' where X and Y are Boolean variables. Consider the following two statements. S1: (P # Q) # R = P # (Q # R) S2: Q # R = R # Q

Only S1 is True

Only S2 is True

Both S1 and S2 are True

Neither S1 nor S2 are True

Ans .

Explanation :
S2 is true, as X' + Y' = Y' + X' S1 is false. Let P = 1, Q = 1, R = 0, we get different results (P # Q) # R = (P' + Q')' + R' = (0 + 0)' + 1 = 1 + 1 = 1 P # (Q # R) = P' + (Q' + R')' = 0 + (0 + 1)' = 0 + 0 = 0

Q. 13Consider the following relation Cinema (theater, address, capacity) Which of the following options will be needed at the end of the SQL query SELECT P1. address FROM Cinema P1

WHERE P1. Capacity> = All (select P2. Capacity from Cinema P2)

WHERE P1. Capacity> = Any (select P2. Capacity from Cinema P2)

WHERE P1. Capacity > All (select max(P2. Capacity) from Cinema P2)

WHERE P1. Capacity > Any (select max (P2. Capacity) from Cinema P2)

Ans .

Explanation :
When the ALL condition is followed by a list, the optimizer expands the initial condition to all elements of the list and strings them together with AND operators. When the ANY condition is followed by a list, the optimizer expands the initial condition to all elements of the list and strings them together with OR operators, as shown below. Source: http://oracle-base.com/articles/misc/all-any-some-comparison-conditions-in-sql.php

Q.14

Consider a function f(x) = 1-|x| on -1 = x = 1. The value of x at which the function attains a maximum and the maximum value of the function are:

0,-1

-1, 0

0, 1

-1, 2.

Ans .

Explanation :

f(x) = 1 - |x|
f(0) = 1
f(1) = f(-1) = 0
f(0.5) = f(-0.5) = 0.5
The maximum is attained at x = 0, and the maximum value is 1.

Q.15

A generic term that includes various items of clothing such as a skirt, a pair of trousers and a shirt is

fabric

textile

fibre

apparel

Ans .

Q.16

Out of the following four sentences, select the most suitable sentence with respect to grammar and usage:

Since the report lacked needed information, it was of no use to them

The report was useless to them because there were no needed information in it

Since the report did not contain the needed information, it was not real useful to them

Since the report lacked needed information, it would not had been useful to them

Ans .

Q.17

Let R be the relation on the set of positive integers such that aRb if and only if a and b are distinct and have a common divisor other than 1. Which one of the following statements about R is True?

R is symmetric and reflexive but not transitive

R is reflexive but not symmetric and not transitive

R is transitive but not reflexive and not symmetric

R is symmetric but not reflexive and not transitive

Ans .

Q.18

Which one of the following fields of an IP header is NOT modified by a typical IP router?

Checksum

Source address

Time to Live (TTL)

Length

Ans .

Explanation :
Length and checksum can be modified when IP fragmentation happens. Time To Live is reduced by every router on the route to destination. Only Source Address is what IP address can not change SO B is the answer.

Q.19

What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

T(logn) for both insertion and deletion

T(n) for both insertion and deletion

T(n) for insertion and T(logn) for deletion

T(logn) for insertion and T(n) for deletion

Ans .

Explanation :
The time taken by search, insert and delete on a BST is always proportional to height of BST. Height may become O(n) in worst case.

Q.20

A file is organized so that the ordering of data records is the same as or close to the ordering of data entries in some index. Then that index is called

Dense

Sparse

Clustered

Unclustered

Ans .

Explanation :
In Clustered Index, data blocks are stored in a way to match the index. Therefore, only one clustered index can be created on a given database table. Refer https://msdn.microsoft.com/en-IN/library/ms190457.aspx for more details.

Q.21

Consider a software program that is artificially seeded with 100 faults. While testing this program, 159 faults are detected, out of which 75 faults are from those artificially seeded faults. Assuming that both real and seeded faults are of same nature and have same distribution, the estimated number of undetected real faults is ____________.

175

185

Ans .

Explanation :
Total faults detected = 159 Real faults detected among all detected faults = 159 - 75 = 84 Since probability distribution is same, total number of real faults is (100/75)*84 = 112 Undetected real faults = 112- 84 = 28

Q.22

The result evaluating the postfix expression 10 5 + 60 6 / * 8 - is

284

142

213

Ans .

Explanation :
Refer http://dictionary.reference.com/browse/extraneous

Q.23

While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

Ans .

Explanation :
Insert(Root,key)
{
if(Root is NULL)
Create a Node with value as key and return
Else if(Root.key <= key)
Insert(Root.left,key)
Else
Insert(Root.right,key)
}

Q.24

Consider a machine with a byte addressable main memory of 220 bytes, block size of 16 bytes and a direct mapped cache having 212 cache lines. Let the addresses of two consecutive bytes in main memory be (E201F)16 and (E2020)16. What are the tag and cache line address (in hex) for main memory address (E201F)16?

E,201

F,201

E,E20

2.01F

Ans .

Explanation :
Block Size = 16 bytes
Block Offset = 4
No. of sets or cache lines = 212
Number of index bits = 12
Size of main memory = 220
Number of tag bits = 20 - 12 - 4 = 4
Let us consider the hex address E201F
Tag lines = First 4 bits = E (in hex)
Cache lines = Next 12 bits = 201 (In Hex)

Q.25

In the given matrix, one of the eigenvalues is 1. the eigenvectors corresponding to the eigenvalue 1 are

 1 -1  2 
 0  1  0 
 1  2  1

Ans .

Explanation :
And let the given matrix be A (square matrix of order 3 x3) The characteristic equation for this is : AX = zX ( X is the required eigenvector ) AX - zX = 0 [ A - z I ] [X] = 0 ( I is an identity matrix of order 3 ) put z = 1 ( because one of the eigenvalue is 1 ) [ A - 1 I ] [X] = 0 The resultant matrix is : [ 0 -1 2 ] [x1] [0] | 0 0 0 ] |x2] =|0| [ 1 2 0 ] |x3] [0] Multiplying thr above matrices and getting the equations as: -x2 + 2x3 = 0 ----------------(1) x1 + 2x2 = 0-----------------(2) now let x1 = k, then x2 and x3 will be -k/2 and -k/4 respectively. hence eigenvector X = { (k , -k/2, -k/4) } where k != 0 put k = -4c ( c is also a constant, not equal to zero ), we get X = { ( -4c, 2c, 1c ) }, i.e. { c ( -4, 2, 1 ) } Hence option B.

Q.26

Among simple LR (SLR), canonical LR, and look-ahead LR (LALR), which of the following pairs identify the method that is very easy to implement and the method that is the most powerful, in that order?

SLR, LALR

Canonical LR, LALR

SLR, canonical LR

LALR, canonical LR

Ans .

Explanation :
SLR parser is a type of LR parser with small parse tables and a relatively simple parser generator algorithm. Canonical LR parser or LR(1) parser is an LR(k) parser for k=1, i.e. with a single lookahead terminal. It can handle all deterministic context-free languages. LALR parser or Look-Ahead LR parser is a simplified version of a canonical LR parser

Q.27

Given a hash table T with 25 slots that stores 2000 elements, the load factor a for T is

0.0125

8000

1.25

Ans .

Explanation :
oad factor = (no. of elements) / (no. of table slots) = 2000/25 = 80

Q.28

Let T be the language represented by the regular expression S*0011S* where S = {0, 1}. What is the minimum number of states in a DFA that recognizes L' (complement of L)?

Ans .

Explanation :
The given regular expression matches with all strings that contain 0011. The complement should match with all strings except the strings with 0011 as substring. Following are some interesting facts/observations from this question. 1) Complement of a regular language is also regular. 2) Since complement is regular, it is always possible to make a DFA for complement. 3) A DFA that accepts its complement is obtained from the above DFA by changing all non-accepting states to accepting states and vice versa as done in this question. Below is DFA for the complement. We can get below DFA by first drawing DFA of regular language for strings with substring as 0011. After drawing DFA, we can invert all states (single circle to double circle and vice versa)

Q.29

Consider the following array of elements. <89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100>. The minimum number of interchanges needed to convert it into a max-heap is

Ans .

Explanation :

           89
      /         \
     19          50
    /  \        /  \  
  17    12     15    2
 /  \   / \   /  \
5   7  11  6  9  100

Minimum number of swaps required to convert above tree 
to Max heap is 3. Below are 3 swap operations.
Swap 100 with 15
Swap 100 with 50
Swap 100 with 89 

           100
      /         \
     19          89
    /  \        /  \  
  17    12     50    5 
 /  \   / \   /  \
7   11  6  9  2   15

Q.31

Consider a software project with the following information domain characteristic for calculation of function point metric.
Number of external inputs (I) = 30
Number of external output (O) = 60
Number of external inquiries (E) = 23
Number of files (F) = 08
Number of external interfaces (N) = 02
It is given that the complexity weighting factors for I, O, E, F and N are 4, 5, 4, 10 and 7, respectively. It is also given that, out of fourteen value adjustment factors that influence the development effort, four factors are not applicable, each of he other four factors have value 3, and each of the remaining factors have value 4. The computed value of function point metric is ____________

612.06

611

Ans .

Explanation :
The value of function point metric = UPF * VAF
Here,
UPF: Unadjusted Function Point (UFP) count
VAF: Value Adjustment Factor

UPF = 4*30 + 60*5 + 23*4 + 8*10 + 7*2 = 606
VAF = (TDI * 0.01) + 0.65
Here TDI is Total Degree of Influence
TDI = 3*4 + 0*4 + 4*6 = 36
VAF = (TDI * 0.01) + 0.65
= 36*0.01 + 0.65

= 0.36 + 0.65 = 1.01
FP = UPF * VAF
= 1.01 * 606
= 612.06

Q.32 Consider the following statements.
I. TCP connections are full duplex.
II. TCP has no option for selective acknowledgment
III. TCP connections are message streams.

Only I is correct

Only I and II are correct

Only II and III are correct

All of I, II and III are correct

Ans .

Explanation :
In TCP, as sender and receiver can send segments at the same time, It is FULL-DUPLEX. TCP has options for selective acknowledgement. With selective acknowledgments (SACKs), the data receiver can inform the sender about all segments that have arrived successfully, so the sender need retransmit only the segments that have actually been lost. As each BYTE is counted in TCP segment, and Sequence number of First BYTE is kept into header, TCP is BYTE stream protocol. So, only 1st is correct and other incorrect. Reference : https://tools.ietf.org/html/rfc2018 This solution is contributed by sandeep pandey.

Q.33

Suppose U is the power set of the set S = {1,2,3,4,5,6}. For any T ? U, let |T| denote the number of elements in T and T' denote the complement of T. For any T, R ? U, let T\R be the set of all elements in T which are not in R. Which one of the following is true?

Ans .

Explanation :
A is false, Take an example like X = {1, 2, 3, 4}, X' = {5, 6}, |X| is not same as |X'|. B is false, as any two subsets of size 5 of U would definitely have some common elements. C is false, Take an example like X = {1, 2} Y = {3, 4, 5}, X\Y = {1, 2}.

Q.34

In a room there are only two types of people, namely Type 1 and Type 2. Type 1 people always tell the truth and Type 2 people always lie. You give a fair coin to a person in that room, without knowing which type he is from and tell him to toss it and hide the result from you till you ask for it. Upon asking, the person replies the following: The result of the toss is head if and only if I am telling the truth.

The result is head

The result is tail

If the person is of Type 1, then the result is tai

If the person is of Type 2, then the result is tail

Ans .

Explanation :
“The result of the toss is head if and only if I am telling the truth.”
If the person is of Type 1 who always tell truth, then result must be head.
If the person is of Type 2 who always tell lie, then result must be head.
Negation of a sentence of the form "X is true if and only if Y is true" is "Either X is true and Y is false, or X is false and Y is true."
Refer: http://math.stackexchange.com/questions/10435/negation-of-if-and-only-if
Which means "Either toss is head and I am not telling truth, or toss is tail
and I am telling truth".
Since the person always lie, it is "Either toss is head and I am not telling truth"

Q.35

Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have exactly two children are _________.

199

200

Any number between 0 and 199

Any number between 100 and 200

Ans .

Explanation :
This can be proved using Handshaking Lemma. Refer below post to see complete proof. Handshaking Lemma and Interesting Tree Properties

Q.36

Consider the following C program.
# include
int main( )
{
static int a[] = {10, 20, 30, 40, 50};
static int *p[] = {a, a+3, a+4, a+1, a+2};
int **ptr = p;
ptr++;
printf("%d%d", ptr - p, **ptr};
}

140

120

200

Ans .

Explanation :
Now ptr is actually pointing to the first element of array p. ptr++ will make it point to the next element of array p. Its value will then change to 2004. One of the Rule of Pointer Arithmetic is that When you subtract two pointers, as long as they point into the same array, the result is the number of elements separating them. ptr is pointing to the second element and p is pointing to the first element so ptr-p will be equal to 1(Excluding the element to which ptr is pointing). Now ptr = 2004 -----> *(2004) = 1012 ----> *(1012) ----> 40. Therefore, final answer is 140. This solution is contributed by Pranjul Ahuja. .

Q.37

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

256

512

1024

2048

Ans .

Explanation :
ime complexity of merge sort is T(nLogn)
c*64Log64 is 30
c*64*6 is 30
c is 5/64
For time 6 minutes
5/64*nLogn = 6*60
nLogn = 72*64 = 512 * 9
n = 512.

Q.38

Consider a network connecting two systems located 8000 kilometers apart. The bandwidth of the network is 500 * 106 bits per second. The propagation speed of the media is 4 *106 meters per second. It is needed to design a Go-Back-N sliding window protocol for this network. The average packet size is 107 bits. The network is to be used to its full capacity. Assume that processing delays at nodes are negligible. Then, the minimum size in bits of he sequence number field has to be ________

Ans .

Explanation :
Propagation time = (8000 * 1000)/ (4 * 10^6)
= 2 seconds
Total round trip propagation time = 4 seconds
Transmission time for one packet = (packet size) / (bandwidth)
= (10^7) / (500 * 10^6)
= 0.02 seconds
Total number of packets that can be transferred before an
acknowledgement comes back = 4 / 0.02 = 200
Maximum possible window size is 200.
In Go-Back-N, maximum sequence number should be one more than
window size.
So total 201 sequence numbers are needed. 201 different sequence
numbers can be represented using 8 bits.

Q.39

Consider the following partial Schedule S involving two transactions T1 and T2. Only the read and the write operations have been shown. The read operation on data item P is denoted by read(P) and the write

T2 must be aborted and then both T1 and T2 must be re-started to ensure transaction atomicity

Schedule S is non-recoverable and cannot ensure transaction atomicity

Only T2 must be aborted and then re-started to ensure transaction atomicity

Schedule S is recoverable and can ensure atomicity and nothing else needs to be done

Ans .

Explanation :
if transaction fails, atomicity requires effect of transaction to be undone. Durability states that once transaction commits, its change cannot be undone (without running another, compensating, transaction). Recoverable schedule: A schedules exactly where, for every set of transaction Ti and Tj. If Tj reads a data items previously written by Ti, then the commit operation of Ti precedes the commit operation of Tj. Aborting involves undoing the operations and redoing them since by the time stamp it is aborted. Option (A): T2 must be aborted and then both T1 and T2 must be re-started to ensure transaction atomicity. It is incorrect because it says abort transaction T2 and then redo all the operations. But there is no gaurantee that it will succeed this time as again T1 may be fail. Option(B): Schedule S is non-recoverable and cannot ensure transaction atomicity. Correct, it is by definition an irrecoverable schedule so now even if we start to undo the actions one by one(after t1 fails) in order to ensure transaction atomicity. Still we cannot undo a commited transaction. hence this schedule is irrecoverable by definition and also not atomic since it leaves the database in an inconsistent state. Simply dirty read so nonrecoverable. Option (C): Only T2 must be aborted and then re-started to ensure transaction atomicity. It is incorrect because it says abort only transaction T2 and then redo all the T2 operations. But this is dirty read problem as it is reading the data item A which is written by T1 and T1 is not committed. Again it will be the dirty read problem. So incorrect. Option (D): Schedule S is recoverable and can ensure transaction atomicity and nothing else needs to be done. Incorrect, it is clearly saying that schedule s is recoverable but it is irrecoverable because T2 read the data item A which is written by T1 and T1 failed and rollback, at the rollback T1 start undo all operations and modified the value of A with previous value but T2 is already committed so T2 can't change the read value of A which was earlier taken from T1.

Q.40

Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and n × n respectively, where 2 = n = 10. Assume that in both code segments, elements of Y are initialized to 0 and each element X[i][j] of array X is initialized to i + j. Further assume that when stored in main memory all elements of X are in same main memory page frame. Code segment 1:
// initialize elements of Y to 0
// initialize elements X[i][j] of X to i+j
for (i = 0; i < n; i++)
y[i] + = X[0][i];
Code segment 2:
// initialize elements of Y to 0
// initialize elements X[i][j] of X to i+j
for (i = 0; i < n; i++)
y[i] + = X[i][0];
Which of the following statements is/are correct?
S1: Final contents of array Y will be same in both code segments.
S2: Elements of array X accessed inside the for loop shown in
code segment 1 are contiguous in main memory.
S3: Elements of array X accessed inside the for loop shown in
code segment 2 are contiguous in main memory.

Only S2 is correct

Only S1 is correct

Only S1 and S2 are correct

Only S1 and S3 are correct

Ans .

Explanation :
In C, 2D arrays are stored in row major order. Therefore, S2 is correct, but S3 is not correct.

Q.41

Consider the following grammar G.
  S -> F -->H
  F -> p --> c
  H-> d-->c 
Where S, F and H are non-terminal symbols, p, d and c are terminal symbols. Which of the following statement(s) is/are correct?
S1: LL(1) can parse all strings that are generated using grammar G.
S2: LR(1) can parse all strings that are generated using grammar G.

Only S1

Only S2

Both S1 and S2

Neither S1 and S2

Ans .

Explanation :

The given grammar is ambiguous as there are two possible leftmost derivations for string "c".

First Leftmost Derivation
  S ? F 
  F ? c

Second Leftmost Derivation
  S ? H
  H ? c

An Ambiguous grammar can neither be LL(1) nor LR(1)

Q.42

Which of the following languages are context-free?
L1 = {ambnanbm ? m, n = 1}
L2 = {ambnambn ? m, n = 1}
L3 = {ambn ? m = 2n + 1}

L1 and L2 only

L1 and L3 only

L3 and L2 only

L4 and L2 only

Ans .

Explanation :
We can build a push down automata for L1 and L3, but can not build push down automata for L@. Note that a PDA can uses a stack. L1 and L3 can be identified using a single stack, but L2 can't be.

Q.43

If the following system has non-trivial solution,
  px + qy + rz = 0
  qx + ry + pz = 0
  rx + py + qz = 0 
then which one of the following options is True?

p - q + r = 0 or p = -q = -r

p + q + r = 0 or p = q = r

p - q + r = 0 or p = -q = r

p +q + r = 0 or p = -q = -r

Ans .

Explanation :

Q.44

For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?
Process    Arrival Time    Processing Time
  A              0              3
  B              1              6
  C              4              4
  D              6              2

First Come First Serve

Shortest Remaining Time

Non-preemptive Shortest Job First

Round Robin with Quantum value two

Ans .

Explanation :

Turnaround time is the total time taken between the submission of a program/process/thread/task (Linux) for execution and the return of the complete output to the customer/user. Turnaround Time = Completion Time - Arrival Time. FCFS = First Come First Serve (A, B, C, D) SJF = Non-preemptive Shortest Job First (A, B, D, C) SRT = Shortest Remaining Time (A(3), B(1), C(4), D(2), B(5)) RR = Round Robin with Quantum value 2 (A(2), B(2), A(1),C(2),B(2),D(2),C(2),B(2)  
Pr  Arr.Time  P.Time   FCFS     SJF      SRT    RR
A      0       3      3-0=3    3-0=3    3-0=3   5-0=5
B      1       6      9-1=8    9-1=8    15-1=14 15-1=14         
C      4       4      13-4=9   15-4=11  8-4=4   13-4=9 
D      6       2      15-6=9   11-6=5   10-6=4  11-6=5 

Average                7.25     6.75     6.25    8.25
Shortest Remaining Time produces minimum average turn-around time.

Q.45Consider the equation (43)x = (y3)8 where x and y are unknown. The number of possible solutions is ________.

Ans .

Explanation :
3 + 4x = 3 + 8y where 0 <= y <= 7
and x >= 5 (because the number represented in base x is 34)
x = 2y and 0 <= y <= 7
The following are possible solutions
y = 3, 4, 5, 6, 7
x = 6, 8, 10, 12, 14

Q.46

Since it is a network that uses switch, every packet goes through two links, one from source to switch and other from switch to destination. Since there are 10000 bits and packet size is 5000, two packets are sent. Transmission time for each packet is 5000 / 1077 bits per second links. Each link has a propagation delay of 20 microseconds. The switch begins forwarding a packet 35 microseconds after it receives the same. If 10000 bits of data are to be transmitted between the two hosts using a packet size of 5000 bits, the time elapsed between the transmission of the first bit of data and the reception of the last bit of the data in microseconds is _________.

1035

1575

2000

2075

Ans .

Explanation :
Sender host transmits first packet to switch, the transmission time is 5000/107 which is 500 microseconds. After 500 microseconds, the second packet is transmitted. The first packet reaches destination in 500 + 35 + 20 + 20 + 500 = 1075 microseconds. While the first packet is traveling to destination, the second packet starts its journey after 500 microseconds and rest of the time taken by second packet overlaps with first packet. So overall time is 1075 + 500 = 1575.

Q.47

Suppose Xi for i = 1, 2, 3 are independent and identically distributed random variables whose probability mass functions are Pr[Xi = 0] = Pr[Xi = 1] = 1/2 for i = 1, 2, 3. Define another random variable Y = X1 X2 ? X3, where ? denotes XOR. Then Pr[Y = 0 ? X3 = 0] = ____________.

0.80

0.75

0.65

0.95

Ans .

Explanation :
From the above table, P(Y=0 nX3=0) = 3/8 And P (X3=0) = 1/2 P (Y=0 | X3=0) = P(Y=0 nX3=0) / P(X3=0) = (3/8) / (1/2) = 3/4 = 0.75 This solution is contributed by Anil Saikrishna Devarasetty . Another Solution : It is given X3 = 0. Y can only be 0 when X1 X2 is 0. X1 X2 become 0 for X1 = 1, X2 = 0, X1 = X2 = 0 and X1 = 0, X = 1 So the probability is = 0.5*0.5*3 = 0.75

Q.48In the network 200.10.11.144/27, the fourth octet (in decimal) of the last IP address of the network which can be assigned to a host is ________

125

158

122

200

Ans .

Explanation :
The last or fourth octet of network address is 144 144 in binary is 10010000. The first three bits of this octal are fixed as 100, the remaining bits can get maximum value as 11111. So the maximum possible last octal IP address is 10011111 which is 159. The question seems to by asking about host address. The address with all 1s in host part is broadcast address and can't be assigned to a host. So the maximum possible last octal in a host IP is 10011110 which is 158. The maximum possible network address that can be assigned is 200.10.11.158/31 which has last octet as 158.

Q.49

Consider the following recursive C function. If get(6) function is being called in main() then how many times will the get() function be invoked before returning to the main()?
void get (int n)
{
   if (n < 1) return;
   get(n-1);
   get(n-3);
   printf("%d", n);
}

Ans .

Explanation :

    get(6) [25 Calls]
                              /      \
               [17 Calls] get(5)       get(3) [7 Calls]
                        /     \
                    get(4)    get(2)[5 Calls]
                   /    \ 
     [7 Calls] get(3)  get(1)[3 Calls]
                /     \
             get(2)   get(0)
            /    \
[3 Calls]get(1)  get(-1) 
   /  \
get(0) get(-2)

Q.50

Let G be connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes ________.

1005

995

1033

2578

Ans .

Explanation :
Since there are 100 vertices, there must be 99 edges in Minimum Spanning Tree (MST). When weight of every edge is increased by 5, the increment in weight of MST is = 99 * 5 = 495 So new weight of MST is 500 + 495 which is 995

Q.51

Let R be a relation on the set of ordered pairs of positive integers such that ((p, q), (r, s)) ? R if and only if p-s = q-r. Which one of the following is true about R?

Neither reflexive nor symmetric

Not reflexive but symmetric

Reflexive but not symmetric

Both reflexive and symmetric

Ans .

Explanation :

((p, q), (r, s)) ? R if and only if p–s = q–r

(p, q) is not related to (p, q)

as p-q is not same as q-p.

The relation is symmetric because if p–s = q–r, then s-q = s-p.

Q.52

The total number of prime implicants of the function f(w, x, y, z) = S(0, 2, 4, 5, 6, 10) is ________.

Ans .

Explanation :
Red,Blue and Green together make total three prime implicant. As we know "A prime implicant of a function is an implicant that cannot be covered by a more general (more reduced - meaning with fewer literals) implicant. (Wikipedia)" we've to see only prime implicants . We can make group of four 1's as in the figure(green group) , a group of two 1's in blue and red .As we can't reduce it further so this is minimal representation of problem and hence total number of prime implicant =3. So answer (B) part.

Q.53

Both I and II

Neither I nor II

Only I

Only II

Ans .

Explanation :
The value of sine function varies from -1 to 1.
For sin = -1 or any other negative value, I becomes false.
For sin = 1 or any other negative value, II becomes false

Q.54

Given the function F = P' + QR, where F is a function in three Boolean variables P, Q and R and P' = !P, consider the following statements.
  S1: F = S (4, 5, 6)
  S2: F = S (0, 1, 2, 3, 7)
  S3: F = ? (4, 5, 6)
  S4: F = ? (0, 1, 2, 3, 7)

S1-true, S2-false, S3-True, S4-False

S1-False, S2-True, S3-True, S4-False

S1-False, S2-True, S3-True, S4-true

S1-False, S2-True, S3-false, S4-False

Ans .

Explanation :
After drawing K map of F = P` + QR ,we can find out S2 and S3 are TRUE

Q.55

Ans .

Explanation :
Therefore the correct option is B.

Q.56Consider B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that can be accommodated in each non-leaf node of the tree is

Ans .

Explanation :
Let m be the order of B+ tree m(8)+(m-1)12 <= 1024
[Note that record pointer is not needed in non-leaf nodes]
m <= 51
Since maximum order is 51, maximum number of keys is 50. Let m be the order of B+ tree
m(8)+(m-1)12 <= 1024
[Note that record pointer is not needed in non-leaf nodes]
m <= 51
Since maximum order is 51, maximum number of keys is 50.

Q.57

Consider the following code sequence having five instructions I1 to I5. Each of these instructions has the following format.
    OP Ri, Rj, Rk 
where operation OP is performed on contents of registers Rj and Rk and the result is stored in register Ri.
   I1 : ADD R1, R2, R3
   I2 : MUL R7, R1, R3
   I3 : SUB R4, R1, R5
   I4 : ADD R3, R2, R4
   I5 : MUL R7, R8, R9 
Consider the following three statements:
S1: There is an anti-dependence between instructions I2 and I5.
S2: There is an anti-dependence between instructions I2 and I4.
S3: Within an instruction pipeline an anti-dependence always 
    creates one or more stalls. 
Which one of above statements is/are correct?

Only S1 and S2 are false

Only S2 is true

Only S1 is true

Only S1 and S2 are true

Ans .

Explanation :

 S1: There is an anti-dependence between instructions I2 and I5.
False, I2 and I5 don't form any write after read situation.  
They both write R7.

S2: There is an anti-dependence between instructions I2 and I4.
True, I2 reads R3 and I4 writes it.

S3: Within an instruction pipeline an anti-dependence always 
    creates one or more stalls. 
Anti-dependency can be removed by renaming variables. 
See following example.
1. B = 3
2. A = B + 1
3. B = 7
Renaming of variables could remove the dependency.
1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

Q.58

Consider the following C program:
# include 
int main( )
{
   int i, j, k = 0;
   j = 2 * 3 / 4 + 2.0 / 5 + 8 / 5;
   k  -= --j;
   for (i = 0; i < 5; i++)
   {
      switch(i + k)
      {
         case 1:
         case 2: printf("\n%d", i + k);
         case 3: printf("\n%d", i + k);
         default: printf("\n%d", i + k);
      }
   }
   return 0;
}

Ans .

Explanation :

 For i = 0, the value of i+k becomes -1, default block 
           is executed, count = 1.
For i = 1, the value of i+k becomes 0, default block
           is executed, count = 2.
For i = 2, the value of i+k becomes 1, all blocks are 
           executed as there is no break, count = 5
For i = 3, the value of i+k becomes 2, three blocks 
           after case 1: are executed, count = 8
For i = 4, the value of i+k becomes 3, two blocks 
           are executed, count = 10

Q.59

Suppose c =  is an array of length k, where all the entries are from the set {0, 1}. For any positive integers a and n, consider the following pseudocode.
DOSOMETHING (c, a, n)
z ? 1
for i ? 0 to k - 1
    do z ? z2 mod n
    if c[i] = 1
       then z ? (z * a) mod n
return z 
If k = 4, c = <1, 0, 1, 1>, a = 2 and n = 8, then the output of DOSOMETHING(c, a, n) is

Ans .

Explanation :
For i = 0, z = 1 mod 8 = 1, since c[0] = 1, z = 1*2 mod 8 = 2.
For i = 1, z = 2*2 mod 8 = 1, since c[1] = 0, z remains 4.
For i = 2, z = 16 mod 8 = 0

Q.60

Assume that the bandwidth for a TCP connection is 1048560 bits/sec. Let a be the value of RTT in milliseconds (rounded off to the nearest integer) after which the TCP window scale option is needed. Let B be the maximum possible window size with window scale option. Then the values of a and B are.

63 milliseconds 65535 * 214

63 milliseconds 65535 * 216

500 milliseconds 65535 * 214

500 milliseconds 65535 * 216

Ans .

Q.61

Consider the following reservation table for a pipeline having three stages S1, S2 and S3.

     Time -->
-----------------------------
      1    2   3    4     5
-----------------------------
S1  | X  |   |   |    |  X |    
S2  |    | X |   | X  |    |
S3  |    |   | X |    |    |

The minimum average latency (MAL) is __________

Ans .

Explanation :

S1 | X | Y |   |   | X | Y | X | Y |   |   | X | Y |
S2 |   | X | Y | X | Y |   |   | X | Y | X | Y |   |
S3 |   |   | X | Y |   |   |   |   | X | Y |   |   |

We can interleave instructions like the above 
pattern.

Latency between X and Y is 1.

Latency between fist and second X is 5.

The pattern repeats after that.
So, MAL is (1 + 5)/2;

Q.62

Consider the following policies for preventing deadlock in a system with mutually exclusive resources.
I. Processes should acquire all their resources at the
beginning of execution. If any resource is not
available, all resources acquired so far are released.
II. The resources are numbered uniquely, and processes are
allowed to request for resources only in increasing
resource numbers.
III. The resources are numbered uniquely, and processes are
allowed to request for resources only in decreasing
resource numbers.
IV. The resources are numbered uniquely. A process is allowed
to request only for a resource with resource number larger
than its currently held resources.
Which of the above policies can be used for preventing deadlock?

Any one of I and III but not II or IV

Any one of I, III and IV but not II

Any one of II and III but not I or IV

Any one of I, II, III and IV

Ans .

Explanation :
If Ist is followed, then hold and wait will never happen. II, III and IV are similar. If any of these is followed, cyclic wait will not be possible

Q.64

Consider the following C program. The output of the program is __________.
# include
int f1(void);
int f2(void);
int f3(void);
int x = 10;
int main()
{
int x = 1;
x += f1() + f2() + f3() + f2();
pirntf("%d", x);
return 0;
}
int f1()
{
int x = 25;
x++;
return x;
}
int f2( )
{
static int x = 50;
x++;
return x;
}
int f3( )
{
x *= 10;
return x;
}

230

231

131

330

Ans .

Explanation :
x += f1() + f2() + f3() + f2();
x = x + f1() + f2() + f3() + f2();
f1() returns 26
f2() returns 51
f3() returns 100
second call to f2() returns 52
[Note x is static in f2()]
x = 1 + 26 + 51 + 100 + 52 = 230

Q.65

Consider three software items: Program-X, Control Flow Diagram of Program-Y and Control Flow Diagram of Program-Z as shown below/p> ”GATE

4, 4, 7

3, 4, 7

4, 4, 8

4, 3, 8

Ans .

Explanation :
The cyclomatic complexity of a structured program[a] is defined with reference to the control flow graph of the program, a directed graph containing the basic blocks of the program, with an edge between two basic blocks if control may pass from the first to the second. The complexity M is then defined as.
M = E - N + 2P,
where
E = the number of edges of the graph.
N = the number of nodes of the graph.
P = the number of connected components.
Source: http://en.wikipedia.org/wiki/Cyclomatic_complexity
For first program X, E = 11, N = 9, P = 1, So M = 11-9+2*1 = 4
For second program Y, E = 10, N = 8, p = 1, So M = 10-8+2*1 = 4
For Third program X, E = 22, N = 17, p = 1, So M = 22-17+2*1 = 7
]

upscfever.com

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

GATE-CS-2015 (Set 3)

UPSCFEVER - POPULAR PAGES

Join The Movement

Discussions and Comments