GATE CSE 2014 Set 3

## GATE CSE

The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X5 + 4X3 + 6X + 5 for a given val

View Question You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as

View Question Consider the decision problem 2CNFSAT defined as follows:
{ $$\Phi $$ | $$\Phi $$ is a satisfiable propositional formula

View Question One of the purposes of using intermediate code in compilers is to

View Question 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

View Question In the following pairs of OSI protocol layer/sub-layer and its functionality, the INCORRECT pair is

View Question A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffi

View Question 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 occur

View Question Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate

View Question An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an I

View Question An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address 131.23.151.76. The router

View Question The memory access time is $$1$$ nanosecond for a read operation with a hit in cache, $$5$$ nanoseconds for a read operat

View Question Consider the following processors ($$ns$$ stands for nanoseconds). Assume that the pipeline registers have zero latency.

View Question An instruction pipeline has five stages, namely, instruction fetch $$(IF),$$ instruction decode and register fetch $$(ID

View Question Consider the following rooted tree with the vertex labelled P as the root
The order in which the nodes are visited duri

View Question Consider the C function given below. Assume that the array listA contains n (> 0) elements, sored in ascending order.

View Question Consider the pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary

View Question Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call

View Question Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is t

View Question 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 a

View Question A prime attribute of a relation scheme $$R$$ is an attribute that appears

View Question Consider the following relational schema:
employee (empId, empName, empDept ) customer (custId, custName, salesRepId, ra

View Question What is the optimized version of the relation algebra expression $$\pi_{A1}(\pi_{A2}(\sigma_{F1}(\sigma_{F2}(r))))$$, wh

View Question Consider the relational schema given below, where eId of the relation dependent is a foreign key referring to empId of t

View Question Consider the transactions T1, T2, and T3 and the schedules S1 and S2 given below.
T1 : r1 (X) ; r1 (Z) ; w1 (X) ; w1 (Z)

View Question Consider the following combinational function block involving four Boolean variables $$x, y, a,$$
$$b$$ where $$x, a, b

View Question Let $$ \oplus $$ denote the exclusive $$OR\left( {XOR} \right)$$ operation. Let $$'1'$$ and $$'0'$$ denote the binary co

View Question Consider the following interm expression of $$F:$$
$$F\left( {P,\,Q,\,R,\,S} \right) = \sum {0,2,5,7,8,10,13,15} $$
Th

View Question
The above synchronous sequential circuit built using $$JK$$ flip-flops is initialized with $${Q_2}{Q_1}{Q_0} = 000.\,\,

View Question Consider the following statements:
P: Good mobile phones are not cheap
Q: Cheap mobile phones are not good
L: P implies

View Question Let S be a sample space and two mutually exclusive events A and B be such that $$A\, \cup \,B = \,S$$. If P(.) denotes t

View Question The CORRECT formula for the sentence, "not all rainy days are cold" is

View Question Let $$X$$ and $$Y$$ be finite sets and $$f:X \to Y$$ be a function. Which one of the following statements is TRUE?

View Question Which one of the following statements is TRUE about every $$n\,\, \times \,n$$ matrix with only real eigen values?

View Question If $${V_1}$$ and $${V_2}$$ are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dim

View Question If $$\int_0^{2\pi } {\left| {x\sin x} \right|dx = k\pi ,} $$ then the values of $$k$$ is equal to _________ .

View Question The value of the integral given below is
$$$\int_0^\pi {{x^2}\,\cos \,x\,dx} $$$

View Question 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

View Question Consider the set of all functions $$f:\left\{ {0,\,1,.....,2014} \right\} \to \left\{ {0,\,1,.....,2014} \right\}$$ such

View Question There are two elements $$x, y$$ in a group $$\left( {G,\, * } \right)$$ such that every elements in the group can be wri

View Question 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 s

View Question Let $$\delta $$ denote the minimum degree of a vertex in a graph. For all planar graphs on $$n$$ vertices with $$\delta

View Question If $$G$$ is a forest with $$n$$ vertices and $$k$$ connected components, how many edges does $$G$$ have?

View Question An operating system uses $$shortest$$ $$remaining$$ $$time$$ $$first$$ scheduling algorithm for pre-emptive scheduling o

View Question A system uses $$3$$ page frames for storing process pages in main memory. It uses the Least Recently Used $$(LRU)$$ page

View Question Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. I

View Question A system contains three programs and each requires three tape units for its operation. The Minimum number of tape units

View Question Which of the following statements are CORRECT?
1) Static allocation of all data areas by a compiler makes it impossible

View Question Let A be a square matrix size $$n \times n$$. Consider the following pseudocode. What is the
expected output?
C = 100;

View Question In the context of modular software design, which one of the following combinations is desirable?

View Question The length of the shortest string NOT in the language (over $$\sum { = \left\{ {a,\,\,b} \right\}} $$) of the following

View Question Consider the following languages over the alphabet $$\sum { = \left\{ {0,\,1,\,c} \right\}:} $$
$$\eqalign{
& {L_

View Question Let $$\sum \, $$ be a finite non - empty alphabet and let $${2^{\sum {{}^ * } }}$$ be the power set of $$\sum {{}^ * .\,

View Question Which one of the following problems is un-decidable?

View Question