GATE CSE 2014 Set 3
View Questions

GATE CSE

1
The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X5 + 4X3 + 6X + 5 for a given value of X using only one temporary variable is _____.
2
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
3
Consider the decision problem 2CNFSAT defined as follows:

{ $$\Phi $$ | $$\Phi $$ is a satisfiable propositional formula in CNF with at most two literal per clause}

For example, $$\Phi = \left( {{x_1} \vee {x_2}} \right) \wedge \left( {{x_1} \vee {{\overline x }_3}} \right) \wedge \left( {{x_2} \vee {x_4}} \right)$$ is a Boolean formula and it is in 2CNFSAT.

The decision problem 2CNFSAT is

4
One of the purposes of using intermediate code in compilers is to
5

Consider the basic block given below.

a = b + c 
c = a + d 
d = b + c 
e = d - b 
a = e + b

The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

6
An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address 131.23.151.76. The router’s routing table has the following entries: GATE CSE 2014 Set 3 Computer Networks - Network Layer Question 22 English

The identifier of the output interface on which this packet will be forwarded is ______.

7
In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is
8
A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is
9
Host A (on TCP/IPv4 network A) sends an IP datagram D to host B (also on TCP/IPv4 network B). Assume that no error occurred during the transmission of D. When D reaches B, which of the following IP header field(s) may be different from that of the original datagram D?

(i) TTL
(ii) Checksum
(iii) Fragment Offset
10
Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each host has a globally unique IPv4 address. Design a 50-bit globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?
11
An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an IP header of length 20 bytes. The values of the relevant fields in the header of the third IP fragment generated by the router for this packet are
12
The memory access time is $$1$$ nanosecond for a read operation with a hit in cache, $$5$$ nanoseconds for a read operation with a miss in cache, $$2$$ nanoseconds for a write operation with a hit in cache and $$10$$ nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves $$100$$ instruction fetch operations, $$60$$ memory operand read operations and $$40$$ memory operand write operations. The cache hit-ratio is $$0.9.$$ The average memory access time (in nanoseconds) in executing the sequence of instructions is___________________.
13
Consider the following processors ($$ns$$ stands for nanoseconds). Assume that the pipeline registers have zero latency.
$$P1:$$ Four-stage pipeline with stage latencies $$1$$ $$ns,$$ $$2$$ $$ns,$$ $$2$$ $$ns,$$ $$1$$ $$ns.$$
$$P2:$$ Four-stage pipeline with stage latencies $$1$$ $$ns,$$ 1$$.5$$ $$ns,$$ $$1.5$$ $$ns,$$ $$1.5$$ $$ns.$$
$$P3:$$ Five-stage pipeline with stage latencies $$0.5$$ $$ns,$$ $$1$$ $$ns,$$ $$1$$ $$ns,$$ $$0.6$$ $$ns,$$ $$1$$ $$ns.$$
$$P4:$$ Five-stage pipeline with stage latencies $$0.5$$ $$ns,$$ $$0.5$$ $$ns,$$ $$1$$ $$ns,$$ $$1$$ $$ns,$$ $$1.1$$ $$ns.$$

Which processor has the highest peak clock frequency?

14
An instruction pipeline has five stages, namely, instruction fetch $$(IF),$$ instruction decode and register fetch $$(ID/RF)$$ instruction execution $$(EX),$$ memory access $$(MEM),$$ and register writeback $$(WB)$$ with stage latencies $$1$$ ns, $$2.2$$ $$ns,$$ $$2$$ $$ns,$$ $$1$$ $$ns,$$ and $$0.75$$ $$ns,$$ respectively ($$ns$$ stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the $$ID/RF$$ stage into three stages $$(ID, RF1, RF2)$$ each of latency $$2.2/3$$ $$ns,$$ Also, the $$EX$$ stage is split into two stages $$(EX1, EX2)$$ each of latency $$1$$ ns. The new design has a total of eight pipeline stages. A program has $$20$$% branch instructions which execute in the $$EX$$ stage and produce the next instruction pointer at the end of the $$EX$$ stage in the old design and at the end of the $$EX2$$ stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average $$CPI$$ of one in both the designs. The execution times of this program on the old and the new design are $$P$$ and $$Q$$ nanoseconds, respectively. The value of $$P/Q$$ is _____________.
15
Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.
typedef struct treeNode* treeptr; 
Struct treeNode 
{ 
    Treeptr leftMostchild, rightSibiling; 
}; 
Int Dosomething (treeptr tree) 
{ 
    int value =0; 
    if (tree ! = NULL) { 
      If (tree -> leftMostchild = = NULL) 
          value=1; 
    else 
        value = Dosomething (tree->leftMostchild); 
        value = value + Dosometing (tree->rightsibiling); 
    } 
    return (value); 
}
When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the
16
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________. GATE CSE 2014 Set 3 Data Structures - Graphs Question 24 English
17
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
18
Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order.
int ProcessArray(int *listA, int x, int n) 
{ 
      int i, j, k; 
      i = 0; 
      j = n-1; 
      do 
      { 
         k = (i+j)/2; 
         if (x <= listA[k]) 
           j = k-1; 
         if (listA[k] <= x) 
           i = k+1; 
      } 
      while (i <= j); 
      if (listA[k] == x) 
           return(k); 
      else 
           return -1; 
}
Which one of the following statements about the function ProcessArray is CORRECT?
19
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O( na logb n + mc logd n ), the value of a + 10b + 100c + 1000d is _______.
20
Consider the following rooted tree with the vertex labelled P as the root GATE CSE 2014 Set 3 Data Structures - Trees Question 63 English The order in which the nodes are visited during an in-order traversal of the tree is
21

Consider the following relational schema:

employee (empId, empName, empDept )

customer (custId, custName, salesRepId, rating)

SalesRepId is a foreign key referring to empId of the employee relation. Assume that each employee makes a sale to at least one customer. What does the following query return?
SELECT empName 
FROM employee E 
WHERE NOT EXISTS (SELECT custId 
       FROM customer C 
       WHERE C.salesRepId = E.empId 
       AND C.rating <> 'GOOD');
22
What is the optimized version of the relation algebra expression $$\pi_{A1}(\pi_{A2}(\sigma_{F1}(\sigma_{F2}(r))))$$, where $$A1, A2$$ are sets of attributes in r with $$A1 \subset A2$$ and $$F1,F2$$ are Boolean expressions based on the attributes in r?
23
Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of the relation employee. Assume that every employee has at least one associated dependent in the dependent relation:

employee (empId, empName, empAge)

dependent (depId, eId, depName, depAge)

Consider the following relational algebra query: $$\Pi_{empId}\:(employee) - \Pi_{empId}\:(employee \bowtie_{(empId=eID) \wedge (empAge \leq depAge)} dependent)$$

The above query evaluates to the set of empIds of employees whose age is greater than that of

24
Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.

T1 : r1 (X) ; r1 (Z) ; w1 (X) ; w1 (Z)

T2 : r2 (X) ; r2 (Z) ; w2 (Z)

T3 : r3 (X) ; r3 (X) ; w3 (Y)

S1: r1(X); r3(Y); r3(X); r2(Y); r2(Z); w3(Y); w2(Z); r1(Z); w1(X); w1(Z)

S2: r1(X); r3(Y); r2(Y); r3(X); r1(Z); r2(Z); w3(Y); w1(X); w2(Z); w1(Z)

Which one of the following statements about the schedules is TRUE?
25
A prime attribute of a relation scheme $$R$$ is an attribute that appears
26
Consider the following combinational function block involving four Boolean variables $$x, y, a,$$
$$b$$ where $$x, a, b$$ are inputs and $$y$$ is the output. GATE CSE 2014 Set 3 Digital Logic - Boolean Algebra Question 41 English
Which one of the following digital logic blocks is the most suitable for implementing this function?
27
Let $$ \oplus $$ denote the exclusive $$OR\left( {XOR} \right)$$ operation. Let $$'1'$$ and $$'0'$$ denote the binary constants. Consider the following Boolean expression for $$F$$ over two variables $$P$$ and $$Q$$:
$$F\left( {P,Q} \right) = \left( {1 \oplus P} \right) \oplus \left( {P \oplus Q} \right) \oplus \left( {P \oplus Q} \right) \oplus \left( {Q \oplus 0} \right)$$

The equivalent expression for $$F$$ is

28
Consider the following interm expression of $$F:$$
$$F\left( {P,\,Q,\,R,\,S} \right) = \sum {0,2,5,7,8,10,13,15} $$
The minterms $$2, 7, 8$$ and $$13$$ are 'do not care' terms. The minimal sum-of-products form for $$F$$ is _______
29
GATE CSE 2014 Set 3 Digital Logic - Sequential Circuits Question 17 English

The above synchronous sequential circuit built using $$JK$$ flip-flops is initialized with $${Q_2}{Q_1}{Q_0} = 000.\,\,$$ The state sequence for this circuit for the next $$3$$ clock cycles is

30
Let S be a sample space and two mutually exclusive events A and B be such that $$A\, \cup \,B = \,S$$. If P(.) denotes the probability of the event, the maximum value of P(A) P(B) is ________________.
31
The CORRECT formula for the sentence, "not all rainy days are cold" is
32
Let $$X$$ and $$Y$$ be finite sets and $$f:X \to Y$$ be a function. Which one of the following statements is TRUE?
33
Which one of the following statements is TRUE about every $$n\,\, \times \,n$$ matrix with only real eigen values?
34
If $${V_1}$$ and $${V_2}$$ are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dimension of $${V_1}\, \cap \,\,{V_2}$$ is _________________.
35
If $$\int_0^{2\pi } {\left| {x\sin x} \right|dx = k\pi ,} $$ then the values of $$k$$ is equal to _________ .
36
The value of the integral given below is $$$\int_0^\pi {{x^2}\,\cos \,x\,dx} $$$
37
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre specified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1+ min(T(y),T(z)). Then the value of the product yz is _______.
38
Consider the set of all functions $$f:\left\{ {0,\,1,.....,2014} \right\} \to \left\{ {0,\,1,.....,2014} \right\}$$ such that $$f\left( {f\left( i \right)} \right) = i,\,\,\,$$ for all $$0 \le i \le 2014.$$ Consider the following statements:
$$P$$. For each such function it must be the case that for every $$i$$, $$f\left( i \right) = i$$
$$Q$$. For each such function it must be the case that for some $$i$$, $$f\left( i \right) = 1$$
$$R$$. Each such function must be onto.

Which one of the following id CORRECT?

39
There are two elements $$x, y$$ in a group $$\left( {G,\, * } \right)$$ such that every elements in the group can be written as a product of some number of $$x's$$ and $$y's$$ in some order. It is known that
$$x * x = y * y = x * y * x * y = y * x * y * x = e$$
where $$e$$ is the identity element. The maximum number of elements in such a group is ______.
40
let $$G$$ be a group with $$15$$ elements. Let $$L$$ be a subgroup of $$G$$. It is known that $$L \ne G$$ and that the size of $$L$$ is at least $$4$$. The size of $$L$$ is ______.
41
Let $$\delta $$ denote the minimum degree of a vertex in a graph. For all planar graphs on $$n$$ vertices with $$\delta \ge 3$$, which one of the following is TRUE?
42
If $$G$$ is a forest with $$n$$ vertices and $$k$$ connected components, how many edges does $$G$$ have?
43
Consider the following statements:
P: Good mobile phones are not cheap
Q: Cheap mobile phones are not good
L: P implies Q
M: Q implies P
N: P is equivalent to Q

Which of the following about L, M, and N is Correct?

44
A system uses $$3$$ page frames for storing process pages in main memory. It uses the Least Recently Used $$(LRU)$$ page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below? $$$4,7,6,1,7,6,1,2,7,2$$$
45
Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is______________.
46
A system contains three programs and each requires three tape units for its operation. The Minimum number of tape units which the system must have such that deadlocks never arise is _________.
47
An operating system uses $$shortest$$ $$remaining$$ $$time$$ $$first$$ scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and $$CPU$$ burst times (in milliseconds):
Process Arrival Time Burst Time
P1 0 12
P2 2 4
P3 3 6
P4 8 5

The average waiting time (in milliseconds) of the processes is ________.

48
Which of the following statements are CORRECT?

1) Static allocation of all data areas by a compiler makes it impossible to implement recursion.

2) Automatic garbage collection is essential to implement recursion.

3) Dynamic allocation of activation records is essential to implement recursion.

4) Both heap and stack are essential to implement recursion.
49
Let A be a square matrix size $$n \times n$$. Consider the following pseudocode. What is the expected output?
C = 100; 
for i = 0 to n do 
for j = 1 to n do 
 { 
      Temp = A[ i ][ j ] + C ; 
      A[ i ][ j ] = A[ j ][ i ] ; 
      A[ j ][ i ] = Temp - C ; 
 } 

 for i = 0 to n do 
 for j = 1 to n do 
 output(A[ i ][ j ]);
50
In the context of modular software design, which one of the following combinations is desirable?
51
The length of the shortest string NOT in the language (over $$\sum { = \left\{ {a,\,\,b} \right\}} $$) of the following regular expression is ____________. $$$a{}^ * b{}^ * \left( {ba} \right){}^ * a{}^ * $$$
52
Consider the following languages over the alphabet $$\sum { = \left\{ {0,\,1,\,c} \right\}:} $$
$$\eqalign{ & {L_1} = \left\{ {{0^n}\,{1^n}\,\left| {n \ge } \right.0} \right\} \cr & {L_2} = \left\{ {wc{w^r}\,\left| {w \in \left\{ {0,\,1} \right\}{}^ * } \right.} \right\} \cr & {L_3} = \left\{ {w{w^r}\,\left| {w \in \left\{ {0,\,1} \right\}{}^ * } \right.} \right\} \cr} $$

Here, $${w^r}$$ is the reverse of the string $$w.$$ Which of these languages are deterministic Context- free languages?

53
Let $$\sum \, $$ be a finite non - empty alphabet and let $${2^{\sum {{}^ * } }}$$ be the power set of $$\sum {{}^ * .\,} $$ Which one of the following is TRUE?
54
Which one of the following problems is un-decidable?
EXAM MAP
Medical
NEETAIIMS
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
Staff Selection Commission
SSC CGL Tier I
CBSE
Class 12