Uttar Pradesh Technical University (UPTU) 2006 B.Tech Computer Science Information Technology GATE - Question Paper

GATE CS - 2006
Q.1 — Q.20 Carry 1 Mark every
1. Consider the polynomial p(x) = a0 +a1x+a2x2 +a3x2, where a1 (- 0,Vi. The minimum
number of multiplications needed to evaluate pon an input x is:
(A) 3
(B) 4
(C) 6
(D) 9
2. Let X,Y,Z be sets of sizes x, y and z respectively. Let W = XxY and E be the set
of all subsets of W. The number of functions from Z to E is:
(A) Z2XY
(B) Zx2
(C) Z2XY
(D) 2XYZ
3. The set {1,2,3,5,7,8,91 under multiplication modulo 10 is not a group. provided
beneath are 4 plausible reasons. Which 1 of them is false?
(A) It is not closed
(B) two does not have an inverse
(C) three does not have an inverse
(D) eight does not have an inverse
4. A relation R is described on ordered pairs of integers as follows:
(x,y)R(u,v)if x < u andy> v. Then R is:
(A) Neither a Partial Order nor an Equivalence Relation
(B) A Partial Order but not a Total Order
(C) A Total Order
(D) An Equivalence Relation
5. For which 1 of the subsequent reasons does Internet Protocol (IP) use the timeto-
live (TTL) field in the IP datagram header?
(A) Ensure packets reach destination within that time
(B) Discard packets that reach later than that time
(C) Prevent packets from looping indefinitely
(D) Limit the time for which a packet gets queued in intermediate routers.
6. Consider 3 CPU-intensive processes, which require 10, 20 and 30 time units and arrive
at times 0, two and 6, respectively. How many situation switches are needed if the operating
system implements a shortest remaining time 1st scheduling algorithm? Do not count the
situation switches at time zero and at the end.
(A) 1
(B) 2
(C) 3
(D) 4
7. Consider the subsequent grammar.
Consider the subsequent LR(0) items corresponding to the grammar above.

provided the items above, which 2 of them will appear in the identical set in the canonical sets-ofitems
for the grammar?
(A) (i) and (ii)
(B) (ii) and (iii)
(C) (i) and (iii)
(D) None of the above
8. You are provided a free running clock with a duty cycle of 50% and a digital waveform f which
modifications only at the negative edge of the clock. Which 1 of the subsequent circuits (using
clocked D flip-flops) will delay the phase of f by 1800?
9. A CPU has 24-bit instructions. A program begins at address 300 (in decimal). Which 1 of
the subsequent is a legal program counter (all values in decimal)?

Earning:   Approval pending.