Indian Institute of Technology New Delhi - (IIT) 2010 M.Tech Computer and Information Science Computer science engineering gate- - Question Paper
CS : COMPUTER SCIENCE AND INFORMATION TECHNOLOGY
Durufioir Three Hours Maximum Murks 100
Read the foliowin* instructions carefully.
1. This question paper contains 24 pages including blank pages for rough work. Please check nil pages and report discrepancy, if any
2. Write your registration number, your name and name of the examination centre at the specified locations on the right half of the Optical Response Sheet (ORS).
3. Using HB pencil, darken ihc appropriate bubble under each digit of your registration number and the letters corresponding to your paper code.
4. All questions in this paper arc of objective type.
5. Questions must be answered on the ORS by darkening the appropriate bubble (marked A. B. C, Pi using HB pencil against the question number on the left hand side of the ORS. For cach question darken the bubble of Ihe correct answer. In ease you wish to change an answer, erase the old answer completely. More than one answer bubbled against a question will he treated as an incorrect response.
6. There arc a total of 65 questions canning 100 marks.
7. Questions Q. I - Q.25 will carry I-mark each, and questions Q.26 - Q.55 will carry 2-marks each.
8. Questions Q.48 - Q.51 (2 pairs) are common data qttcslions and question pairs (Q.52. Q 53) and (Q.54. Q.55) urc linked answer questions. The answer to ihe second question of the linked answer questions depends on the answer to the first question of the pair. If the first question in the linked pair is wrongly answered or is un-attemptcd. ihcn the answer to the second question in ihe pair will not be evaluated.
9. Questions Q.5G - Q.65 belong to General Apiitude (CiA). Questions Q.56 - Q.60 will carry 1-mark each, and questions Q.6I - Q.65 will cam1 1 marks each. The GA questions will begin on a fresh page starting from page 15.
10. Un-attempted questions will carry zero marks.
11. Wrong answers will carry NEGATIVE marks. For Q.l - Q,25 and Q,56 - Q.6U, *A mark will be deducted for each wrong answer. For Q.26 - Q.51 and Q.61 - Q.65, % mark will be deducted for each wrong answer. The question pairs (Q.52, Q.5.1). and (Q.54, Q.55) arc questions with linked answers. There will be negative marks only for wrong answer to the first question of the linked answer question pair i.e. for Q.52 and Q.54, 3/t mark will be deducted for each wrong answer. There is no negative marking for Q.53 and Q.55.
12. Calculator (without data connectivity) is allowed in ihe examination hall.
13. Charts, graph sheets or tables are NOT allowed in the examination hall-
14. Rough work can be done on ihe question paper itself Additionally, blank pages are provided at the end of the question paper for rough work.
:oio
Q.l - Q,25 carry one mark each.
Q. I Let G = (V. E) be a graph. Define {C/) = X(/. where / i* the number of vertices of dcgmc d
j
in G. If 5 and 7 a re two different trees *ith f(.V) = (7 ). then
(A) | 51 = 2| X] (B) j 51 - | 7| 1 (C)|5[|T| (D} \ 5 ] = | T\ + 1
Q.2 Newton-Raphson method is used to compute a root of the equation a2-13 = 0 with 3.5 as the initial value. The approximation after one iteration is
(A) 3,575 (B) 3.677 (C) 3.007 (D) 3.607
Q.3 What is the possible number of reflexive relations on a set of 5 elements?
(A) 210 (B) 2n (C) 2*' (D) 2a
Q.4 Consider the set S = [I, O)2 J, where (0 and ay are cube roots of unity. If * denotes the multiplication operation, the structure {S, *} forms
(A) a group (B) a ring (C) an integral domain (D) afield
Q.5 What is the value of lim 1 ?
i, ti)
Q.6 The mintermexpansion of f(P,Q,R) = PQ + QR + PRis
(A) m~ + m4 + mb + m, (B) it\ + //j, -f + m}
(C) mn +m{ + mb 4-m, (D) ni* + + /*,
Q 7 A main memory unit with a capacity of 4 megabytes is built using 1M x 1-bil DRAM chips. Each DRAM chip has IK rows of cells with IK cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The lime required to perform one refresh operation on all the colls in (he memory unit is
(A) 100 nanoseconds (B) 100*2 nanoseconds
(C) 100*2 nanoseconds (D) 32()0*2aj nanoseconds
Q.8 P is a 16-bit signed integer. The 2s complement represent ion of P is (F87B),*. The 2s complement representation of R*P is
(A) (C3D8)lS (B)(187B>|6 (O <Pfi78)]b (D) miBU
(A)F@Q@R (B)PQR (C) P + Q + R (D) P + Q + R
Q.10 In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?
Q 9 The Boolean expression for the output / of the multiplexer shown beJow is
(A) 0 (B)l (C) (n-i)f2 (D) n-1
Q. JI What does the following program print?
include <stdio.h>
void f(int *p, int *q){
P * q:
*p = 2;
)
ir.t i = 0, j = 1 ;
int ma i n ;} {
f (ii, ij) ;
pnnLf p%d %d\n", i, j} ; retain 0;
}
(A) 2 2 (B) 2 1 (O 0 1 (D) 0 2
Q.12 Two alternative packages A and B are available for processing a database having 10* records. Package A requires 0.0001 Jtime units and package B requires J0nloglvn lime units to process n records. What is the smallest value of k for which package B will be preferred over A?
Q. 13 Which data structure in a compiler is used for managing information about variables and their attributes?
(A) Abstract syntax tree (B) .Symbol table
(C) Semantic stack (D) Parse table
Q. 14 Which languages necessarily need heap allocation in the runtime environment?
(A) Those that support recursion.
(B) Those that use dynamic scoping.
(C) Those that alio* dynamic data structures.
(D) Those that use global variables.
Q.J5 One of the header fields in an IP datagram is ihe Timc-lo-Lwc (TTL) field- Which of the following statements best explains the need for ihis field?
(A) It can be used to prioritize packets
(B) It can be used to reduce delays.
(C) It can be used to optimize throughput.
(D) It can be used to prevent packet looping.
Q. 16 Which one of ihe follow ii*g is not a clieni-server application?
(A) Internet chat (B) Web browsing
(Q E-mail (D) Ping
Q. 17 Le t L1 be a recursive lang uage. Let L2 and L 3 be I anguage s that are recursi vd y enumerabl e bu I not recursive. Which of the following statements is not necessarily true?
(A) L2 - LI is recursively enumerable.
(R) LI - L3 is recursively enumerable.
(C) L2 P| L3 is recursively enumerable.
(D) L2 U L3 is recursively enumerable.
Q. 18 Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non*rool node?
(A) 1 (B) 2 (C)3 (D) 4
Q. 19 A relational schema for a train reservation daLabase is given below.
Passenger (pid, piiarne* age)
Reservation(pid r class, tid)
Table: Passenger____Table: Reservaticn_
|
pid |
pname |
Age |
|
0 |
Sachin |
65 |
|
1 |
Rahul |
66 |
|
2 |
Sourav |
67 |
|
3 |
Anir |
69 |
|
pid |
class |
tid |
|
0 |
AC |
8200 |
|
1 |
AC |
8201 |
|
2 |
SC |
8201 |
|
5 |
AC |
8203 |
|
1 |
sc |
8204 |
|
3 |
AC |
8202 |
What pids are returned by the following SQL query for the above instance of the tables?
SELECT pid FROM Reservation WHERE class = 'AC' AND EXISTS (SELECT *
PROW Passenger
age > 6S AND ?as?5angor . pid = Reservation .pid)
(Bj 1.2
(C) 1. 3
(D)K5
(A) 1.0
Q.20 Which of the following concurrency control protocols ensure both conflict serializability arid freedom from deadlock?
(A) 1 only
(O Bath I andJJ
(D) Neither I nor II
f. 2-phase locking 11. Tinte-slump ordering
(IS) II only
Q.21 The cyclomatic complexity of cach of the modules A and B shown below is 10. What us the cyclomacic complexity of die sequential integration shown on the right hand side?
 |
|
(C) 20 |
(B) 21
(D) 10
(A) )9
Q.22 What is ihe appropriate pairing of items in the two columns listing various activities encountered in a software life cycle0
1. Module Development and Integration
P. Requirements Capture Q. Design R. Implementation S. Maintenance
2. Domain Analysis
3- .Structural and Behavioral Modeling A, Performance Tuning
(A) P-3 Q-2 R-4 S-l (B) P-2 Q-3 R-l S-4 (O P-3 Q-2 R-l S-4 (D) P-2 Q-3 R-4 S-l
Q.23 Consider the methods used by processes PI and P2 for accessing (heir critical sections whenever needed, as given below The initial values of shared boolean variables SI and S2 are randomly assigned
|
Method used by PI |
Method used by P2 |
|
while [SI == S2); Critical Section SI - S3; |
While (Si i- S2); Critical Section S2 = not(SI); |
Which one of the following statements describes the properties achieved?
(A) Mutual exclusion but not progress
(B) Progress but not mutual exclusion
(C) Neither mutual exclusion nor progress {D) Boih mulual exclusion and progress
Q.24 A system uses FIFO policy for page replacement. 11 has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct p.ies in some order and then accesses the same 100 pages hnt now in the reverse order. How many page faults will occur?
(A) 196
<B)102
(C) 197
(D) 195
5r?J
rs
Q.25 Which of the following statements are true?
I. Shortest remaining iirnc first scheduling may cause starvation
JI- Preemptive scheduling may cause starvation
III. Round robin is better than FCFS in terms of response lime
(A) I only (B) I and III only (O 11 and III only (D) 1. II and QI
Q.26 - Q,55 carry two marks each,
Q.26 Consider a company that assembles computers. The probability of a faulty assembly of any computer is />. The company therefore subjects cach computer to a testing process. This tesiing process gives the correct result for any computer with a probability of q. What is the probability of a computer being declared faulty7
(A)pq+(l-p)(l-q) (B)(l-q)p (C)(l-p)q (D) pq
Q.27 What is the probability that a divisor of 10W is a multiple of 1090?
(A) 1/625 (B) 4/625 (C) 12/625 (D) 16/625
Q.28 The degree sequence of a simple graph is the scquencc of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
1 7. 6,5,4, 4, 3 2, 1
H. 6, 6. 6,6. 3. X 2, 2
HI 7, 6, 6,4,4. 3,2.2
IV. 8. 7, 7,6.4, 2, L 1
(A) 1 and H (B) 111 and IV (O IV only (D) II and IV
Q.29 Consider the following matrix
"2 3'
.4=
If the eigenvalues of A are 4 and 8, then
(A).* = 4f v = 10 (B) A = 5, y =s S (C)x = 3,,y = 9 (D) jc = ~4. > = 10
Q.30 Suppose the predicate F(x,y,t) is used to rcpics&nt the staiemenl that person x can fool person y at lime /. Which one of the statements below expresses best the meaning of the formula
(A) Everyone can fool some person at some time.
(B) No one can fool everyone all the time.
(C) Everyone cannot fool some person all the time.
(D) No one can fool some person ai some lime.
Q 3J What is (he boolean expression for the oulput / of the combinational logic circuit of NOR gales given below?
|
0 R |  |
(A) Q + R
(B) P + Q
(C) P + R
(D) P + Q + R
Q.32 In the sequential circuit shown below, if the initial value of the output QxQq is 00. what are (he nexi fouT values of QiQq ?
(A) ) 1,10,01,00 (B) 10,1 K0 J* 00 (C) 10,00,01,11 (D) 11,10,00,01
Q.33 A 5-siage pipelined processor has Instruction Fetch (IF), Instruction Decode {ID). Operand Fcich (OF*. Perform Operation fPO) unj Wriie Operand (WO) *tui:s. The II**. II). OF Jild WO stupes lake I clock cycle each for any instruction. The VO si age takes 1 clock cycle for ADD and SUB instructionv 3 clock cycles for MUL instruction, and 6 clock cycles for 1)1 V instruction respectively. Operand forwarding is used in the pipeline. What is ihc number of clock cyclcs needed to execute the following sequence of instruclions?
fnsiruclion Meaning of instruction
t0: MULR.K* Rt Rc'R,
/,; D1V R,,R,, R, Rs*-RJR*
/*: ADD R*. Rt. R; R: R*+R:
SL'li Kj, R=1 R* Rs K; - R*
<A) 13 W 15 (C) 17 (D) 19
Q.34 The weight of a sequence ayaw...yaHof real numbers is defined as + <7,/2 + ... + /2"l. A subsequence of a sequence is obtained by dele ling some elements from the sequence, keeping the order of the remaining elements the same. Lei X denote the maximum possible weight of a subsequence of .........., and Y the maximum possible weighi of a subsequence of
,. Then X is equal to
(A)max(*\ci0 + H + (C) iru\{Y.ti0 + 2V) (D) <j0 + Yf2
Q.35 What is the value printed by the following V program?
#include <stdio.h> int f{int *a, int n}
{
if (n <= 0} return Or
else if (*a % 2 == 0) return *a + (a+1,n-1); elso return *<x - f{a+l,n-l);
)
int main( }
{
int all = (12, 7. 13. 4, 11, 6); printf t"fcd"* f(o,6)); return 0;
)
(O 15
(A) -9
<K>>
(D) 19
zmi!
0 30 The following (' function takes a singly-linked list us inpul argument. It modifies ihe list by moving ihe last element to the fronl of the list and returns the modified list. Some part of the code is left blank.
typedef struct node { int value; struct node next;
) Node;
Node *move_to_ront{Node *hcad) {
Mode *p, *q;
if ((head - = NULL) || (head->next = = NULL)) return head; q = NULL; p = head; while (p->next = NULLl I
q = p;
p = p->next;
}
return head;
}
Choose the correct alternative to replace the blank line.
(A)q = NULL; p->next = head; head = p;
(B)q->next = NULL; head = p; p->next = head;
(C)head = p; p->next = q; q->next = NULL;
(D)q->next = NULL; p->next = head; head = p;
Q.37 The program below uses six temporary variables at b, c, d, e, f
|
a = |
1 | |
|
b = |
10 | |
|
c = |
20 | |
|
d = |
a + |
b |
|
e = |
c + |
d |
|
f = |
c + |
e |
|
b = |
c + |
e |
|
e = |
b + |
f |
|
d = |
5 + |
e |
|
return d |
1 + | |
Assuming ihat all operations lake iheir operands from registers, whai is the minimum number of registers needed lo cxccutc Ibis program without spilling?
(A) 2 (I*)!* (0 4 (D) 6
Q.38 The grammar S aSa | hS | c is
(A)LL(l)but roi LR(I) (IS) LR(11 but not LL( 11
(C) Both LL( 1) and LR(J) ([)) Neiiher LL( J) nor LR(I)
0 39 Let = \ n (0 + })* J h has even number of ls|, i.e. /. is ihe sei of all hit strings with even tiumber of U. Which one of ihe regular expressions below represents /.?
(AMO* 10*1)* (H) IJ*( l(>*10*j* ((') (J*( 10* !)*(> <D) 0*1(10*I)*]0*
Aif2*
cs
Q4D Consider ihe languages /./ = ( O'lJ | i* j }. 12 = { OV | / = j }, L? = \ 0'1; | t = 2j + l).
!A = (OT | ;* 2j }. Which one of (he following statements is true?
(A) Only L2 is context free.
(B) Only L2 and L3 are context free.
(C) Only U and L2 are context free.
(D) All are context free.
Q.4J L*t w be any string of length n in (0,1}V Let L be the set of all substrings of h\ What is the minimum number of states in a n on-deterministic finite automaton that accepts L7
(A) n-1 (B)n {C) n+\ (D) 2-1
Q.42 Consider the following Schedule for transactions T LT2 and T3:
X! T2 n
Read (X)
Read ( Y)
Read ( Y)
Write ( V
Write (X)
Write (X)
Read (X)
Write {X)
Which one of the schedules below is the corTect serialization of the above?
(A) T| T3 T2 (B) T2 * T1 ->T3
(C) T2 * T3 Tl (lT3Tl T2
Q 43 The following functional dependencies hold for relations R(A, B, C) and S(B, D. E);
B -+ A,
A->C
The relation R contains 200 tuples and the relation S contains 100 tuples What is the maximum number of tuples possible in the natural join ft M .V ?
(A) 100 (B) 200 <C) 300 (D) 2OM
Q.44 The following program is to be lesied for sUlcmcni coverage begin
if (a == b) (Si; exit;} else if (c == d) {S2;} else (S3; exit;}
S4;
end
The lesl cases TL T2.T3 and T4 given below are expressed in terms of the properties satisfied by the values of variables n, b, c and d. The exatt values are noi given.
TI: a, b, c and d are all equal T2: a, fc>, c and d are all distinct
T3: a = b and c J = d T4: a !- b and c = d
Which of the test suites given below ensures coverage of statements SI, S2, S3 and S4?
(A) TI. T2, T3 (B) T2, T4 (C) T3, T4 (D) TL T2, T4
|
Q.45 The following program consists of 3 concurrcni processes and 3 binary semaphores The semaphores are initialized as SO=l, $2=0, | ||||||
|
How many limes will process PO print *0l?
(A) At least twice (B) Exactly iwice (C) Exactly thrice (D) Exactly once
Q.46 A system has n resources R(> .R t. and k processes Po. -.Pi i The implementation of the resource request logic of each process P* is as follows:
if (1%2==0} {
if (i<n) request ; if (i+2 < n) request R;
>
else C
i (i<n) request Rr. i ; if (i2<n) request Kn. y,
}
In which one of the following situations is a deadlock possible?
(A)h = 4D,*2G (B)n = 2I.A = 12 ') = 2(J. A* = 10 (D) w = 41.*= 19
Q 47 Suppose computers A and B have IP add re sscs KJ. 1(35.1.113 and 10-105-1-91 respeclively and they both use the same netmask N. Which of ihe values of N given below should not be used if A and B should belong to the same network?
(A) 255.255.255.0 (B) 255.255.255.128 (C) 255.255.255.192 (D) 255255 255.224
Common Data Questions Common DaU for Questions 48 and 49:
A computer system has an Ll cache, an L2 cache. ;ind a main memory unit connected as shown below. The block si7 in LJ cache is 4 words The block siae in L2 cache is 16 words. The memory access limes are 2 nanoseconds. 20 nanoseconds and 200 nanoseconds for LI cache..L2 cache and main memory unii respectively.
Q.4S When Iherc is a miss in Ll cache and a hit in L2 cache, a block is transferred from L2 cuchc to Ll cache. What is the time taken for this transfer?
(A) 2 nanoseconds (B) 20 nanoseconds (C) 22 nanoseconds (D) 88 nanoseconds
Q.49 When there is a miss in both Ll cache and L2 cache, first a block ts transferred from main incmory to L2 cache, and then a block is transferred from L2 cache to Ll cache. What is the total time taken for these transfers?
(A) 222 nanoseconds (B) 88$ nanoseconds
(C) 902 nanoseconds (D) 968 nanoseconds
Common Data for Questions 50 and 51:
|
>4 set |
(0,1.23,4) | ||
|
1 |
8 |
1 |
4 |
|
0 |
12 |
4 |
9 |
|
12 |
0 |
7 |
3 |
|
4 |
7 |
0 |
2 |
|
9 |
3 |
2 | |
Consider a complete undirected graph wit weight of the edge |fj|.
/0
8 I
Q.50
What is the minimum possible weight of a spanning tree 7 in this graph such (hat vertex 0 is a leaf node in the tree T?
(A) 7 (Bj 8 ((*) 9 (D) 10
Q.51 What is the minimum possible weight of a path P from vertex I to vertex 2 in this graph such that P contains at most 3 edges?
(A) 7 (B)S (C)0 (D) 10
:oin
Statement for Linked Answer Question* 52 and 53:
A hash table of length 10 uses open addressing with hash function h(k) = k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.
|
0 | |
|
1 | |
|
2 |
42 |
|
3 |
23 |
|
4 |
.34 |
|
5 |
52 |
|
6 |
46 |
|
7 |
33 |
|
8 | |
|
9 |
Q.52 Which one of the following choices gives n possible order in which the key values could have been inserted in the table?
(A) 46, 42, 34,52,23* 33
(D) 42, 46. 33. 23. 34,52
Q.53 How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?
(A) 10 (B)20 (C) 30 (D) 40
Q.54 All the router* use the distance vector based routing algorithm to update their routing tables. Each router slans with its routing table initialized to contain an entry for each neighbour with the weight of the respective connecting link. After all tlw routing tables stabilize, how many links in the network will never be used for carrying any data?
(A) 4 (B) 3 (C)2 (D) 1
Statement for Linked Answer Questions 54 and 55:
|
Consider a network with 6 rouiers Rl to R6 connected with links having weights as shown in the following diagram. |
 |
Q.55 Suppose ihe weights of all unused links in the previous question are changed to 2 and the distance vector aJgonthm is used again until alJ routing tables stabilize. How many links will now remain unused?
(A) 0 (B) 1 (C)2 (D) 3
:oio
General Aptitude (GA) Questions Q.56 - Q.60 carry one mark each,
Q.56 Choose the most appropriate word from the options given Mow to complete the following sentence:
His rather casual remark* on politics______ bis lack of seriousness about the subject
(A) masked
(B) belied
(C) betrayed {D) suppressed
Q.57 Which of ihe following options is the closest in meaning to the word he low:
Circuitous
(A) cyclic
(B) indirect
(C) confusing
(D) crooked
Q.58 Choose the most appropriate word from ihe options given below to complete the following sentence:
If we manage to_our natural resources, we would leave a better planet for
(A) uphold
(B) restrain
(C) cherish
(D) conserve
Q.59 25 persons are in a room, 15 of them play hockey, 17 of them play football and 10 of them play both hockey and football Then the number of persons playing neither hockey nor football is:
(A) 2 (B) 17 (C) Li (D) 3
Q.6L) The question below consists of a pair of related words followed by four pairs of words. Select the pair that best expresses the relation in the original pair.
Unemployed i Worker
(A) fallow: land
(B) unaware; sleeper
(C) wit: jester
(D) renovated; house
Q.61 - Q.65 carry two marks each.
Q.61 If 137 + 276 = 435 how much is 731 + 6727 (A) 534 (B) 1403 (0 1623 (D) 15J3
Q.62 tUri (H). Gita (G). Irfan (!) and Saira (S) arc siblings (i.e. brothers and sjsters). All were bom on T January. The age difference between an) two successive siblings (that is born one after another} is less than 3 years. Given the following facts:
i. Harisagc + Gita's age > Irfan's age + Sairas age
ii. The age difference betwiien Gita and Saira is 1 year However. Gita is not the oldest and Saira is not ihe youngest.
iii. There are no twins.
In what order were they bom (oldest first)?
(A)HSIG (BJSGHI <C) IGSH (D) 1HSG
Q 63 Modern warfare has changed from large scale clashes of armies to suppression of civilian populations. Chemical agents that do their work silently appear to t>e suited to such warfare; and regretfully, there exist people in military establishments who think that chemical agents are useful tools for their cause.
Which of Ihe following statements best sums up the meaning of the above passage:
(A) Modern warfare has resulted in civil strife.
(B) Chemical agents are useful in modern warfare.
(C) Use of chemical agents in warfare would be undesirable.
(D) People ui military establishments like lo use chctnicai agents in war.
Q.64 5 skilled workers can build a wall in 20 days; 8 semi-skilied workers can build a wall in 25 days; )0 unskilled workers can buiJd a wall in 30 days. Tf a team has 2 skilled, 6 semi-skilled and 5 unskilled workers, how long will il lake to build the wail?
(A) 20 days (B)lSdays (C)16days (D)15days
Q 65 Given digits 2. 2. 3, 3, 3T 4T 4, 4, 4 how many distinct 4 digit numbers greater than 3000 can be formed0
(A) 50 (B)5l (0 52 (D) 54
Space for Rough Work
>oio___os
Space for Rough Work
ri/M
Smi t;s
Space for Rough Work
:2/m
os
CS
CS 24
|
Attachment: |
| Earning: Approval pending. |
