Indian Institute of Technology Mumbai (IIT-M) 2005 M.E Information Technology GATE IT - Question Paper
Wednesday, 23 January 2013 02:40Web
Page 16 of 16
reverse lookup of 145.128.16.8? In the subsequent choices “NS” is an abbreviation of
“nameserver”?
(A) Query a NS for the root domain and then NS for the “dom” domains
(B) Directly query a NS for “dom” and then a NS for “mydomain.dom” domains
(C) Query a NS for in-addr.arpa and then a NS for 128.145.in-addr.arpa domains
(D) Directly query a NS for 145.in-addr.arpa and then a NS for 128.145.in- addr.arpa
domains.
78. Consider the subsequent message M = 1010001101. The cyclic redundancy check (CRC) for
this message using the divisor polynomial x5 + x4 + x2 + one is:
(A) 01110
(B) 01011
(C) 10101
(D)10110
79. Suppose that 2 parties A and B wish to setup a common secret key (D-H key) ranging from
themselves using the Diffie-Hellman key exchange technique. They agree on seven as the modulus
and three as the primitive root. Party A selects two and party B selects five as their respective
secrets. Their D-H key is:
(A) 3
(B) 4
(C) 5
(D)6
80. provided beneath is an excerpt of an xml specification.
provided beneath are several possible excerpts from “libratry.dtd”. For which excerpt would the
above specification be valid?
(A)
(B)
(C)
(D)
Linked ans Questions: Q.81a to Q85b Carry 2 Marks every.
Statement for Linked ans ques. 81a and 81b:
A disk has eight equidistant tracks. The diameters of the innermost and outermost tracks are 1
cm and eight cm respectively. The innermost track has a storage capacity of 10 MB.
81. (A) What is the total amount of data that can be stored on the disk if it is used with a
drive that rotates it with
(i) Constant Linear Velocity
(ii) Constant Angular Velocity
(A) (i) 80 MB (ii) 2040 MB (B) (i) 2040 MB (ii) 80 MB
(C) (i) 80 MB (ii) 360 MB (D) (i) 360 MB (ii) 80 MB
(B) If the disk has 20 sectors per track and is currently at the end of the fifth sector of the
inner most track and the head can move at a speed of 10 meters/sec and it is rotating at
constant angular velocity of 6000 RPM, how much time will it take to learn one MB contiguous
data starting from the sector four of the outer most track?
(A) 13.5 ms
(B) 10 ms
(C) 9.5 ms
(D)20 ms
Statement for Linked ans ques. 82a and 82b:
A database table Ti has 2000 records and occupies 80 disk blocks. a different table T2 has 400
records and occupies 20 disk blocks. These 2 tables have to be joined as per a specified join
condition that needs to be evaluated for every pair of records from these 2 tables. The
memory buffer space available can hold exactly 1 block of records for Ti and 1 block of
records for T2 simultaneously at any point in time. No index is available on either table.
82. (A) If Nested loop join algorithm is employed to perform the join, with the most
improper option of table to be used in outer loop, the number of block accesses needed for
studying the data are:
(A) 800000
(B) 40080
(C) 32020
(D) 100
(B) If, instead of Nested loop join, Block nested loop join is used, again with the most
improper option of table in the outer loop, the reduction in number of block accesses
needed for studying the data will be:
(A) 0
(B) 30400
(C) 38400
(D)798400
Statement for Linked ans ques. 83a and 83b:
Consider the context-free grammar
E -E+E
E _(E*E)
E - Id
Where E is the starting symbol, the set of terminals is {id,(,+,),*, and the set of
non-terminals is {E}.
83. (A) Which of the subsequent terminal strings has more than 1 parse tree when parsed
according to the above grammar?
(A) id + id + id + id
(B) id + (id* (id * id))
(C) (id * (id*id)) + id
(D) ((id * id + id) * id)
(B) For the terminal string with more than 1 parse tree found as solution to ques.
83a, how many parse trees are possible?
(A) 5
(B) 4
(C) 3
(D)2
Statement for Linked ans ques. 84a and 84b:
A sink in a directed graph is a vertex isuch that there is an edge from every vertex j Ito land
there is no edge from Ito any other vertex. A directed graph G with n vertices is represented
by its adjacency matrix a, where A[ijjl = one if there is an edge directed from vertex I tojand 0
otherwise. The subsequent algorithm determines whether there is a sink in the graph G.
I = 0;
do {
j=i+1;
while((j
for(j = 0 ;j < n ;j + +)
if (j!=i)&&E3) flag =0;
if(flag) printf(”Sink exists”) else printf(”Sink does not exist”);
84. (A) select the accurate expressions for E1 and E2
(A) E1 : A [1111 and E2 : =
(B) (!A[ijjl& &!A[jjij)
(C) E1 : !A[ijjl and E2 :1 =
(D) (A[ijfj !A[jji1)
(B) select the accurate expression for E3
(A) (A[ijjl& &!A[f Ill)
(C) (!A[ijfj !A[jji1)
(B) E1:!A[ijjl and E2:i=j+1;
(D) E1 :A[ijjl and E2 :i=j+1;
Statement for Linked ans ques. 85a and 85b:
Consider a simple graph with unit edge costs. every node in the graph represents a router.
every node maintains a routing table indicating the next hop router to be used to relay a
packet to its destination and the cost of the path to the destination through that router.
Initially, the routing table is empty. The routing table is synchronously updated as follows. In
every updation interval, 3 tasks are performed.
(i) A node determines whether its neighbours in the graph are accessible. If so, it sets the
tentative cost to every accessible neighbour as 1. Otherwise, the cost is set to .
(ii) From every accessible neighbour, it gets the costs to relay to other nodes via that
neighbour (as the next hop)
(iii) every node updates its routing table based on the info received in the previous two
steps by choosing the minimum cost.
85. (A) For the graph provided above, possible routing tables for different nodes after they have
stabilized, are shown in the subsequent choices. Identify the accurate table?
(A) Table for node A (B) Table for node C
A- AA1
BB1 BB1
Ccl C- -
DB3 DD1
EC3 EEl
FC4 FE3
(C) Table for node B (D) Table for node D
A A one A B3
B - - B B1
C C one C C1
D Dl D
E C two E E1
F D two F Fj]
(B) Continuing from the earlier problem, suppose at a few time t, when the costs have
stabilized, node A goes down. The cost from node F to node A at time (t+100)is:
(A) > 100 but finite
(B)
(C) 3
(D) >3 and 100
| Earning: Approval pending. |
