Category: GATE

Gate 2018 Computer Science and Information Technology 

Q. 1 “ From where are they bringing their books? ________ bringing _______ books from _____.” The words that best fill the blanks in the above sentence are

A. Their, they’re, there

B. They’re, their, there

C. There, their, they’re

D. They’re, there, there

 

Q. 2 “ A _________ investigation can sometimes yield new facts, but typically organized ones are more successful.” The word that best fills the blank in the above sentence is

A. meandering

B. timely

C. consistent

D. systematic

 

Q. 3 The area of a square is d. What is the area of the circle which has the diagonal of the square as its diameter?

A. d

B. d2 d2

C. 1 4 | 1 4 14 d²

D. ½d

 

Q. 4 What would be the smallest natural number which when divided either by 20 or by 42 or by 76 leaves a remainder of 7 in each case?

A. 3047

B. 6047

C. 7987

D. 63847

 

Q. 5 What is the missing number in the following sequence? 2, 12, 60, 240, 720, 1440, _____, 0 

A. 2880

B. 1440

C. 720

D. 0

 

Q. 6 In appreciation of the social improvements completed in a town, a wealthy philanthropist decided to gift Rs 750 to each male senior citizen in the town and Rs 1000 to each female senior citizen. Altogether, there were 300 senior citizens eligible for this gift. However, only 8/9th of the eligible men and 2/3rd of the eligible women claimed the gift. How much money (in Rupees) did the philanthropist give away in total?

A. 1,50,000

B. 2,00,000

C. 1,75,000

D. 1,51,000

 

Q. 7 If pqr ≠ 0 and p⁻ⁱ = 1/q , q⁻ⁿ = 1/r , r ⁻° = 1/p , what is the value of the product i*n*o?

A. -1

B. 1/(p*q*r)

C. 1

D. p*q*r

 

Q. 8 In a party, 60% of the invited guests are male and 40% are female. If 80% of the invited guests attended the party and if all the invited female guests attended, what would be the ratio of males to females among the attendees in the party?

A. 2:3

B. 1:1

C. 3:2

D. 2:1

 

Q. 9 In the figure, ∠DEC + ∠BFC is equal to

A. ∠BCD − ∠BAD

B. ∠BAD + ∠BCF

C. ∠BAD + ∠BCD

D. ∠CBA + ∠ADC

 

Q. 10 A six sided unbiased die with four green faces and two red faces is rolled seven times. Which of the following combinations is the most likely outcome of the experiment? 

A. Three green faces and four red faces.

B. Four green faces and three red faces

C. Five green faces and two red faces.

D. Six green faces and one red face

 

Q. 11 Which one of the following is a closed form expression for the generating function of the sequence {an}, where an = 2n + 3 for all n = 0, 1, 2,… ?

A. 3/(1−x)²

B. 3x⁄(1−x)²

C. 2-x/(1−x)²

D. 3-x/(1−x)²

 

Q. 12 Consider the following C program.

#include 

struct Ournode{

char x,y,z;

};

int main(){

struct Ournode p = {‘1’, ‘0’, ‘a’+2};

struct Ournode *q = &p;

printf (“%c, %c”, *((char*)q+1), *((char*)q+2));

return 0;

}

The output of this program is

A. 0, c

B. 0, a+2

C. 0, a+2

D. 0, c

 

Q. 13 A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let enqueue be implemented by inserting a new node at the head, and dequeue be implemented by deletion of a node from the tail. Which one of the following is the time complexity of the most time-efficient implementation of enqueue and dequeue, respectively, for this data structure?

A. θ(1), θ(1)

B. θ(1), θ(n)

C. θ(n), θ(1)

D. θ(n), θ(n)

 

Q. 14 Let ⊕ and ⊗ denotes the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is not correct?

A. a

B. b

C. c

D. d

 

Q. 15 Consider the following processor design characteristics.

I. Register-to-register arithmetic operations only

II. Fixed-length instruction format

III. Hardwired control unit

Which of the characteristics above are used in the design of a RISC processor?

A. I and II only

B. II and III only

C. I and III only

D. I, II and III

 

Q. 16 L et N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

A. k ≥2ⁿ

B. k ≥ n

C. k ≤n²

D. k ≤2ⁿ

 

Q. 17 The set of all recursively enumerable languages is

A. closed under complementation

B. closed under intersection

C. a subset of the set of all recursive languages

D. an uncountable set.

 

Q. 18 Which one of the following statements is FALSE?

A. Context-free grammar can be used to specify both lexical and syntax rules.

B. Type checking is done before parsing.

C. High-level language programs can be translated to different Intermediate Representations.

D. Arguments to a function can be passed using the program stack.

 

Q. 19 The following are some events that occur after a device controller issues an interrupt while process L is under execution.

(P) The processor pushes the process status of L onto the control stack.

(Q) The processor finishes the execution of the current instruction.

(R) The processor executes the interrupt service routine.

(S) The processor pops the process status of L from the control stack.

(T) The processor loads the new PC value based on the interrupt.

Which one of the following is the correct order in which the events above occur?

A. QPTRS

B. PTRSQ

C. TRPQS

D. QTPRS

 

Q. 20 Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory, and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units. Which one of the following is the correct expression for the page fault rate experienced by the process?

A. (D – M) / (X – M)

B. (X – M) / (D – M)

C. (D – X) / (D – M)

D. (X – M) / (D – X)

 

Q. 21 In an Entity-Relationship (ER) model, suppose 􀀎 is a many-to-one relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in 􀀎 and that the cardinality of E1 is greater than the cardinality of E2. Which one of the following is true about 􀀎?

A. Every entity in E1 is associated with exactly one entity in E2.

B. Some entity in E1 is associated with more than one entity in E2.

C. Every entity in E2 is associated with exactly one entity in E1

D. Every entity in E2 is associated with at most one entity in E1.

 

Q. 22 Consider the following two tables and four queries in SQL.

Book (isbn, bname), Stock (isbn, copies)

Query 1: SELECT B.isbn, S.copies

FROM Book B INNER JOIN Stock S

ON B.isbn = S.isbn;

Query 2: SELECT B.isbn, S.copies

FROM Book B LEFT OUTER JOIN Stock S

ON B.isbn = S.isbn;

Query 3: SELECT B.isbn, S.copies

FROM Book B RIGHT OUTER JOIN Stock S

ON B.isbn = S.isbn;

Query 4: SELECT B.isbn, S.copies

FROM Book B FULL OUTER JOIN Stock S

ON B.isbn = S.isbn;

Which one of the queries above is certain to have an output that is a superset of the

outputs of the other three queries?

A. Query 1

B. Query 2

C. Query 3

D. Query 4

 

Q. 23 Match the following:

Field Length in bits

P. UDP Header’s Port Number I. 48

Q. Ethernet MAC Address II. 8

R. IPv6 Next Header III. 32

S. TCP Header’s Sequence Number IV. 16

A. P-III, Q-IV, R-II, S-I

B. P-II, Q-I, R-IV, S-III

C. P-IV, Q-I, R-II, S-III

D. P-IV, Q-I, R-III, S-II

 

Q. 24 Consider the following statements regarding the slow start phase of the TCP congestion control algorithm. Note that cwnd stands for the TCP congestion window and MSS denotes the Maximum Segment Size.

A. The cwnd increases by 2 MSS on every successful acknowledgment.

B. The cwnd approximately doubles on every successful acknowledgement.

C. The cwnd increases by 1 MSS every round trip time.

D. The cwnd approximately doubles every round trip time.

 

Q. 25 Two people, P  and Q, decide to independently roll two identical dice, each with 6 faces, numbered 1 to 6. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until there is no tie. Define a trial as a throw of the dice by P and Q. Assume that all 6 numbers on each dice are equi-probable and that all trials are independent. The probability (rounded to 3 decimal places) that one of them wins on the third trial is _____. 

 

Q. 26 The value of the expression as shown in figure correct to three decimal place is ?

Assuming (π = 3.14)

 

Q. 27 Consider a matrix A=uvⁿ where u = (1⁄2) , v = (1⁄1). Note that vⁿ denotes the transpose of v. The largest eigenvalue of A is

 

Q.28 The chromatic number of the following graph is

 

Q. 29 Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is ________.

 

Q. 30 The postorder traversal of a binary tree is 8,9,6,7,4,5,2,3,1. The inorder traversal of the same tree is 8,6,9,4,7,2,5,1,3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.

 

Q. 31 Consider the following C program:

#include

int counter = 0;

int calc (int a, int b) {

int c;

counter++;

if (b==3) return (a*a*a);

else {

c = calc(a, b/3);

return (c*c*c);

}

}

int main (){

calc(4, 81);

printf (“%d”, counter);

}

The output of this program is _____.

 

Q. 32 Consider the sequential circuit shown in the figure, where both flip-flops used are positive edge-triggered D flip-flops. The number of states in the state transition diagram of this circuit that have a transition back to the same state on some value of “in” is _____.

 

Q. 33 A 32-bit wide main memory unit with a capacity of 1 GB is built using 256M × 4-bit DRAM chips. The number of rows of memory cells in the DRAM chip is 214. The time taken to perform one refresh operation is 50 nanoseconds. The refresh period is 2 milliseconds. The percentage (rounded to the closest integer) of the time available for performing the memory read/write operations in the main memory unit is __________.

 

Q. 34 Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of 􀀏 instances. Resource instances can be requested and released only one at a time. The largest value of 􀀏 that will always avoid deadlock is ____.

 

Q. 35 Consider a long-lived TCP session with an end-to-end bandwidth of 1 Gbps (= 109 bits persecond). The session starts with a sequence number of 1234. The minimum time (in seconds, rounded to the closest integer) before this sequence number can be used again is _______.

 

Q. 36 Consider a matrix P whose only eigenvectors are the multiples of [1⁄4]. Consider the following statements.

(I) P does not have an inverse 

(II) P has a repeated eigenvalue

(III) P cannot be diagonalized

Which one of the following options is correct?

A. Only I and III are necessarily true

B. Only II is necessarily true

C. Only I and II are necessarily true

D. Only II and III are necessarily true

 

Q. 37 Let N be the set of natural numbers. Consider the following sets.

P: Set of Rational numbers (positive and negative)

Q: Set of functions from {0, 1} to N

R: Set of functions from N to {0, 1}

S: Set of finite subsets of N.

Which of the sets above are countable?

A. Q and S only

B. P and S only

C. P and R only

D. P, Q and S only

 

Q. 38 Consider the first-order logic sentence ≡ ∃s∃t∃u∀v∀w∀x∀y ƒ(s, t, u, v, w, x, y)

where ƒ(s, t, u, v, w, x, y) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose 􀀐 has a model with a universe containing 7 elements. Which one of the following statements is necessarily true? 

A. There exists at least one model of 􀀐 with universe of size less than or equal to 3.

B. There exists no model of 􀀐 with universe of size less than or equal to 3.

C. There exists no model of 􀀐 with universe of size greater than 7.

D. Every model of 􀀐 has a universe of size equal to 7.

 

Q. 39 Consider the following C program:

#include

void fun1(char *s1, char *s2){

char *tmp;

tmp = s1;

s1 = s2;

s2 = tmp;

}

void fun2(char **s1, char **s2){

char *tmp;

tmp = *s1;

*s1 = *s2;

*s2 = tmp;

}

int main(){

char *str1 = “Hi”, *str2 = “Bye”;

fun1(str1, str2); printf(“%s %s “, str1, str2);

fun2(&str1, &str2); printf(“%s %s”, str1, str2);

return 0;

}

The output of the program above is

A. Hi Bye Bye Hi

B. Hi Bye Hi Bye

C. Bye Hi Hi Bye

D. Bye Hi Bye Hi

 

Q. 40 Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements.

(I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)

(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |􀀙 − 􀀚| = 1.

Which of the statements above must necessarily be true

A. I only

B. II only

C. Both I and II

D. Neither I nor II

 

Q. 41 Assume that multiplying a matrix G1 of dimension 􀀃 × 􀀄 with another matrix G2 of dimension 􀀄 × 􀀅 requires 􀀃􀀄􀀅 scalar multiplications. Computing the product of n matrices G1G2G3…Gn can be done by parenthesizing in different ways. Define Gi Gi+1 as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G1G2G3G4G5G6 using parenthesization (G1(G2G3)) (G4(G5G6)), G2G3 and G5G6 are the only explicitly computed pairs. Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

A. F1F2 and F3F4 only

B. F2F3 only

C. F3F4 only

D. F1F2 and F4F5 only

 

Q. 42 Consider the following C code. Assume that unsigned long int type length is 64 bits. unsigned long int fun(unsigned long int n){

unsigned long int i, j = 0, sum = 0;

for (i = n; i > 1; i = i/2) j++;

for ( ; j > 1; j = j/2) sum++;

return(sum);

}

The value returned when we call fun with the input 2⁴⁰ is

A. 4

B. 5

C. 6

D. 40

 

Q. 43 Consider the unsigned 8-bit fixed point binary number representation below,

b7 b6 b5 b4 b3 . b2 b1 b0

where the position of the binary point is between b3 and b2. Assume b7 is the most

significant bit. Some of the decimal numbers listed below cannot be represented exactly in the above representation:

(i) 31.500 (ii) 0.875 (iii) 12.100 (iv) 3.001

Which one of the following statements is true?

A. None of (i), (ii), (iii), (iv) can be exactly represented

B. Only (ii) cannot be exactly represented

C. Only (iii) and (iv) cannot be exactly represented

D. Only (i) and (ii) cannot be exactly represented

 

Q. 44 The size of the physical address space of a processor is 2^p bytes. The word length is 2^w bytes. The capacity of cache memory is 2^n bytes. The size of each cache block is 2^m words. For a 􀀏-way set-associative cache memory, the length (in number of bits) of the tag field is

A. p – n – log₂ K

B. p – n + log₂ K

C. p – n – m – w – log₂ K

D. p – n – m – w + log₂ K

 

Q. 45 Consider the following languages as shown in figure. Which of the languages are context free?

A. I and IV only

B. I and II only

C. II and III only

D. II and Iv only

 

Q. 46 Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M.

(I) For an unrestricted grammar G and a string w, whether w ∈ L(G)

(II) Given a Turing machine M, whether L(M) is regular

(III) Given two grammars G₁ and G₂ , whether L G₁) = L(G₂)

(IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language.

Which one of the following statements is correct?

A. Only I and II are undecidable

B. Only III is undecidable

C. Only II and IV are undecidable

D. Only I, II and III are undecidable

 

Q. 47 A lexical analyzer uses the following patterns to recognize three tokens T₁, T₂ and T₃ over the alphabet {a,b,c}.

T₁: a? (b | c)*a

T₂: b? (a | c)*b

T₃: c? (b | a)*c

Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix. If the string bbaacabc is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

A. T₁T₂T₃

B. T₁T₁T₃

C. T₂T₁T₃

D. T₃T₃

 

Q. 48 Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #. Which one of the following is correct for the given parse tree?

A. $ has higher precedence and is left associative; # is right associative

B. # has higher precedence and is left associative; $ is right associative

C. $ has higher precedence and is left associative; # is left associative

D. # has higher precedence and is right associative; $ is left associative

 

Q. 49 In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max as given below. For example, Max[P2,F] is the maximum number of instances of F that P2 would require. The number of instances of the resources allocated to the various processes at any given state is given by a matrix named Allocation. Consider a state of the system with the Allocation matrix as shown below, and in which 3 instances of E and 3 instances of F are the only resources available. From the perspective of deadlock avoidance, which one of the following is true? 

A. The system is in safe state.

B. The system is not in safe state, but would be safe if one more instance of E were available

C. The system is not in safe state, but would be safe if one more instance of F were available

D. The system is not in safe state, but would be safe if one more instance of G were available

 

Q. 50 Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is 􀀡. Three semaphores empty, full and mutex are defined with respective initial values of 0, 􀀡 and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal(). Which one of the following assignments to P, Q, R and S will yield the correct solution?

A. P: full, Q: full, R: empty, S: empty

B. P: empty, Q: empty, R: full, S: full

C. P: full, Q: empty, R: empty, S: full

D. P: empty, Q: full, R: full, S: empty

 

Q. 51  Consider the relations r(A, B) and s(B, C), where s.B is a primary key and r.B is a foreign key referencing s.B. Consider the query as shown in figure

Let LOJ denote the natural left outer join operation. Assume that r and s contain no null

values . Which of the following queries is not equivalent to q ?

A. (A)

B. (B)

C. (C)

D. (D)

 

Q. 52 Consider the following four relational schemas. For each schema, all non-trivial functional dependencies are listed. The underlined attributes are the respective primary keys. Schema I: Registration (roll no, courses)

Field ‘courses’ is a set-valued attribute containing the set of courses a student has

registered for. Non-trivial functional dependency:

roll no −> courses

Schema II: Registration (roll no, course id, email)

Non-trivial functional dependencies:

roll no, course id −> email

email −> rollno

Schema III: Registration (roll no, course id, marks, grade)

Non-trivial functional dependencies:

roll no, course Id−> marks, grade marks −> grade

Schema IV: Registration (roll no, course id, credit)

Non-trivial functional dependencies:

roll no, course id −> credit course id −> credit

Which one of the relational schemas above is in 3NF but not in BCNF?

A. Schema I

B. Schema II

C. Schema III

D. Schema IV

 

Q. 53 Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2, … , 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and  denote the number of connected components in G. Then, 􀀗 + 10􀀢 = _____.

 

Q. 54 Consider Guwahati (G) and Delhi (D) whose temperatures can be classified as high (H), medium (M) and low (L). Let P(HG ) denote the probability that Guwahati has high temperature. Similarly, P(MG ) and P(LG ) denotes the probability of Guwahati having medium and low temperatures respectively. Similarly, we use P(HD), P(MD) and P(LD) for Delhi.

The following table gives the conditional probabilities for Delhi’s temperature given Guwahati’s temperature.

Consider the first row in the table above. The first entry denotes that if Guwahati has high temperature (HG) then the probability of Delhi also having a high temperature (HD) is 0.40; i.e., P(HD|HG ) = 0.40. Similarly, the next two entries are P(MD|HG ) = 0.48 and P(LD|HG ) =

0.12. Similarly for the other rows.

If it is known that P(HG ) = 0.2, P(MG ) = 0.5, and P(LG ) = 0.3, then the probability (correct to two decimal places) that Guwahati has high temperature given that Delhi has high temperature is_________.

 

 

Q. 55 Consider the following program written in pseudo-code. Assume that x and y are integers. Count(x,y) {

if (y != 1){

if (x != 1) {

print(“*”);

Count(x/2, y);

}

else {

y = y-1;

Count(1024, y);

}

}

}

The number of times that the print statement is executed by the callCount(1024,1024) is

_____.

 

Q. 56 The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is _____.

 

Q. 57 Consider the following undirected graph G: Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is ______.

 

Q. 58 Consider the weights and values of items listed in figure. Note that there is only one unit of each item. The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by V₀ . A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by V₁. The value of V₀ − V₁ is

 

Q. 59 Consider the minterm list form of a Boolean function 􀀊 given below.

F(P, Q, R, S) = Σn(0, 2, 5, 7, 9, 11) + d(3, 8, 10, 12, 14)

Here, 􀀧 denotes a minterm and 􀀁 denotes a don’t care term. The number of essential

prime implicants of the function 􀀊 is ______.

 

Q. 60 The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards. The number of clock cycles required for completion of execution of the sequence of instructions is ______. 

 

Q. 61 A processor has 16 integer registers (R0, R1, .. , R15) and 64 floating point registers (F0, F1,… , F63). It uses a 2-byte instruction format. There are four categories of instructions: Type-1, Type-2, Type-3, and Type-4. Type-1 category consists of four instructions, each with 3 integer register operands (3Rs). Type-2 category consists of eight instructions, each with 2 floating point register operands (2Fs). Type-3 category consists of fourteen instructions, each with one integer register operand and one floating point register operand (1R+1F). Type-4 category consists of N instructions, each with a floating point register operand (1F). The maximum value of N is __________.

 

Q. 62 Given a language 􀀛, define Lⁿⁱ as follows

L⁰ = {s}

Lⁿ = Lⁿ⁻¹. L for all n > 0

The order of a language L is defined as the smallest k such thatLⁱ ⁱ = Lⁱ ⁱ ⁺¹. Consider the

language L₁ (over alphabet 0) accepted by the following automaton. The order of L₁ is _____.

 

Q. 63 Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders

(numbered as 0, 1, … , 199), and 256 sectors per track (numbered as 0, 1, … , 255). The

following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time:

[120, 72, 2] , [180, 134, 1] , [60, 20, 0] , [212, 86, 3] , [56, 116, 2] , [118, 16, 1]

Currently the head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible. The total power consumption in milliwatts to satisfy all of the above disk requests using the Shortest Seek Time First disk scheduling algorithm is _______.

 

Q. 64 Consider an IP packet with a length of 4,500 bytes that includes a 20-byte IPv4 header and a 40-byte TCP header. The packet is forwarded to an IPv4 router that supports a Maximum Transmission Unit (MTU) of 600 bytes. Assume that the length of the IP header in all the outgoing fragments of this packet is 20 bytes. Assume that the fragmentation offset value stored in the first fragment is 0. The fragmentation offset value stored in the third fragment is _______.

 

Q. 65 Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carrier sense based medium access protocol. A node that receives a packet to transmit will carrier-sense the medium for 5 units of time. If the node does not detect any other transmission in this duration, it starts transmitting its packet in the next time unit. If the node detects another transmission, it waits until this other transmission finishes, and then begins to carrier-sense for 5 time units again. Once they start to transmit, nodes do not perform any collision detection and continue transmission even if a collision occurs. All transmissions last for 20 units of time. Assume that the transmission signal travels at the speed of 10 meters per unit time in the medium. Assume that the system has two nodes P and Q, located at a distance d meters from each other. P starts transmitting a packet at time t=0 after successfully completing its carrier-sense phase. Node Q has a packet to transmit at time t=0 and begins to carrier-sense the medium. The maximum distance d (in meters, rounded to the closest integer) that allows Q to successfully avoid a collision between its proposed transmission and P’s ongoing transmission is _____.

 

Answer Sheet
Question	1	2	3	4	5	6	7	8	9	10
Answer	B	A	D	C	B	B	C	B	A	C
Question	11	12	13	14	15	16	17	18	19	20
Answer	D	A	B	D	D	D	B	B	A	B
Question	21	22	23	24	25	26	27	28	29	30
Answer	A	D	C	C	0.021 To 0.024	0.27 To 0.3	0.27 to 0.3	3	42	4
Question	31	32	33	34	35	36	37	38	39	40
Answer	4	2	59 to 60	2	34 to 35	D D	D	A	A	A
Question	41	42	43	44	45	46	47	48	49	50
Answer	C	B	C	B	B	D	D	A	A	C
Question	51	52	53	54	55	56	57	58	59	60
Answer	C	B	109	0.6 to 0.62	10230	80	4	16	3	219
Question	61	62	63	64	65
Answer	32	2	85	144	50

GATE 2017 Electronics and Communication Engineering Session 2

 

Q. 1 the rank of the matrix is

 

Q. 2 the general solution of the differential equation d²y/dx² + 2 dy/dx -5y = 0 in terms of arbitrary constants K₁ and K₂ is

A. a

B. b

C. c

D. d

 

Q. 3 the smaller angles(in degrees) between the planes x+y+z=1 and 2x-y+2z=0 is_________ 

 

Q. 4 the residues of the function f(z) = 1/(z-4)(z+1)³ are

A. -1/27 and -1/125

B. 1/125 and -1/125

C. -1/27 and 1/5

D. 1/27 and -1/5

 

Q. 5 In the circuit shown. V is a sinusoidal voltage source. The current I is in phase with voltage V. The ratio is (amplitude of voltage across the capacitor/amplitude of voltage across the resistor) is

 

Q. 6 A connection is made consisting of resistance A in series with a parallel combination of resistances B and C. Three resistors of value 10 ohms, 5 ohms and 2 ohms are provided. Consider all possible permutations of the given resistors into the positions A. B. C. and identify the configurations with maximum possible overall resistance. and also the ones with minimum possible overall resistance. The ratio of maximum to minimum values of the resistances (up to second decimal place) is

 

Q. 7 An LTI system with unit sample response h[n] = 5δ[n] -7δ[n – 1] +7δ[n – 3] — 5δ[n – 4] is a 

A. low-pass filter

B. high-pass filter

C. band-pass filter

D. band-stop filter

 

Q. 8 The input x(t) and the output y(t) of a continuous-time system are related as.The system is 

A. linear and time-variant

B. linear and time-invariant

C. non-linear and time-variant

D. non-linear and time-invariant

 

Q. 9 An it-channel enhancement mode MOSFET is biased at V(GS) > V(TH) and V(DS) > ( V(GS) – V(S). where Vas is the gate-to-source voltage. V(DS) is the drain-to-source voltage and V(TH) is the threshold voltage. Considering channel length modulation effect to be significant. The MOSFET behaves as a

A. voltage source with zero output impedance

B. voltage source with non-zero output impedance

C. current source with finite output impedance

D. current source with infinite output impedance

 

Q. 10 An npn bipolar junction transistor (BJT) is operating in the active region. If the reverse bias across the base-collector junction is increased, then

A. the effective base width increases and common-emitter current gain increases

B. the effective base width increases and common-emitter current gain decreases

C. the effective base width decreases and common-emitter current gain increases

D. the effective base width decreases and common-emitter current gain decreases

 

Q. 11 Consider an n-channel MOSFET having width W. length L. electron mobility in the channel μ(n) and oxide capacitance per unit area C. If gate-to-source voltage V(GS) = 0.7 V. drain-tosource voltage F(DS) = 0.1 V. (μ(n C(OX))) = 100 μA/V² threshold voltage V(TH)= 0.3 V and (W/L) = 50. then the transconductance g(m) (in mA/N) is

 

Q. 12 The output V₀, of the diode circuit shown in the figure is connected to an averaging DC voltmeter. The reading on the DC voltmeter in Volts. neglecting the voltage drop across the diode, is

 

Q. 13 In the figure. D₁ is a real silicon pit junction diode with a drop of 0.7 V under forward bias condition and D₂ is a Zener diode with breakdown voltage of — 6.8 V. The input V(in)(t) is a periodic square wave of period T. whose one period is shown in the figure. assuming 10τ << T, where τ is the time constant of the circuit , the maximum and minimum values of the output waveform is respectively.

A. 7.5V and -20.5 V

B. 6.1V and -21.9 V

C. 7.5V and -21.2 V

D. 6.1V and -22.6 V

 

Q. 14 Consider the circuit shown in the figure. Assume base-to-emitter voltage V(BE) = 0.8 V and common-base current gain (a) of the transistor is unity.

The value of the collector-to-emitter voltage V(CE) (in volt) is

 

Q. 15 For the circuit shown in the figure. P and Q are the inputs and Y is the output. The logic implemented by the circuit is

A. XNOR

B. XOR

C. NOR

D. OR

 

Q. 16 consider the circuit shown in the figure.The Boolean expression F implemented by the circuit is

A. X’Y’Z’ + XY + Y’Z

B. X’YZ’ + XZ +Y’Z

C. X’YZ’ + XY + Y’Z

D. X’Y’Z’ + XZ +Y’Z

 

Q. 17 In a DRAM,

A. periodic refreshing is not required

B. information is stored in a capacitor

C. Information is stored in a latch

D. both read and write operations can be performed simultaneously

 

Q. 18 for the system show in the figure Y(X)/X(S) =

 

Q. 19 consider the state space relization

 

Q. 20 which of the following statements is correct?

A. lead compensator is used to reduce the settling time

B. lag compensator is used to reduce the steady state error

C. lead compensator may increase the order of a system

D. lag compensator always stabilizes an unstable system

 

Q. 21 which one of the following graphs shows the shannon capacity(channel capacity) in bits of a memoryless binary symmetric channel with cross over probability p?

A. a

B. b

C. c

D. d

 

Q. 22 Consider the random process X(t) = U + Vt,where U is a zero-mean Gaussian random variable and V is a random variable uniformly distributed between 0 and 2. Assume the U and V are statistically independent. The mean value of the random process at t = 2 is 

 

Q. 23 A sinusoidal message signal is convened to a PCM signal using a uniform quantizer. The required signal-to-quantization noise ratio (SQNR) at the output of the quantizer is 40 dB. The minimum number of bits per sample needed to achieve the desired SQNR is

 

Q. 24 Two conducting spheres S1 and S2 of radii a and b (b > a) respectively. are placed far apart and connected by a long. thin conducting wire. as shown in the figure. For sonic charge placed on this structure. the potential and surface electric field on SI are Va and Ea and that on S2 are Vb and Eb, respectively. Then. which of the following is CORRECT?

A. Va = Vb and Ea < Eb

B. Va > Vb and Ea > Eb

C. Va = Vb and Ea > Eb

D. Va > Vb and Ea = Eb

 

Q. 25 A two-wire transmission line terminates in a television set. The VSWR measured on the line is 5.8. The percentage of power that is reflected from the television set is ____________

 

Q. 26 The values of the integrals and are

A. same and equal to 0.5

B. same and equal to – 0.5

C. 0.5 and -0.5. respectively

D. -0.5 and 0.5. respectively

 

Q. 27 An integral lover a counterclockwise circle C is given by

If C is defined as lz I = 3, then the value I is

A. -πi sin (1)

B. -2πi sin (1)

C. -3πi sin (1)

D. -4πi sin (1)

 

Q. 28 If the vector function P = a(x)(3y — k₁z) + a(y)(k₂x — 2z) — a(z)(k₃y + z) is irrational. then the values of the constants k₁, k₂ and k₃. respectively, are

A. 0.3, —2.5, 0.5

B. 0.0, 3.0, 2.0

C. 0.3, 0.33, 0.5

D. 4.0, 3.0, 2.0

 

Q. 29 Passengers try repeatedly to get a seat reservation in any train running between two stations until they are successful. If there is 40% chance of getting reservation in any attempt by a passenger. then the average number of attempts that passengers need to make to get a seat reserved is

 

Q. 30 The minimum value of the function f(x) = x/3(x² – 3) in the interval —100 ≤ x ≤ 100 occurs at x=

 

Q. 31 The switch in the circuit, shown in the figure. was open for a long time and is closed at t = 0. The current i(t) (in ampere) at t = 0.5 seconds is

 

Q. 32 Consider the circuit shown in the figure. The Thevenin equivalent resistance (in Q) across PQ is

 

Q. 33 Consider an LTI system with magnitude response and phase response

If the input to the system is then the average power of the output signal y(t) is

 

Q. 34 The transfer function of a causal LTI system is H(s) = 1/s. If the input to the system is x(t) = [sin(t)/πt] u(t), where u(t) is a unit step function. the system output y(t) as t tends to infinity is_________

 

Q. 35 Consider the parallel combination of two LTI systems shown in the figure.

The impulse responses of the systems are h₁(t) = 2δ(t +2)— 3δ(t + 1) h₂(t) = δ(t — 2). If the input x(t) is a unit step signal. then the energy of y(t) is

 

Q. 36 A MOS capacitor is fabricated’ on p-type Si (Silicon) where the metal work function is 4.1 eV and electron affinity of Si is 4.0 eV. Ec – Ef = 0.9 eV. where Ec and Ef are the conduction band minimum and the Fermi energy levels of Si. respectively. Oxide εᵣ = 3.9. εₒ = 8.85 x 10-” F/cm, oxide thickness tₒ = 0.1 pm and electronic charge q = 1.6 x 10-19 C. If the measured flat band voltage of this capacitor is -1 V. then the magnitude of the fixed charge at the oxidesemiconductor interface, in nC/cm1. is

 

Q. 37 For a particular intensity of incident light on a silicon pn junction solar cell, the photo current density (Jᵣ is 2.5 inA/cm2 and the open-circuit voltage (Vᵤ) is 0.451 V. Consider thermal voltage (VT) to be 25 mV. If the intensity of the incident light is increased by 20 times. assuming that the temperature remains unchanged. V,„ (in volts) will be

 

Q. 38 Two n-channel MOSFETs. T1 and T2. are identical in all respects except that the width of T2 is double that of T1. Both the transistors are biased in the saturation region of operation. but the gate overdrive voltage (Vgs — Vth) of T2 is double that of T1. where Vgs and Vin are the gate-to-source voltage and threshold voltage of the transistors, respectively. If the drain current and transconductance of T I are Id1 and Gm1 respectively. the corresponding values of these two parameters for T2 are

A. A

B. B

C. C

D. D

 

Q. 39 An abrupt pn junction (located at x = 0) is uniformly doped on both p and n sides. The width of the depletion region is W and the electric field variation in the x-direction is E(x). Which of the following figures represents the electric field profile near the Pn junction? 

A. A

B. B

C. C

D. D

 

Q. 40 Assuming that transistors MI and M2 are identical and have a threshold voltage of 1 V. the state of transistors MI and M2 are respectively

A. Saturation,Saturation

B. Linear,Linear

C. Linear,Saturation

D. Sanitation, Linear

 

Q. 41 In the circuit shown, transistors Qi and Q2 are biased at a collector current of 2.6 nth. Assuming that transistor current gains are sufficiently large to assume collector current equal to emitter current and thermal voltage of 26 my. the magnitude of voltage gain Vo/Vs in the mid-band frequency range is (up to second decimal place).

 

Q. 42 In the voltage reference circuit shown in the figure. the op-amp is ideal and the transistors Q1,Q2… Q32 are identical in all respects and have infinitely large values of common-emitter current gain (β). The collector current (Ic) of the transistors is related to their base-emitter voltage (Vas) by the relation lc = Is exp (Yap/VT). where Is is the saturation current. Assume that the voltage Vp shown in the figure is 0.7 V and the thermal voltage VT = 26 mV. The output voltage Vout (in volts) is

 

Q. 43 The state diagram of a finite state machine (FSM) designed to detect an overlapping sequence of three bits is shown in the figure. The FSM has an input ‘In’ and an output ‘Out’. The initial state of the FSM is So.

In = 0 

Out = 0

If the input sequence is 10101101001101. starting with the left-most bit. then the number of times ‘Out’ will be 1 is

 

Q. 44 Figure I shows a 4-bit ripple carry adder realized using full adders and Figure II shows the circuit of a full-adder (FA). The propagation delay of the XOR. AND and OR gates in Figure II are 20 ns. 15 ns and 10 ns. respectively. Assume all the inputs to the 4-bit adder are initially reset to 0.

At t = 0. the inputs to the 4-bit adder are changed to X₃X₂X₁X₀ = 1100. Y₃Y₂Y₁Y₀ = 0100 and Z₀ = 1. The output of the ripple carry adder will be stable at t (in ns) =

 

Q. 45 The programmable logic array(PLA) is shown in the figure. The boolean function F is represented as

A. A

B. B

C. C

D. D

 

Q. 46 A unity feedback control system is characterized by the open-loop transfer fiction

G(s)= 2(s + 1) / s³ + ks² + 2s + 1

The value of k for which the system oscillates at 2 rac/s is

Q. 47 A second-order LTT system is described by the following state equations.

d/dt x₁(t) – x₂(t) = 0

—d/dt x₂(t) 2x₁(t) 3x₂(t) = r(t)

where x₁(t) and x₂(t) are the two state variables and r(t) denotes the input. The output c(t) = Mt) The system is

A. undamped (oscillatory)

B. underdamped

C. critically damped

D. overdamped

 

Q. 48 A unity feedback control system is characterized by the open-loop transfer function 10K(s + 2) /G(s) — s³+ 3s² + 10

The Nyquist path and the corresponding Nyquist plot of G(s) are shown in the figures

Below. If 0 < K < 1. then the number of poles of the closed-loop transfer Amnon that lie in the righthalf of the s-plane is

A. 0

B. 1

C. 2

D. 3

 

Q. 49 The signal x(t) = sin(14000n). where t is in seconds, is sampled at a rate of 9000 samples per second. The sampled signal is the input to an ideal lowpass filter with frequency response H(f) as follows:

What is the number of sinusoids in the output and their frequencies in kHz?

A. Number = 1, frequency = 7

B. Number = 3. frequencies = 2, 7,11

C. Number = 2. frequencies = 2, 7

D. Number = 2. frequencies = 7,11

 

Q. 50 The unmodulated carrier power in an AM transmitter is 5 kW. This carrier is modulated by a sinusoidal modulating signal. The maximum percentage of modulation is 50%. If it is reduced to 40%. then the maximum modulated carrier power (in kW) that can be used without overloading the transmitter is

 

Q. 51 A modulating signal given by x(t) = 5 sin(4π10³t — 10π cos 2π 10π³t) V is fed to a phase modulator with phase deviation constant kp = 5 rad/V. If the carrier frequency is 20 kHz the instantaneous frequency (in kHz) at t = 0.5 ms is

 

Q. 52 Consider a binary memoryless channel characterized by the transition probability diagram shown in the figure.

The channel is

A. lossless

B. noiseless

C. useless

D. deterministic

 

Q. 53 An electron (q₁) is moving in free space with velocity 10⁵ nils towards a stationary electron (q₂) far away. The closest distance that this moving electron gets to the stationary electron before the repulsive force diverts its path is __________x 10⁻⁸ m

[Given. mass of electron in = 9.11×10⁻³¹ kg. charge of electron e = —1.6×10⁻¹⁹ C. and

permitivity = (I/36π)10⁻⁹ F/m]

 

Q. 54 tandard air-filled rectangular waveguides of dimensions a = 2.29 cm and b = 1.02 cm are designed for radar applications. It is desired that these waveguides operate only in the dominant TE10 mode with the operating frequency at least 25% above the cutoff frequency of the TE10 mode but not higher than 95% of the next higher cutoff frequency. The range of the allowable operating frequency(f) is

A. 8.19 GHz ≤ f ≤ 13.1 GHz

B. 8.19 GHz ≤f ≤12.45 GHz

C. 6.55 GHz≤ f ≤ 13.1 GHz

D. 1.64 GHz ≤ f ≤ 10.24 GHz

 

Q. 55 The pemittivity of water at optical frequencies is 1.754. It is found that an isotropic light source at a distance a’ under water forms an illuminated circular area of radius 5 m. as shown in the figure. The critical angle is

The value of d (in meter) is

 

Q. 56 The ninth and the tenth of this month are Monday and Tuesday

A. figuratively

B. retrospectively

C. respectively

D. rightfully

 

Q. 57 It is to read this year’s textbook the last year’s.

A. easier than

B. most easy than

C. easier from

D. easiest from

 

Q. 58 A rule states that in order to drink beer. one must be over 18 years old. In a bar. there are 4 people. Rs 16 years old. Q is 25 years old. R is drinking milkshake and S is drinking a beer. What must be checked to ensure that the rule is being followed?

A. Only P’s drink

B. Only P’s drink and S’s age

C. Only S’s age

D. Only P’s drink Q’s drink and S’s age

 

Q. 59 Fatima starts from point P. goes North for 3 km. and then East for 4 km to reach point Q. She then turns to face point P and goes 15 km in that direction. She then goes Nonh for 6 km. How far is she from point P. and in which direction should she go to reach point P?

A. 8 km east

B. 12 km North

C. 6 km east

D. 10 km North

 

Q. 60 500 students are taking one or more courses out of Chemistry. Physics. and Mathematics. Registration records indicate course enrolment as follows: Chemistry (329). Physics (186). Mathematics (295). Chemistry and Physics (83). Chemistry and Mathematics (217). And Physics and Mathematics (63). How many students are taking all 3 subjects? 

A. 37

B. 43

C. 47

D. 53

 

Q. 61 “If you are looking for a history of India. or for an account of the rise and fall of the British Raj. or for the reason of the cleaving of the subcontinent into two mutually antagonistic parts and the effects this mutilation will have in the respective sections. and ultimately on Asia. you will not fad it in these pages: for though I have spent a lifetime in the country. I lived too near the seat of events. and was too intimately associated with the actors. to get the perspective needed for the impartial recording of these matters.” Which of the following statements best reflects the author’s opinion?

A. An intimate association does not allow for the necessary perspective.

B. Matters are recorded with an impartial perspective.

C. An intimate association offers an impartial perspective.

D. Actors are typically associated with the impartial recording of matters.

 

Q. 62 Each of P. Q. R. S. W. X. Y and Z has been married at most once. X and Y are married and have two children P and Q. Z is the grandfather of the daughter S of P. Further. Z and W are married and are parents of It Which one of the following must necessarily be FALSE? 

A. X is the mother-in-law of R

B. P and R are not married to each other

C. Pisa son of X and Y

D. Q cannot be married to R

 

Q. 63 1200 men and 500 women can build a bridge in 2 weeks. 900 men and 250 women will take 3 weeks to build the same bridge. How many men will be needed to build the bridge in one week?

A. 3000

B. 3300

C. 3600

D. 3900

 

Q. 64 The number of 3-digit numbers such that the digit 1 is never to the immediate right of 2 is 

A. 781

B. 791

C. 881

D. 891

 

Q. 65 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 in intervals in this plot.

Which of the following is the steepest path leaving from P?

A. P to Q

B. P to R

C. P to S

D. P to T

 

Answer Sheet
Question	1	2	3	4	5	6	7	8	9	10
Answer	4	A	54 to 55	B	0.1 to 0.21	0.12 to 2.16	C	B	C	C
Question	11	12	13	14	15	16	17	18	19	20
Answer	0.45 To 0.55	3.15 To 3.21	A	5.5 to 6.5	ABCD	B	B	0.95 to 1.05	4.99 to 5.01	D
Question	21	22	23	24	25	26	27	28	29	30
Answer	C	2.0	7.0	C	48 to 51	C	D	B	2.4 to 2.6	-100.01 to -99.99
Question	31	32	33	34	35	36	37	38	39	40
Answer	8 to 8.3	-1.01 to 0.99	7.95 to 8.05	0.45 to 0.55	7.0	6.85 to 6.95	0.51 to 0.62	B	A	C
Question	41	42	43	44	45	46	47	48	49	50
Answer	49 To 51	1.1 to 1.2	4	50.0	C	0.75 to 0.76	D	C	B	5.19 to 5.23
Question	51	52	53	54	55	56	57	58	59	60
Answer	69.9 to 70.1	C	4.55 to 5.55	B	4.2 to 4.4	C	A	B	A	D
Question	61	62	63	64	65
Answer	A	B	C	C	B

GATE 2017 Electronics and Communication Engineering Session 1

Q. 1 Consider the 5×5 matrix.

It is given that A has only one real eigenvalue. Then the real eigenvalue of A is

A. -2.5

B. 0

C. 15

D. 25

 

Q. 2 The rank of the given matrix is

A. 0

B. 1

C. 2

D. 3

 

Q. 3 Consider the following statements about the linear dependence of the real-valued

functions y1=1, y2=x and y3=x^3, over the field of real numbers. 

I. y1, y2 and y3 are linearly independent on -1<=x<=0

II. y1, y2 and y3 are linearly dependent on 0<=x<=1

III. y1, y2 and y3 are linearly independent on 0<=x<=1

IV. y1, y2 and y3 are linearly dependent on -1<=x<=0

Which one among the following is correct?

A. Both I and II are true

B. Both I and III are true

C. Both II and IV are true

D. Both III and IV are true

 

Q. 4 Three fair dice are thrown simultaneously. The probability that all three dice have the same number of dots on the faces showing up (up to third decimal place) is

 

Q. 5 Consider the following statements for continuous-time linear time invariant (LTI) systems.

I. There is no bounded input bounded output (BIBO) stable system with a pole in the right half of the complex plane.

II. There is no causal and BIBO stable system with a pole in the right half of the complex plane.

Which among the following is correct?

A. Both I and II are true.

B. Both I and II are not true.

C. Only I is true.

D. Only II is true.

 

Q. 6 Consider a single input single output discrete-time system with x[n] as input and y[n] as output, where the two are related as

y[n] = n[x[n]], for 0<=n<=10

y[n] = x[n] – x[n-1], otherwise

Which one of the following statements is true about the system?

A. It is causal and stable

B. It is causal but not stable

C. It is not causal but stable

D. It is neither causal nor stable

 

Q. 7 In the circuit shown, the positive angular frequency w (in radians per second) at which the magnitude of the phase difference between the voltages V1 and V2 equals pi/4 radians, is 

 

Q. 8 A periodic signal x(t) has a trigonometric Fourier series expansion as given.

If x(t) = – x(-t) = – x(t – pi/w0), we can conclude that

A. an are zero for all n and bn are zero for all n even

B. an are zero for all n and bn are zero for all n odd

C. an are zero for n even and bn are zero for all n odd

D. an are zero for n odd and bn are zero for all n even

 

Q. 9 A bar of Gallium Arsenide (GaAs) is doped with Silicon such that the Silicon atoms occupy Gallium abs Arsenic sites in the GaAs crystal. Which one of the following statements is true?

A. Silicon atoms act as p-type dopants in Arsenic sites and n-type dopants in Gallium sites

B. Silicon atoms act as n-type dopants in Arsenic sites and p-type dopants in Gallium sites

C. Silicon atoms act as p-type dopants in Arsenic as well as Gallium sites

D. Silicon atoms act as n-type dopants in Arsenic as well as Gallium sites

 

Q. 10 A n^+ -n Silicon device is fabricated with uniform and non-degenerate donor doping concentrations of ND1 = 1 x 10^18 cm^-3 and ND2 = 1 x 10^15 cm^-3 corresponding to the n^+ and n regions respectively, At the operational temperature T, assume complete impurity ionization, kT/q = 25 mV, and intrinsic carrier concentration to be ni = 1 x 10^10 cm^-3. What is the magnitude of the built-in potential of this device?

A. 0.748 V

B. 0.460 V

C. 0.288 V

D. 0.173 V

 

Q. 11 For a narrow base PNP BJT, the excess minority carrier concentrations (nE for emitter, pB for base, nC for collector) normalized to equilibrium minority carrier concentrations (nE0 for emitter, pB0 for base, nC0 for collector) in the quasi-neutral emitter, base and collector regions are shown. Which one of the following biasing modes is the transistor operating in?

A. Forward active

B. Saturation

C. Inverse active

D. Cutoff

 

Q. 12 For the operational amplifier circuit shown, the output saturation voltages are +15V or -15V. The upper and lower threshold voltages for the circuit are, respectively

A. +5V and -5V

B. +7V and -3V

C. +3V and -7V

D. +3V and -3V

 

Q. 13 A good transconductance amplifier should have

A. high input resistance and low output resistance

B. low input resistance and high output resistance

C. high input and output resistances

D. low input and output resistances

 

Q. 14 The Miller Effect in the context of a Common Emitter amplifier explains

A. an increase in the low-frequency cutoff frequency

B. an increase in the high-frequency cutoff frequency

C. a decrease in the low-frequency cutoff frequency

D. a decrease in the high-frequency cutoff frequency

 

Q. 15 In the latch circuit shown, the NAND gates have non-zero, but unequal propagation delays. The present input condition is: P = Q = ‘0’. If the input condition is changed simultaneously to P = Q = ‘1’, the outputs X and Y are

A. X = ‘1’, Y = ‘1’

B. either X = ‘1’, Y = ‘0’ or X = ‘0’, Y = ‘1’

C. either X = ‘1’, Y = ‘1’ or X = ‘0’, Y = ‘0’

D. X = ‘0’, Y = ‘0’

 

Q. 16 The clock frequency of an 8085 microprocessor is 5 MHz. If the time required to execute an instruction is 1.4 us, then the number of T-states needed for executing the instruction is

A. 1

B. 6

C. 7

D. 8

 

Q. 17 Consider the D-Latch shown in the figure, which is transparent when its clock input CK is high and has zero propagation delay. In the figure, the clock signal CLK1 has a 50% duty cycle and CLK2 is a one-fifth period delayed version of CLK1. The duty cycle at the output of the latch in percentage is

 

Q. 18 The open loop transfer function

G(s) = (s+1) / s^P(s+2)(s+3)

where p is an integer, is connected in unity feedback configuration as shown in the figure. Given that the steady state error is zero for unit step input and is 6 for unit ramp input, the value of the parameter p is

 

Q. 19 Consider a stable system with transfer function

G(s) = (s^p + b1s^p-1 + … + bp) / (s^q + a1s^q-1 + … + aq)

where b1, …, bp and a1, … , aq are real valued constants. The slope of the Bode log magnitude curve of G(s) converges to -60 dB/decade as x —> infinity. A possible pair of

value for p and q is

A. p = 0 and q = 3

B. p = 1 and q = 7

C. p = 2 and q = 3

D. p = 3 and q = 5

 

Q. 20 Which of the following can be the pole-zero configuration of a phase-lag controller (lag compensator)?

A. (A)

B. (B)

C. (C)

D. (D)

 

Q. 21 Let (X1, X2) be independent random variables. X1 has mean 0 and variance 1, while X2 has mean 1 and variance 4. The mutual information I(X1; X2) between X1 and X2 in bits is

 

Q. 22 Which one of the following statements about differential pulse code modulation (DPCM) is true?

A. The sum of message signal sample with its prediction is quantized

B. The message signal sample is directly quantization, and it’s prediction is not used

C. The difference of message signal sample and a random signal is quantized

D. The difference of message signal sample with its prediction is quantized

 

Q. 23 In a digital communication system, the overall pulse shape p(t) at the receiver before the sampler has the Fourier transform P(f). If the symbols are transmitted at the rate of 2000 symbols per second, for which of the following cases is the inter symbol interference zero?

A. (A)

B. (B)

C. (C)

D. (D)

 

Q. 24 The voltage of an electromagnetic wave propagating in a coaxial cable with uniform characteristic impedance is V(l) = e^(-yl+jwt) Volts, where l is the distance of the cable in metres, y = (0.1 + j40)m^-1 is the complex propagation constant, and w = 2pi x 10^9 rad/s is the angular frequency. The absolute value of the attenuation in the cable in dB/metre is

 

Q. 25 Consider a wireless communication link between a transmitter and a receiver in free space, with finite and strictly positive capacity. If the effective areas of the transmitter and the receiver antennas, and the distance between them are all doubled, and everything else remains unchanged, the maximum capacity of the wireless link

A. increases by a factor of 2

B. decreases by a factor of 2

C. remains unchanged

D. decreases by a factor of root of 2

 

Q. 26 Let f(x) = e^x+x^2 for real x. From among the following, choose the Taylor series

approximation of f(x) around x = 0, which includes all powers of x less than or equal to 3.

A. 1 + x + x^2 + x^3

B. 1 + x + 3/2 x^2 + x^3

C. 1 + x + 3/2 x^2 + 7/6 x^3

D. 1 + x + 3x^2 + 7x^3

 

Q. 27 A three dimensional region R of finite volume is described by

x^2 + y^2 <= z^3; 0 <= z <= 1,

where x, y, z are real. The volume of R (up to two decimal places) is

 

Q. 28 Let C be the straight line segment from point A: (0, 2, 1) to point B: (4, 1, -1). The value of I is

 

Q. 29 Which one of the following is the general solution of the first order differential equation dy/dx = (x + y + 1)^2, where x, y are real?

A. y = 1 + x + tan^-1(x + c), where c is a constant.

B. y = 1 + x + tan(x + c), where c is a constant.

C. y = 1 – x + tan^-1(x + c), where c is a constant.

D. y = 1 – x + tan(x + c), where c is a constant.

 

Q. 30 Starting with x = 1, the solution of the equation x^3 + x = 1, after two iterations of Newton- Raphson’s method (up to two decimal places)0 is

 

Q. 31 Let x(t) be a continuous time periodic signal with fundamental period T = 1 seconds. Let {ak} be the complex Fourier series coefficients of x(t), where k is integer valued. Consider the following statements about x(3t):

I. The complex Fourier series coefficients of x(3t) are {ak} where k is integer valued

II. The complex Fourier series coefficients of x(3t) are {3ak} where k is integer valued

III. The fundamental angular frequency of x(3t) is 6pi rad/s

For the three statements above, which one of the following is correct?

A. only II and III are true

B. only I and III are true

C. only III is true

D. only I is true

 

Q. 32 Two discrete-time signals x[n] and h[n] are both non-zero only for n = 0, 1, 2, and are zero otherwise. It is given that

x[0] = 1, x[1] = 2, x[2] = 1, h[0] = 1.

Let y(n) be the linear convolution of x[n] and h[n]. Given that y[1] = 3 and y[2] = 4, the value of the expression (10y[3] + y[4]) is

 

Q. 33 Let h[n] be the impulse response of a discrete-time linear time invariant (LTII) filter. The impulse response is given by

h[0] = 1/3; h[1] = 1/3; and h[n] = 0 for n < 0 and n > 2.

Let H(w) be the discrete-time Fourier transform (DTFT) of h[n] where w is the normalized angular frequency in radians. Given that H(w0) = 0 and 0 < w0 < pi, the value of w0 (in radians) is equal to

 

Q. 34 The figure shows an RLC circuit excited by the sinusoidal voltage 100cos(3t) Volts, where t is in seconds. The ratio amplitude of V2/amplitude of V1 is

 

Q. 35 In the circuit shown, the voltage Vin(t) is described by:

Vin(t) = 0, for t < 0

Vin(t) = 15 Volts, for t >= 0

where t is in seconds. The time (in seconds) at which the current I in the circuit will reach the value 2 Amperes is

 

Q. 36 The dependence of drift velocity of electrons on electric field in a semiconductor is shown. The semiconductor has a uniform electron concentration of n = 1 x 10^16 cm^-3 and electronic charge q = 1.6 x 10^-19 C. If a bias of 5 V is applied across a 1 um region of this semiconductor, the resulting current density in this region, in kA/cm^2, is

 

Q. 37 As shown, a uniformly doped silicon (Si) bar of length L = 0.1 um with a donor concentration ND = 10^16 cm^-3 is illuminated at x = 0 such that electron and hole pairs are generated at the rate of GL = GL0 (1 – x/L0, 0 <=x<=L, where GL0 = 10^17 cm^-3 s^-1. Hole lifetime is 10^-4 s, electronic charge q = 1.6 x 10^-19 C, hole diffusion coefficient DP = 100 cm^2/s and low level injection condition prevails. Assuming a linearly decaying steady state excess hole concentration that goes to 0 at x = L, the magnitude of the diffusion current density at x = L/2, in A/cm^2, is

 

Q. 38 As shown, two Silicon (Si) abrupt p-n junction diodes are fabricated with uniform donor doping concentrations of ND1 = 10^14 cm6-3 and ND2 = 10^16 cm^-3 in the n-regions, and uniform acceptor doping concentrations of NA1 = 10^14 cm^-3 and NA2 = 10^16 cm^-3 in the p-regions of the diodes, respectively. Assuming that the reverse bias voltage is >> builtin potentials of the diodes, te ratio C2/C1 of their reverse bias capacitances for the same applied reverse bias, is

Q. 39 In the figure shown, the npn transistor acts as a switch. For the input Vin(t) as shown in the figure, the transistor switches between the cut-off and saturation regions of operation, when T is large. Assume collector-to-emitter voltage at saturation VCE(sat) = 0.2 V and base-to-emitter voltage VBE = 0.7 V. The minimum value of the common-base current gain of the transistor for the switching should be

 

Q. 40 For the circuit shown, assume that the NMOS transistor is in saturation. Its threshold voltage Vtn = 1 V and its transconductance parameter is 1 mA/V^2. Neglect channel length modulation and body bias effects. Under these conditions, the drain current ID in mA is 

 

Q. 41 For the DC analysis of the Common-Emitter amplifier shown, neglect the base current and assume that the emitter and collector currents are equal. Given that VT = 25 mV, VBE = 0.7 V, and the BJT output resistance ro is practically infinite. Under these conditions, the midband voltage gain magnitude, Av = |vo/vi| V/V, is

 

Q. 42 The amplifier circuit shown in the figure is implemented using a compensated operational amplifier (op-amp), and has an open-loop voltage gain, A0 = 10^5 V/V and an open-loop cutoff frequency, fc = 8 Hz. The voltage gain of the amplifier at 15 kHz, in V/V, is 

 

 

Q. 43 Which one of the following gives the simplified sum of products expression for the Boolean function F = m0 + m2 + m3 + m5, where m0, m2, m3 , m5 are minterms corresponding to the inputs A, B and C with A as the MSB and C as the LSB?

A. (A)

B. (B)

C. (C)

D. (D)

 

Q. 44 A 4-bit shift register circuit configured for right-shift operation, i.e. Din —-> A, A —-> B, B —- > C, C —-> D, is shown. If the present state of the shift register is ABCD = 1101, the number of clock cycles required to reach the state ABCD = 1111 is

 

Q. 45 The following FIVE instructions were executed on 8085 microprocessor.

MVI A 33H

MVI B 78H

ADD B

CMA

ANI 32H

The Accumulator value immediately after the execution of the fifth instruction is

A. 00H

B. 10H

C. 11H

D. 32H

 

Q. 46 A finite state machine (FSM) is implemented using the D flip-flops A and B, and logic  gates, as shown in the figure. The four possible states of the FSM are QAQB = 00, 01, 10 and 11. Assume that Xin is held at a constant logic level throughout the operation of the FSM. When the FSM is initialized to the state QAQB = 00 and clocked, after a few clock cycles, it starts cycling through

A. all of the four possible states if Xin = 1

B. three of the four possible states if Xin = 0

C. only two of the four possible states if Xin = 1

D. only two of the four possible states if Xin = 0

 

Q. 47 A linear time invariant (LTI) system with the transfer function

G(s) = K(s62 + 2s + 2) / (s^2 – 3s + 2)

is connected in unity feedback configuration as shown in the figure. For the closed loop system shown, the root locus for 0 < K < infinity intersects the imaginary axis for K = 1.5. The closed loop system is stable for

A. K > 1.5

B. 1 < K < 1.5

C. 0 < K < 1

D. no positive value of K

 

Q. 48 Which one of the following options correctly describes the location of the roots of the equation

s^4 + s^2 +1 = 0

on the complex plane?

A. Four left half plane (LHP) roots

B. One right half plane (RHP) root, one LHP root, and two roots on the imaginary axis

C. Two RHP roots and two LHP roots

D. All four roots are on the imaginary axis

 

Q. 49 The Nyquist plot of the transfer function

G(s) = K / (s^2 + 2s + 2)(s + 2)

does not encircle the point (-1 + j0) for K=10 but does encircle the point (-1 + j0) for K=100. Then the closed loop system (having unity gain feedback) is

A. stable for K=10 and stable for K=100

B. stable for K=10 and unstable for K=100

C. unstable for K=10 and stable for K=100

D. unstable for K=10 and unstable for K=100

 

Q. 50 In binary frequency shift keying (FSK), the given signal waveforms are

u0(t) = 5cos(20000(pi)t); 0<=t<=T, and

u1(t) = 5cos(22000(pi)t); 0<=t<=T,

where T is the bit-duration interval and t is in seconds. Both u0(t) and u1(t) are zero outside the interval 0<=t<=T. With a matched filter (correlator) based receiver, the smallest positive value of T (in milliseconds) required to have u0(t) and u1(t) uncorrelated is 

A. 0.25 ms

B. 0.5 ms

C. 0.75 ms

D. 1.0 ms

 

Q. 51 Let X(t) be a wide sense stationary random process with the power spectral density Sx(f) as shown in figure (a), where f is in Hertz (Hz). The random process X(t) is input to an ideal lowpass filter with the frequency response

H(f)) = 1, |f| <= 1/2 Hz

H(f) = 0, |f| > 1/2 Hz

as shown in Figure (b). The output of the lowpass filter is Y(t).

Let E be the expectation operator and consider the following statements:

I. E(X(t)) = E(Y(t))

II. E(X^2(t)) = E(Y^2(t))

III. E(Y^2(t)) = 2

Select the correct option:

A. only I is true

B. only II and III are true

C. only I and II are true

D. only I and III are true

 

Q. 52 A continuous time signal x(t) = 4cos(200(pi)t) + 8cos(400(pi)t), where t is in seconds, is the output to a linear time invariant (LTI) filter with the impulse response

h(t) = 2sin(300(pi)t)/pi(t), t is not = 0

h(t) = 600, t = 0

Let y(t) be the output of this filter. The maximum value of |y(t)| is

 

Q. 53 An optical fiber is kept along the z direction. The refractive indices for the electric fields along x and y directions in the fiber are nx = 1.5000 and ny = 1.5001, respectively (nx is not equal to ny due to the imperfection in the cross-section). The free space wavelength of a light wave propagating in the fiber is 1.5um. If the light wave is circularly polarized at the input of the fiber, the minimum propagation distance after which it becomes linearly polarized, in centimeters, is

 

Q. 54 The expression for an electric field in free space is given, where x, y, z represent the spatial coordinates, t represents time, and w, k are constants. This electric field

A. does not represent a plane wave

B. represents a circularly polarized plane wave propagating normal to the z-axis

C. represents an elliptically polarized plane wave propagating along the x-y plane

D. represents a linearly polarized plane wave

 

Q. 55 A half wavelength dipole is kept in the x-y plane and oriented along 45 degrees from the xaxis. Determine the direction of null in the radiation pattern for 0 <= x <= pi. Here the angle y (0 <= y <= pi) is measured from the z-axis, and the angle x (0 <= x <= 2pi) is measured from the x-axis in the x-y plane.

A. y = 90 degrees, x = 45 degrees

B. y = 45 degrees, x = 90 degrees

C. y = 90 degrees, x = 135 degrees

D. y = 45 degrees, x = 135 degrees

 

Q. 56 She has a sharp tongue and it can occasionally turn ______

A. hurtful

B. left

C. methodical

D. vital

 

Q. 57 I _____ made arrangements had I _____ informed earlier.

A. could have, been

B. would have, being

C. had, have

D. had been, been

 

Q. 58 In the summer, water consumption is known to decrease overall by 25%. A Water Boars official states that in the summer household consumption decreases by 20%, while other consumption increases by 70%

Which of the following statements is correct?

A. The ratio of household to other consumption is 8/17

B. The ratio of household to other consumption is 1/17

C. The ratio of household to other consumption is 17/8

D. There are errors in the official’s statement

 

Q. 59 40% of deaths on city roads may be attributed to drunk driving. The number of degrees needed to represent this as a slice of a pie chart is

A. 120

B. 144

C. 160

D. 212

 

Q. 60 Some tables are shelves. Some shelves are chairs. All chairs are benches. Which of the following conclusions can be deduced from the previous sentences?

i. At least one bench is a table

ii. At least one shelf is a bench

iii. At least one chair is a table

iv. All benches are chairs

A. Only i

B. Only ii

C. Only ii and iii

D. Only iv

 

Q. 61 “If you are looking for a history of India, or for an account of the rise and fall of the British Raj, or for the reason of the cleaving of the subcontinent into two mutually antagonistic parts and the effect this mutilation will have on the respective sections, and ultimately on Asia, you will not find it in these pages; for though I have spent a lifetime in this country, I lived too near the seat of events, and was too intimately associated with the actors, to get the perspective needed for the impartial recording of these matters”. Here, the word ‘antagonistic’ is closest in meaning to

A. impartial

B. argumentative

C. separated

D. hostile

 

Q. 62 S, T, U, V, W, X, Y and Z are seated around a circular table. T’s neighbours are Y and V. Z is seated this to the left of T and second to the right of S. U’s neighbours are S and Y; and T and W are not seated opposite each other. Who is third to the left of V?

A. X

B. W

C. U

D. T

 

Q. 63 Trucks (10m long) and cars (5m long) go on a single lane bridge. There must be a gap of at least 20m after each truck and a gap of at least 15m after each car. Trucks and cars travel at a speed of 36km/h. If cars and trucks go alternately, what is the maximum number of vehicles that can use the bridge in one hour?

A. 1440

B. 1200

C. 720

D. 600

 

Q. 64 There are 3 Indians and 3 Chinese in a group of 6 people. How many subgroups of this group can we choose so that every subgroup has at least one Indian?

A. 56

B. 52

C. 48

D. 44

 

Q. 65 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 25m intervals in this plot. The path from P to Q is best described by

A. Up-Down-Up-Down

B. Down-Up-Down-Up

C. Down-Up-Down

D. Up-Down-Up

 

Answer Sheet
Question	1	2	3	4	5	6	7	8	9	10
Answer	C	C	B	0.027 To 0.028	D	A	0.9 to 1.1	A	A	D
Question	11	12	13	14	15	16	17	18	19	20
Answer	C	B	C	D	B	C	29.9 to 30.1	0.991 to 0.88	C	C
Question	21	22	23	24	25	26	27	28	29	30
Answer	0	D	B	0.85 to 0.88	C	C	0.7 to 0.88	C	C	0.7 To 0.85
Question	31	32	33	34	35	36	37	38	39	40
Answer	D	31	2.05 to 2.15	2.55 to 2.65	0.3 to 0.4	1.5 to 1.7	15.9 to 16.1	10	0.89 to 0.91	1.9 to 2.1
Question	41	42	43	44	45	46	47	48	49	50
Answer	127 To 129	43.3 to 45.3	B	10	B	D	A	C	B	B
Question	51	52	53	54	55	56	57	58	59	60
Answer	A	7.9 to 8.1	0.36 to 0.38	C	A	A	A	D	B	B
Question	61	62	63	64	65
Answer	D	A	A	A	C

GATE 2017 Computer Science and Information Technology Session 2

Q. 1 The representation of the value of a 16−bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is

A. 571244

B. 736251

C. 571247

D. 136251

 

Q. 2 Match the following:

A. P-ii; Q-iv; R-i; S-iii

B. P-ii; Q-i; R-iv; S-iii

C. P-ii; Q-iv; R-iii; S-i

D. P-iii; Q-iv; R-i; S-ii

 

Q. 3 Match the algorithms with their time complexities:

A. P→ (iii) Q → (iv) r →(i) S →(ii)

B. P→ (iv) Q →(iii) r →(i) S→(ii)

C. P→ (iii) Q →(iv) r →(ii) S→(i)

D. P→ (iv) Q →(iii) r →(ii) S→(i)

 

Q. 4 Let L₁, L₂ be any two context-free languages and R be any regular language. Then which of the following is/are correct.

1- L₁, L₂ is context-free

2- L₁ is context-free

3- L₁-R is context-free

4- L₁ ∩ L₂ is context-free

A. 1, 2 and 4 only

B. 1 and 3 only

C. 2 and 4 only

D. 1 only

 

Q. 5 Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:

A. P-ii; Q-iii; R-iv; S-i

B. P-ii; Q-i; R-iii; S-iv

C. P-iii; Q-iv; R-i; S-ii

D. P-i; Q-iv; R-ii; S-iii

 

Q. 6 Which of the following statements about parser is/are CORRECT?

I.Canonical LR is more powerful than SLR

II.SLR is more powerful than LALR

III.SLR is more powerful than Canonical LR

A. I only

B. II only

C. III only

D. II and III only

 

Q. 7 Which of the following is/are shared by all the threads in a process?

I.Program counter

II.Stack

III.Address space

IV.Registers

A. I and II only

B. III only

C. IV only

D. III and IV only

 

Q. 8 In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed ?

1.Contiguous

2.Linked

3.Indexed

A. 1 and 3 only

B. 2 only

C. 3 only

D. 2 and 3 only 8

 

Q. 9 Consider the following statements about the routing protocols. Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) in an IPv4 network.

I.RIP uses distance vector routing

II.RIP packets are sent using UDP

III.OSPF packets are sent using TCP

IV.OSPF operation is based on link-state routing

Which of the above statements are CORRECT?

A. I and IV only

B. I, II and III only

C. I, II and IV only

D. II, III and IV only

 

Q. 10 If, then the constants R and S are

A. 2/π and 16/π

B. 2/π and 0

C. 4/π and 0

D. 4/π and 16/π

 

Q. 11 Let p,q,r denote the statements ”It is raining”, “It is cold”, and “It is pleasant”, respectively. Then the statement “It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by

A. (¬p∧r)∧(¬r→(p∧q))

B. (¬p∧r)∧((p∧q)→¬r)

C. (¬p∧r)∨((p∧q)→¬r)

D. (¬p∧r)∨(r→(p∧q))

 

Q. 12 Given the following binary number in 32-bit (single precision) IEEE−754 format : 00111110011011010000000000000000

The decimal value closest to this floating-point number is :

A. 1.45∗10¹

B. 1.45∗10⁻¹

C. 2.27∗10⁻¹

D. 2.27∗10¹

 

Q. 13 A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time?

I.Next pointer of front node points to the rear node.

II.Next pointer of rear node points to the front node

A. (I) only.

B. (II) only.

C. Both (I) and (II).

D. Neither (I) nor (II).

 

Q. 14 Consider the following function implemented in C:

void print xy(int x, int y) {

int *ptr;

x=0;

ptr=&x;

y=*ptr;

*ptr=1;

printf(“%d, %d”, x, y);

}

The output of invoking printxy(1,1) is

A. 0,0

B. 0,1

C. 1,0

D. 1,1

 

Q. 15 The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?

A. MNOPQR

B. NQMPOR

C. QMNROP

D. POQNMR

 

Q. 16 Identify the language generated by the following grammar, where S is the start variable. 

S→XY

X→aX∣a

Y→aYb∣ϵ

A. A

B. B

C. C

D. D

 

Q. 17 An ER model of a database consists of entity types A and B. These are connected by a relationship R which does not have its own attribute. Under which one of the following conditions, can the relational table for R be merged with that of A?

A. Relationship R is one-to-many and the participation of A in R is total

B. Relationship R is one-to-many and the participation of A in R is partial

C. Relationship R is many-to-one and the participation of A in R is total

D. Relationship R is many-to-one and the participation of A in Ris partial

 

Q. 18 Consider socket API on a Linux machine that supports connected UDP sockets. A connected UDP socket is a UDP socket on which connect function has already been called. Which of the following statements is/are CORRECT?

I.A connected UDP socket can be used to communicate with multiple peers simultaneously.

II.A process can successfully call connect function again for an already connected UDP socket

A. I only

B. II only

C. Both I and II

D. Neither I nor II

 

Q. 19 Consider the following tables T1 and T2.

In table T1. P is the primary key and Q is the foreign key referencing R in table T2 with on delete cascade and on-update cascade. In table T2, R is the primary key and S is the foreign key referencing P in table T1 with on-delete set NULL and on-update cascade. In order to delete record ⟨3,8⟩ from the table T1, the number of additional records that need to be deleted from table T1 is _______

 

Q. 20 The maximum number of IPv4 router addresses that can be listed in the record route (RR) option field of an IPv4 header is______

 

Q. 21 Consider the set X={a,b,c,d,e}

under partial ordering R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}

The Hasse diagram of the partial order (X,R) is shown below.

The minimum number of ordered pairs that need to be added to R to make (X,R) a lattice is ______

 

Q. 22 Then the rank of P+Q is ___________ . for the given matrices

 

Q. 23 G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is _________ .

 

Q. 24 Consider the quadratic equation x²−13x+36=0 with coefficients in a base b. The solutions of this equation in the same base b are x=5 and x=6. Then b= _____

 

Q. 25 The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = {w1aw2 | w1,w2 ∈ {a,b}∗ , |w1|=2,|w2|≥3} is ______________ .

 

Q. 26 P and Q are considering to apply for a job. The probability that P applies for the job is 1/4, the probability that P applies for the job given that Q applies for the job is 1/2, and the probability that Q applies for the job given that P applies for the job is 1/3. Then the probability that P does not apply for the job given that Q does not apply for this job is 

A. 4/5

B. 5/6

C. 7/8

D. 11/12

 

Q. 27 If w, x, y and z are boolean variables, then which of the following are incorrect.

A. (A)

B. (B)

C. (C)

D. (D)

 

Q. 28 Given f(w,x,y,z)=Σm(0,1,2,3,7,8,10)+Σd(5,6,11,15); where d represents the ‘don’t-care’ condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of f(w,x,y,z)?

A. f=(w¯+z¯)(x¯+z)

B. f=(w¯+z)(x+z)

C. f=(w+z)(x¯+z)

D. f=(w+z¯)(x¯+z)

 

Q. 29 In a two-level cache system, the access times of L1 and L2 caches are 1 and 8 clock cycles, respectively. The miss penalty from the L2 cache to main memory is 18 clock cycles. The miss rate of L1 cache is twice that of L2. The average memory access time (AMAT) of this cache system is 2 cycles. The miss rates of L1 and L2 respectively are

A. 0.111 and 0.056

B. 0.056 and 0.111

C. 0.0892 and 0.1784

D. 0.1784 and 0.0892

 

Q. 30 Consider the recurrence function

Then T(n) in terms of θ notation is

A. θ(loglogn)

B. θ(logn)

C. θ(√n)

D. θ(n)

 

Q. 31 For any discrete random variable X, with probability mass function

define the polynomial function

For a certain discrete random variable Y, there exists a scalar β∈[0,1] such that gy(z)=(1−β +βz)^N. The expectation of Y is

A. Nβ(1−β)

B. Nβ

C. N(1−β)

D. Not expressible in terms of N and β alone

 

Q. 32 Consider the following expression grammar G:

E→E−T∣T

T→T+F∣F

F→(E)∣id

Which of the following grammars is not left recursive, but is equivalent to G?

A. E→E−T∣T T→T+F∣FF→(E)∣id

B. E→TE′ E′→−TE′∣ϵ T→T+F∣F F→(E)∣id

C. E→TX X→−TX∣ϵ T→FY Y→+FY∣ϵ F→(E)∣id

D. E→TX∣(TX) X→−TX∣+TX∣ϵ T→id

 

Q. 33 A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for that processes are shown below:

Which of the following best describes current state of the system?

A. Safe, Deadlocked

B. Safe, Not Deadlocked

C. Not Safe, Deadlocked

D. Not Safe, Not Deadlocked

 

Q. 34 Consider the binary code that consists of only four valid codewords as given below: 00000, 01011, 10101, 11110

Let the minimum Hamming distance of the code p and the maximum number of erroneous bits that can be corrected by the code be q. Then the values of p and q are

A. p=3 and q=1

B. p=3 and q=2

C. p=4 and q=1

D. p=4 and q=2

 

Q. 35 Consider two hosts X and Y, connected by a single direct link of rate 10⁶ bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2×10⁸ m/sec. Host X sends a file of 50,000 bytes as one large message to host Y continuously. Let the transmission and propagation delays be p milliseconds and q milliseconds respectively. Then the value of p and q are

A. p =50 and q=100

B. p =50 and q=400

C. p=100 and q=50

D. p =400 and q=50

 

Q. 36 The pre-order traversal of a binary search tree is given by 12,8,6,2,7,9,10,16,15,19,17,20. Then the post-order traversal of this tree is

A. 2,6,7,8,9,10,12,15,16,17,19,20

B. 2,7,6,10,9,8,15,17,20,19,16,12

C. 7,2,6,8,9,10,20,17,19,15,16,12

D. 7,6,2,10,9,8,15,16,17,20,19,12

 

Q. 37 Consider the C program fragment below which is meant to divide x by y using repeated subtractions. The variables x, y, q and r are all unsigned int.

while (r >= y) {

r=r-y;

q=q+1;

}

Which of the following conditions on the variables x,y,q and r before the execution of the fragment will ensure that the loop terminated in a state satisfying the condition x==(y∗q+r)?

A. (q==r) && (r==0)

B. (x>0) && (r==x) && (y>0)

C. (q==0) && (r==x) && (y>0)

D. (q==0) && (y>0)

 

Q. 38 Consider the following C function

int fun(int n) {

int I, j;

for(i=1; i<=n; i++) {

for (j=1; j printf(“%d %d”, I, j);

}

}

}

Time complexity of fun in terms of Θ notation is

A. Θ(n√n)

B. Θ(n²)

C. Θ(nlogn)

D. Θ(n²logn)

 

Q. 39 Let δ denote the transition function and δˆ denote the extended transition function of the ϵ-NFA whose transition table is given below:

Then δˆ(q2,aba) is

A. ∅

B. {q0,q1,q3}

C. {q0,q1,q2}

D. {q0,q2,q3}

 

Q. 40  Consider the following languages.

Which of the following are CORRECT?

I.L₁ is context free but not regular

II.L₂ is not context free

III.L₃is not context free but recursive

Iv.L₄ is deterministic context free

A. I, II and IV only

B. II and III only

C. I and IV only

D. III and IV only

 

Q. 41 Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable?

I.Given a regular expression R and a string w, is w∈L(R)?

II.Given a context-free grammar G, is L(G)=∅

III.Given a context-free grammar G, is L(G)=Σ∗ for some alphabet Σ?

IV.Given a Turing machine M and a string w, is w∈L(M)?

A. I and IV only

B. II and III only

C. II, III and IV only

D. III and IV only

 

Q. 42 The next state table of a 2-bit saturating up-counter is given below.

The counter is built as a synchronous sequential circuit using T flip-flops. The expressions for T1 and T0 are

A. A

B. B

C. C

D. D

 

Q. 43 Consider the following snippet of a C program. Assume that swap (&x,&y) exchanges the content of x and y:

int main () {

int array[] = {3, 5, 1, 4, 6, 2};

int done =0;

int i;

while (done==0) {

done =1;

for (i=0; i<=4; i++) {

if (array[i] < array[i+1]) {

swap(&array[i], &array[i+1]);

done=0;

}

}

for (i=5; i>=1; i–) {

if (array[i] > array[i-1]) {

swap(&array[i], array[i-1]);

done =0;

}

}

}

printf(“%d”, array[3]);

}

The output of the program is _______

 

Q. 44 Two transactions T1 and T2 are given as

T1:r1(X)w1(X)r1(Y)w1(Y)

T2:r2(Y)w2(Y)r2(Z)w2(Z)

where ri(V) denotes a read operation by transaction Ti on a variable V and wi(V) denotes a write operation by transaction Ti on a variable V. The total number of conflict serializable schedules that can be formed by T1 and T2 is ______

 

Q. 45 The read access times and the hit ratios for different caches in a memory hierarchy are as given below:

The read access time of main memory in 90 nanoseconds. Assume that the caches use the referred-word-first read policy and the write-back policy. Assume that all the caches are direct mapped caches. Assume that the dirty bit is always 0 for all the blocks in the caches. In execution of a program, 60% of memory reads are for instruction fetch and 40% are for memory operand fetch. The average read access time in nanoseconds (up to 2 decimal places) is _________

 

Q. 46 Consider the following database table named top_scorer.

Consider the following SQL query:

SELECT ta.player FROM top_scorer AS ta

WHERE ta.goals >ALL (SELECT tb.goals

FROM top_scorer AS tb

WHERE tb.country = ‘Spain’)

AND ta.goals > ANY (SELECT tc.goals

FROM top_scorer AS tc

WHERE tc.country=’Germany’)

The number of tuples returned by the above SQL query is ______

 

Q. 47 If the ordinary generating function of a sequence ….

then then a₃−a₀ is equal to ___________ .

 

Q. 48 If a random variable X has a Poisson distribution with mean 5, then the expectation E[(x+2)²] equals ___.

 

Q. 49 In a B+ Tree , if the search-key value is 8 bytes long , the block size is 512 bytes and the pointer size is 2 B , then the maximum order of the B+ Tree is ____

 

Q. 50 A message is made up entirely of characters from the set X={P,Q,R,S,T}. The table of probabilities for each of the characters is shown below:

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is ______.

 

Q. 51 Consider the set of process with arrival time ( in milliseconds ) , CPU burst time ( in milliseconds) and priority ( 0 is the highest priority ) shown below . None of the process have I/O burst time The average waiting time (in milliseconds) of all the process using preemptive priority scheduling algorithm is ______

 

Q. 52 If the characteristic polynomial of a 3 × 3 matrix M over R (the set of real numbers) is λ³–4λ² +aλ+30,a∈R , and one eigenvalue of M is 2, then the largest among the absolute values of the eigenvalues of M is _______

 

Q. 53 Consider a machine with a byte addressable main memory of 2³² bytes divided into blocks of size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with this machine. The size of the tag field in bits is _______

 

Q. 54 Consider the following C program.

#include

int main () {

int m=10;

int n, n1;

n=++m;

n1=m++;

n–;

–n1;

n-=n1;

printf(“%d”, n);

return 0;

}

The output of the program is ______

 

Q. 55 Consider the following C program.

#include

#include

int main() {

char* c=”GATECSIT2017”;

char* p=c;

printf(“%d”, (int)strlen(c+2[p]-6[p]-1));

return 0;

}

The output of the program is _______

 

Q. 56 Choose the options with the words that are not synonyms

A. aversion , dislike

B. luminious , radiant

C. plunder,loot

D. yeinding ,resistant

 

Q. 57 Saturn is ________ to be seen on a clear night with the naked eye .

A. enough bright

B. bright enough

C. as enough bright

D. bright as enough

 

Q. 58 There are 5 building V,W,X,Y and Z in a row .V is the west of W.Z is east of X and west of V.W is the west of Y .Which is the building in the middle .?

A. V

B. W

C. X

D. Y

 

Q. 59 A test has 20 questions with 100 marks in total.There are 2 types of questions.Multiple choice questions are 3 marks each and essay questions are 11 marks each .How many multiple choice questions does the paper have ?

A. 12

B. 15

C. 18

D. 19

 

Q. 60 There are 3 red socks, 4 green socks,and 3 blue socks.You choose 2 socks.The probability that they are same color ?

A. 1/5

B. 7/30

C. 1/4

D. 4/15

 

Q. 61 We lived in a culture that that denied any merit to literary works , considering that

considering them important only when they were handmaidens to something seemingly more urgent -namely ideology .This was a country where all gestures even most private were interrupted in the political terms. The authors belief that ideology is not as important as literature is revealed by the word

A. Culture

B. seemingly

C. urgent

D. political

 

Q. 62 There are 3 boxes one contains apples another contains oranges and the last one contains both apples and oranges .All three are known to be perfectly labelled .If you are permitted to open just one box and then pull out and inspect only one fruit .Which box would you open to determine the contents of all three boxes.

A. The box labelled “Apples “

B. The box labelled “Apples and oranges “

C. The box labelled ” oranges “

D. cannot be determined

 

Q. 63 X is a 30 digit number starting with the digit 4 following by the digit 7 .The number x³ will have

A. 90 digits

B. 91 digits

C. 92 digits

D. 93 digits

 

Q. 64 The number of roots of e^x+0.5x²-2 =0 in the range [-5,5] is

A. 0

B. 1

C. 2

D. 3

 

Q. 65 An air pressure contour line joins locations in the region having the same atmospheric pressure .The following is an air pressure contour plot of a geographical region .Contour lines are shown in 0.05 bar intervals in this plot.

If the possibility of a thunderstorm is given by how fast air pressure rises drops over a

region .Which of the following is most likely to have a thunderstorm ?

A. P

B. Q

C. R

D. S

 

Answer Sheet
Question	1	2	3	4	5	6	7	8	9	10
Answer	D	A	C	B	C	A	B	D	C	C
Question	11	12	13	14	15	16	17	18	19	20
Answer	A	C	B	C	D	C	C	B	0	9
Question	21	22	23	24	25	26	27	28	29	30
Answer	-0.01 To 0.01	2	16	8	8	A	C	A	A	B
Question	31	32	33	34	35	36	37	38	39	40
Answer	B	C	B	A	D	B	C	C	C	D
Question	41	42	43	44	45	46	47	48	49	50
Answer	D	B	3	54	4.72	7	15	54	52	225
Question	51	52	53	54	55	56	57	58	59	60
Answer	29	5	18	0	2	D	B	A	D	B
Question	61	62	63	64	65
Answer	B	B	A	C	C

GATE 2017 Computer Science and Information Technology Session 1

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

A. I only

B. I and IV only

C. II only

D. II and III only

 

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

A. IV only

B. I and IV only

C. II only

D. II and III only

 

Q. 3 Let c_1, …, c_n be scalars, not all zero, such that for i = 0 to n, Σ c_i a_i = 0 where a_i are column vectors in R^n. Consider the set of linear equations Ax = b where A = [a_1 , … , a_n] and b = Σ a_i for i = 1 to n. The set of equations has

A. a unique solution at x = J_n where J_n denotes an n-dimensional vector of all 1

B. no solution

C. infinitely many solutions

D. finitely many solutions

 

Q. 4 Consider the following functions from positive integers to real numbers:

10, √n, n, log2 n, 100/n.

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is

A. log2 n, 100/n, 10, √n, n

B. 100/n, 10, log2 n, √n, n

C. 10, 100/n, √n, log2 n, n

D. 100/n, log2 n, 10, √n, n

 

Q. 5 Consider the given table. Match the algorithms to the design paradigms they are based on. 

A. (P) ↔ (ii); (Q) ↔ (iii); (R) ↔ (i)

B. (P) ↔ (iii); (Q) ↔ (i); (R) ↔ (ii)

C. (P) ↔ (ii); (Q) ↔ (i); (R) ↔ (iii)

D. (P) ↔ (i); (Q) ↔ (ii); (R) ↔ (iii)

 

Q. 6 Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are:

**The height of a tree with a single node is 0.

A. 4 and 15 respectively.

B. 3 and 14 respectively.

C. 4 and 14 respectively.

D. 3 and 15 respectively.

 

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

A. 2^(-f) to 2^i

B. 2^(-f) to [2^i – 2^(-f)]

C. 0 to 2^i

D. 0 to [2^i – 2^(-f)]

 

Question 8

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;

}

 

Q. 8 Consider the given C code fragment. Assuming that m and m point to valid NULLterminated linked lists, invocation of join will 

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

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

C. cause a null pointer dereference for all inputs.

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

 

Q. 9 When two 8-bit numbers A_7 … A_0 and B_7 … B_0 in 2’s complement representation (with A_0 and B_0 as the least significant bits) are added using a ripple-carry adder, the sum bits obtained are S_7 … S_0 and the carry bits are C_7 … C_0. An overflow is said to have occurred if

A. the carry bit C_7 is 1

B. all the carry bits (C_7, …, C_0) are 1

C. (A_7 . B_7 . (S_7)’ + (A_7)’ . (B_7)’ . S_7) is 1

D. (A_0 . B_0 . (S_0)’ + (A_0)’ . (B_0)’ . S_0) is 1

 

Q. 10 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 one of the following represents the language generated by the above grammar?

A. {(ab)^n (cb)^n | n ≥ 1}

B. {(ab)^n (cb)^m1 (cb)^m2 … (cb)^mn | n, m1, m2, … , mn ≥ 1}

C. {(ab)^n ((cb)^m)^n | m, n ≥ 1}

D. {(ab)^n ((cb)^n)^m | m, n ≥ 1}

 

Question 11

struct data {

int marks[100];

char grade;

int cnumber;

};

struct data student;

 

Q. 11 Consider the given C struct. The base address of student is available in register R1. The field student.grade can be accessed efficiently using

A. Post-increment addressing mode, (R1)+

B. Pre-decrement addressing mode, -(R1)

C. Register direct addressing mode, R1

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

 

Q. 12 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 form of the above code?

A. p1 = a – b q1 = p1 * c p1 = u * v q1 = p1 + q1

B. p3 = a – b q4 = p3 * c p4 = u * v q5 = p4 + q4

C. p1 = a – b q1 = p2 * c p3 = u * v q2 = p4 + q3

D. p1 = a – b q1 = p * c p2 = u * v q2 = p + q

 

Question 13

#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 0;

x = assignval (x, 10);

}

printf (“%d\n”, *x);

free (x);

}

 

Q. 13 Consider the given C code. The code suffers from which one of the following problems?

A. compiler error as the return of malloc is not typecast appripriately

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

C. compiles successfully but execution may result in dangling pointer

D. compiles successfully but execution may result in memory leak

 

Q. 14 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? 

A. LAST-ACK

B. TIME-WAIT

C. FIN-WAIT-1

D. FIN-WAIT-2

 

Q. 15 A sender sends a message m to receiver R, which is digitally signed by S with its private key. In the scenario, one or more of the following security violations 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.

Which one of the following are possible security violations?

A. (I) and (II) only

B. (I) only

C. (II) only

D. (II) and (III) only

 

Q. 16 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?

A. V → W V → X Y → V Y → Z

B. V → W W → X Y → V Y → Z

C. V → W V → X Y → V Y → X Y → Z

D. V → W W → X Y → V Y → X Y → Z

 

Q. 17 Consider the following grammar:

P → xQRS

Q → yz | z

R → w | ε

S → y

What is FOLLOW(Q)?

A. {R}

B. {w}

C. {w, y}

D. {w, $}

 

Q. 18 Threads of a process share

A. global variables but not heap.

B. heap but not global variables.

C. neither global variables nor heap.

D. both heap global variables.

 

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

 

Q. 20 Let T be a tree with 10 vertices. The sum of the degrees of all vertices in T is __________.

 

Q. 21 Consider the given Karnaugh map, where X represents “don’t care” and blank represents 0. Assume for all inputs (a, b, c, d), the respective complements (a’, b’, c’, d’) are also available. The given logic is implemented using 2-input NOR gates only. The minimum number of gates required is _______.

 

Q. 22 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 __________.

 

Q. 23 Consider a database that has the relation schema EMP (EmpId, EmpName and DeptName). An instance of the schema EMP and an SQL query on it are given. The output of executing the SQL query is ________.

 

Q. 24 Consider the given CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given in the table. If the preemptive shortest remaining time first scheduling algorithm is used to schedule the processes, then the average waiting time across all processes is ___________ milliseconds.

 

Q. 25 Consider a two-level cache hierarchy with L1 and L2 caches. An application incurs 1.4 memory accesses per instruction on average. For this application, the miss rate of L1 cache is 0.1; the L2 cache experiences, on average, 7 misses per 1000 instructions. The miss rate of L2 expressed correct to two decimal places is ____________.

 

Q. 26 Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edged in E are positive and 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?

A. (I) only

B. (II) only

C. both (I) and (II)

D. neither (I) nor (II)

 

Q. 27 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 lock 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 a 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

A. x = 1, y = 2

B. x = 2, y = 1

C. x = 2, y = 2

D. x = 1, y = 1

 

Q. 28 The value of lim_(x→1) (x^7 – 2x^5 + 1) / (x^3 – 3x^2 + 2)

A. is 0

B. is -1

C. is 1

D. does not exist

 

Q. 29 Let p, q, and r be propositions and the expression (p → q) → r be a contradiction. Then, the expression (r → p) → q is

A. a tautology.

B. a contradiction.

C. always TRUE when p is FALSE.

D. always TRUE when q is TRUE.

 

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

A. 2

B. 1/2

C. 1

D. -1/2

 

Q. 31 Let A be n X n real valued square symmetric matrix of rank 2 with Σ_(i = 1 to n) Σ_(j = 1 to n)

(A_ij)² = 50. Consider the following statements:-

(I) One eigenvalue must be in [-5, 5].

(II) The eigenvalue with largest magnitude must be strictly greater than 5.

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

A. Both (I) and (II)

B. (I) only

C. (II) only

D. Neither (I) nor (II)

 

Q. 32 A computer network uses polynomials 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

A. 01011011010

B. 01011011011

C. 01011011101

D. 01011011100

 

Q. 33 Consider a combination of T and D flip-flops connected as shown in the figure. The output of the D flip-flop is connected to the T flip-flop and the output of the T flip-flop is connected to the input of the D flip-flop. Initially, both Q0 and Q1 are set to 1 (before the 1st clock cycle). The outputs

A. Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 00 respectively

B. Q1Q0 after the 3rd cycle are 11 and after the 4th cycle are 01 respectively

C. Q1Q0 after the 3rd cycle are 00 and after the 4th cycle are 11 respectively

D. Q1Q0 after the 3rd cycle are 01 and after the 4th cycle are 01 respectively

 

Q. 34 If G is a grammar with productions S → SaS | aSb | bSa | SS | ∈ where S is the start variable. Then which one of the following strings is not generated by G?

A. abab

B. aaab

C. abbaa

D. babba

 

Question 35

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

fun2 (++n);

printf(“%d”, n);

}

 

Q. 35 Consider the given two functions. The output printed when fun1(5) is called is

A. 53423122233445

B. 53423120112233

C. 53423122132435

D. 53423120213243

 

Question 36

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 – -);

}

return val;

}

 

Q. 36 Consider the C functions foo and bar as given. Invocations of foo(3) and bar(3) will result in: 

A. Return of 6 and 6 respectively.

B. Infinite loop and abnormal termination respectively.

C. Abnormal termination and infinite loop respectively.

D. Both terminating abnormally.

 

Q. 37 Consider the context-free grammars 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 L(G1) ∩ L(G2) is

A. Finite.

B. Not finite but regular.

C. Context-free but not regular.

D. Recursive but not context-free.

 

Q. 38 Consider the languages L1 and L2 over the alphabet Σ = {a, b, c}. Let L1 = {a^n b^n c^m | m, n ≥ 0} and L2 = {a^m b^n c^n | m, n ≥ 0}. Which of the following are context-free languages? 

I. L1 ∪ L2

II. L1 ∩ L2

A. I only

B. II only

C. I and II

D. Neither I nor II

 

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

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

B. f is computable if and only if Lf is recursively enumerable.

C. If f is computable then Lf is recursive, but not conversely.

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

 

Q. 40 Recall that Belady’s anomaly is that the page-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?

A. S1 is true. S2 is true.

B. S1 is true. S2 is false.

C. S1 is false. S2 is true.

D. S1 is false. S2 is false.

 

Q. 41 Consider a database that has the relation schemas EMP (EmpId, EmpName, DeptId) and DEPT (DeptName, DeptId). Note that the DeptId 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] ≠ v[DeptId] ))}

(II) { t | ∃u ∈ EMP( t{EmpName] = u[EmpName] ∧ ∃ v ∈ DEPT( t[DeptId] ≠ v[DeptId] ))}

(III) { t | ∃u ∈ EMP( t{EmpName] = u[EmpName] ∧ ∃ v ∈ DEPT( t[DeptId] = v[DeptId] ))}

Which of the above queries are safe?

A. (I) and (II) only

B. (I) and (III) only

C. (II) and (III) only

D. (I), (II) and (III)

 

Q. 42 In a database system, unique timestamps are assigned to each transaction using Lamport’s logical clock. Let TS(T1) and TS(T2) be the timestamps 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 system 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 transaction that is not killed terminates eventually. Which of the following is TRUE about the database system that uses the above algorithm to prevent deadlocks?

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

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

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

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

 

Question 43

stmt → if expr then expr else expr ; stmt | ∅

expr → term relop term | term

term → id | number

id → a | b | c

number → [0 – 9]

where relop is a relational operator (e.g., <, >, …), ∅ refers to the empty statement,

and if, then, else are terminals.

 

Q. 43 Consider the given grammar. Consider a program P following the given grammar

containing ten if terminals. The number if control flow paths in P is _______. 

For example, the program

if e1 then e2 else e3

has 2 control flow paths, e1 → e2 and e1 → e3.

 

Q. 44 In an RSA cryptosystem, a participant A uses two prime numbers p=13 and q=17 to generate her public and private keys. If the public key of A is 35, then the private key of A is ________.

 

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

Bit rate of the transmission channel = 1 Mbps Propagation delay from sender to receiver = 0.75 ms Time to process a frame = 0.25 ms

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

 

Q. 46 Consider a database that has the relation schema CR (StudentName, CourseName). An instance of the schema CR is as given in the figure. The following query is made on the database.

T1 ← Π_(CourseName) (σ_(StudentName=’SA’) (CR))

T2 ← CR ÷ T1

The number of rows in T2 is

 

Q. 47 The number of integer between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7: 

 

Q. 48 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 _______.

 

Q. 49 Consider an 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 given instruction sequence. If the target of the branch instruction is i, then the decimal value of the Offset is ________.

 

Q. 50 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 naive pipeline implementation (NP) with 5 stages and

(ii) and efficient pipeline (EP) where the OF stage is divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns, respectively.

The speedup (correct up to 2 decimal places) achieved by EP over NP in executing 20

independent instructions with no hazards is _________.

 

Q. 51 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 to connection of multiple blocks for the same cache set. Compulsory misses occur due to first time access to the block. The sequence of access 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 _________.

 

Q. 52 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 ans store instructions can have memory operands and (ii) arithmetic instructions can have only register or immediate operands. The value of X is __________.

 

Question 53

#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”, len);

}

void main() {

char *x = “abc”;

char *y = “defgh”;

printlength(x, y);

}

 

Q. 53 Consider the given C program. Recall that strlen is defined in string.h as returning a value of type size_t, which is and unsigned int. The output of the program is ____________.

 

Q. 54 A cache memory unit with capacity of N words and block size of B words is to be designed. If it is designed as a 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.

 

Question 55

#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);

}

 

Q. 55 The output of the given C program is _________.

 

Q. 56 After Rajendra Chola returned from his voyage to Indonesia, he ________ to visit the temple in Thanjavur.

A. was wishing

B. is wishing

C. wished

D. had wished

 

Q. 57 Research in the workplace reveals that people work for many reasons ________.

A. money beside

B. beside money

C. money besides

D. besides money

 

Q. 58 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?

A. Rahul and Murali

B. Srinivas and Arul

C. Srinivas and Murali

D. Srinivas and Rahul

 

Q. 59 Find the smallest number y such that y × 162 is a perfect cube.

A. 24

B. 27

C. 32

D. 36

 

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

A. 0.3^k

B. 0.6^k

C. 0.7^k

D. 0.9^k

 

Q. 61 “The hold of the nationalist imagination on our colonial past is such that anything

inadequately or improperly nationalist is not just history.” Which of the following statements best reflects the author’s opinion?

A. Nationalists are highly imaginative.

B. History is viewed through the filter of nationalism.

C. Our colonial past never happened.

D. Nationalism has to be both adequately and properly imagined.

 

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

A. 2

B. 3

C. 4

D. Cannot be determined

 

Q. 63 The expression [ (x – y) – |x – y| ] / 2 is equal to

A. the maximum of x and y

B. the minimum of x and y

C. 1

D. none of the above

 

Q. 64 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 ans 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?

A. 21

B. 18

C. 16

D. 14

 

Q. 65 A contour line joins locations having the same height above the mean sea level. A contour plot of a geographical region is given. 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?

A. P, Q

B. P, Q, T

C. R, S, T

D. Q, R, S

 

Answer Sheet
Question	1	2	3	4	5	6	7	8	9	10
Answer	D	B	C	B	C	B	D	B	C	B
Question	11	12	13	14	15	16	17	18	19	20
Answer	D	B	D	D	B	A	C	D	0	18
Question	21	22	23	24	25	26	27	28	29	30
Answer	1	4	2.6	3	0.05	A	D	C	D	A
Question	31	32	33	34	35	36	37	38	39	40
Answer	B	C	B	D	A	C	B	A	A	B
Question	41	42	43	44	45	46	47	48	49	50
Answer	D	A	1024	11	86.5 To 89.5	4	271	5	2	1.49 To 1.52
Question	51	52	53	54	55	56	57	58	59	60
Answer	76	2	3	14	23	C	D	C	D	C
Question	61	62	63	64	65
Answer	B	A	B	D	C