|
61. In an inventory management system implemented at a trading corporation,
there are several tables designed to hold all the information. Amongst these,
the following two tables hold information on which items are supplied by which
suppliers, and which warehouse keeps which items along with the stock-level
of these items.
Supply = (supplierid, itemcode)
Inventory = (itemcode, warehouse, stocklevel)
For a specific information required by the management, following SQL query has
been written.
Select distinct STMP supplierid
From supply as STMP
Where not unique (Select ITMP.supplierid
From Inventory, Supply as ITMP
Where STMP.supplierid = ITMP.supplierid
And ITMP. itemcode = Inventory. itemcode
And Inventory.warehouse = �Nagpur�);
For the warehouse at Nagpur, this query will find all suppliers who
(A) do not supply any item
(B) supply exactly one item
(C) supply one or more items
(D) supply two or more items
62. In a schema with attributes A, B, C, D and E following set of functional
dependencies are given.
A-B
A-C
CD-E
B-D
E-A
Which of the following functional dependencies is NOT implied by the above set?
(A) CD - AC
(B) BD - CD
(C) BC - CD
(D) AC - BC
63. A network with CSMA/CD protocol in the MAC layer is running at 1 Gbps over a
1 km cable with no repeaters. The signal speed in the cable is 2x108m/sec.
The minimum frame size for this network should be
(A) 10000 bits
(B) 10000 bytes
(C) 5000 bits
(D)5000 bytes
64. A channel has a bit rate of 4 kbps and one-way propagation delay of 20 ms.
The channel uses stop and wait protocol. The transmission time of the
acknowledgement frame is negligible. To get a channel efficiency of at least 50�h,
the minimum frame size should be
(A) 80 bytes
(B) 80 bits
(C) 160 bytes
(D) 160 bits
65. On a TCP connection, current congestion window size is Congestion Window = 4 KB.
The window size advertised by the received is Advertise Window = 6 KB.
The last byte sent by the sender is LastByteSent = 10240 and the last byte acknowledged
by the receiver is LastByteAcked = 8192. The current window size at the sender is:
(A) 2048 bytes
(B) 4096 bytes
(C) 6144 bytes
(D)8192 bytes
66. In a communication network, a packet of length L bits takes link Li with a probability
of Pi or link L2 with a probability of P2. Link Li and L2 have bit error probability of b1
and b2 respectively. The probability that the packet will be received without error via
either Li or L2 is:
(A) (i_b1)Lp1+(i_b2)Lp2
(B) [i_(b1+b2)P1P2
(C) (1�b1 )L (1 � b2 )L p1p2
(D) i � (bi�-p, + b21- p)
67. In a TDM medium access control bus LAN, each station is assigned one time slot
per cycle for transmission. Assume that the length of each time slot is the time to
transmit 100 bits plus the end-to-end propagation delay. Assume a propagation speed
of 2xiO8m/sec. The length of the LAN is 1 km with a bandwidth of 10 Mbps. The maximum
number of stations that can be allowed in the LAN so that the throughput of each
station can be Mbps is:
(A) 3
(B) 5
(C) 10
(D) 20
68. A company has a class C network address of 204.204.204.0. It wishes to have
three subnets, one with 100 hosts and two with 50 hosts each. Which one of the
following options represents a feasible set of subnet address/subnet mask pairs?
(A) 204.204.204.128/255.255.255.192
204.204.204.0/255.255.255.128
204.204.204.64/255.255.255.128
(B) 204.204.204.0/255.255.255.192
204.204.204.192/255.255.255.128
204.204.204.64/255.255.255.128
(C) 204.204.204.128/255.255.255.128
204.204.204.192/255.255.255.192
204.204.204.224/255.255.255.192
(D) 204.204.204.128/255.255.255.128
204.204.204.64/255.255.255.192
204.204.204.0/255.255.255.192
69. Assume that �hostl.mydomain.dom� has an IP address of 145.128.16.8.
Which of the following options would be most appropriate as a subsequence
of steps in performing the reverse lookup of 145.128.16.8? In the following
options �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.
70. Consider the following message M = 1010001101. The cyclic redundancy check (CRC)
for this message using the divisor polynomial x5 + x4 + x2 + 1 is:
(A) 01110
(B) 01011
(C) 10101
(D) 10110
71. Suppose that two parties A and B wish to setup a common secret key (D-H key)
between themselves using the Diffie-Hellman key exchange technique. They agree on 7
as the modulus and 3 as the primitive root. Party A chooses 2 and party B chooses 5
as their respective secrets. Their D-H key is:
(A) 3
(B) 4
(C) 5
(D) 6
72. Given below is an excerpt of an xml specification.
<!DOCTYPE library SYSTEM �library.dtd�>
<Book>
<title> GATE 2005 </title>
<type value = �BROCHURE�!>
<accno> 10237623786</accno>
</Book>
<Book>
<type value = �FICTION�!>
<accno>0024154807</accno>
</Book>
Given below are several possible excerpts from �libratry.dtd�.
For which excerpt would the above specification be valid?
(A) <!ELEMENT Book (title+, type, accno)>
<!ELEMENT title (#PCDATA)>
<!ELEMENT type EMPTY>
<!ATTLIST type value (BROCHURE/FICTION/TECHNICAL)>
<!ELEMENT accno (#PCDATA)>
(B) <!ELEMENT Book (title?, type, accno)>
<!ELEMENT title (#PCDATA)>
<!ELEMENT type ATTLIST>
<!ATTLIST type value (BROCHURE/FICTION/TECHNICAL)>
<!ELEMENT accno value (#PCDATA)>
(C) <!ELEMENT Book (title*, type, accno)>
<!ELEMENT title (#PCDATA)>
<!ELEMENT type ATTLIST>
<!ATTLIST type value (BROCHURE/FICTION/TECHNICAL)>
<!ELEMENT accno (#PCDATA)>
(D) <!ELEMENT Book (title?, type, accno)>
<!ELEMENT title (#PCDATA)>
<!ELEMENT type EMPTY>
<!ATTLIST type value (BROCHURE/FICTION/TECHNICAL)>
<!ELEMENT accno (#PCDATA)>
Linked Answer Questions: Q.73a to Q73b Carry Two Marks Each.
Statement for Linked Answer Questions 73a and 73b:
A disk has 8 equidistant tracks. The diameters of the innermost and outermost tracks
are 1 cm and 8 cm respectively. The innermost track has a storage capacity of 10 MB.
73. (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 5th 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 read
1 MB contiguous data starting from the sector 4 of the outer most track?
(A) 13.5 ms
(B) 10 ms
(C) 9.5 ms
(D) 20 ms
Statement for Linked Answer Questions 74a and 74b:
A database table Ti has 2000 records and occupies 80 disk blocks.
Another table T2 has 400 records and occupies 20 disk blocks.
These two tables have to be joined as per a specified join condition
that needs to be evaluated for every pair of records from these two tables.
The memory buffer space available can hold exactly one block of records for
Ti and one block of records for T2 simultaneously at any point in time.
No index is available on either table.
74. (A) If Nested loop join algorithm is employed to perform the join,
with the most appropriate choice of table to be used in outer loop,
the number of block accesses required for reading 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 appropriate choice of table in the outer loop, the reduction in
number of block accesses required for reading the data will be:
(A) 0
(B) 30400
(C) 38400
(D)798400
Statement for Linked Answer Questions 75a and 75b:
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}.
75. (A) Which of the following terminal strings has more than one 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 one parse tree obtained as
solution to Question 83a, how many parse trees are possible?
(A) 5
(B) 4
(C) 3
(D) 2
Statement for Linked Answer Questions 76a and 76b:
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 = 1 if there is an edge directed
from vertex I tojand 0 otherwise. The following algorithm determines whether there is a
sink in the graph G.
>I = 0;
do {
j=i+1;
while((j<n) && E1)j++;
if (j<n)E2
} while (j<n)
flag =1;
for(j = 0 ;j < n ;j + +)
if (j!=i)&&E3) flag =0;
if(flag) printf(�Sink exists�) else printf(�Sink does not exist�);
76. A) Choose the correct expressions for E1 and E2
(A) E1 : A [1111 and E2 : =
(B) E1:!A[ijjl and E2:i=j+1;
(C) E1 : !A[ijjl and E2 :1 =
(D) E1 :A[ijjl and E2 :i=j+1;
(B) Choose the correct expression for E3
(A) (A[ijjl& &!A[f Ill)
(B) (!A[ijjl& &!A[jjij)
(C) (!A[ijfj !A[jji1)
(D) (A[ijfj !A[jji1
|
