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
An IP router implementing Classless Inter-domain Routing (CIDR) receives a packet with address 131.23.151.76. The router

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
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 pseudocode given below. The function Dosomething () takes as argument a pointer to the root of an arbitrary

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

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
Let A be a square matrix size $$n \times n$$. Consider the following pseudocode. What is the
expected output?
C = 100;

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

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