GATE Exam Information technology Practice Exam
Which one of the following regular expressions is NOT equivalent to the regular
expression (a +
b
+
c)
*?
(A)
(a*+b*+c*)*
(B)
(a*b*c*)*
(C)
((ab)
*
+c *)
* 1
(D) (a *
b
*
+c *)
*
8. What is the minimum number of NAND gates required to implement a 2-input EXCLUSIVE-
OR function without using any other logic gate?
(A) 3
(B) 4
(C) 5
(D)6
9. Which one of the following statements is FALSE?
(A) There exist context free languages such that all the context free grammars generating
them age ambiguous.
(B) An unambiguous context free grammar always has a unique parse tree for each string of
the language generated by it.
(C) Both deterministic and non-deterministic pushdown automata always accept the same set
of languages
(D) A finite set of string from one alphabet is always a regular language.
10. What is the minimum size of ROM required to store the complete truth table of an 8-bit x
8-bit multiplier?
(A) 32 K x i6 bits
(B) 64 K x i6 bits
(C) i6 K x 32 bits
(D)64 K x 32 bits
11. What is the bit rate of a video terminal unit with 80 characters/line, 8 bits/character and
horizontal sweep time of lOOps (including 20 ps of retrace
time)?
(A) 8 Mbps
(B) 6.4 Mbps
(C) 0.8 Mbps
(D)0.64 Mbps
12. Consider a system with 2 level caches. Access times of Level 1 cache, Level 2 cache and
main memory are 1 ns, iOns, and 500 ns, respectively. The hit rates of Level 1 and Level 2
caches are 0.8 and 0.9, respectively. What is the average access time of the system ignoring
the search time within the cache?
(A) 13.0 ns
(B) 12.8 ns
(C) 12.6 ns
(D) 12.4 ns
13. Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list.
What is the worst-case time complexity of the best known algorithm to delete the node x from
the list?
(A) 0(n)
(B) o(log2
n)
(C)
O(logn)
(D)0(1)
14. Which one of the following is NOT shared by the threads of the same process?
(A) Stack
(B) Address Space
(C) File Descriptor Table
(D) Message Queue
15. Let x be an integer which can take a value of 0 or 1. The statement if(x = 0) x = 1; else x
= 0; is equivalent to which one of the following?
(A) x=1+x;
(B) x=1—x;
(C) x=x—1;
(D)x=1%x;
16. Which of the following commands or sequences of commands will rename a file x to file y
in a Unix system?
I. my y, x II. my x, y III. cp y, x (rm x) IV. cp x, y (rm x)
(A) II and III
(B) II and IV
(C) land III
(D)II only
17. In a software project, COCOMO (Constructive Cost Model) is used to estimate
(A) effort and duration based on the size of the software
(B) size and duration based on the effort of the software
(C) effort and cost based on the duration of the software
(D) size, effort and duration based on the cost of the software
18. The diagram that helps in understanding and representing user requirements for a
software project using UML (Unified Modeling Language) is:
(A) Entity Relationship Diagram
(B) Deployment Diagram
(C) Data Flow Diagram
(D) Use Case Diagram
19. A software organization has been assessed at SEI CMM Level 4. Which of the following
does the organization need to practice beside Process Change Management and Technology
Change Management in order to achieve Level 5?
(A) Defect Detection
(B) Defect Prevention
(C) Defect Isolation
(D) Defect Propagation
20. A software configuration management tool helps in
(A) keeping track of the schedule based on the milestones reached
(B) maintaining different versions of the configurable items
(C) managing manpower distribution by changing the project structure
(D) all of the above
21. Which level of locking provides the highest degree of concurrency in a relational data
base?
(A) Page
(B) Table
(C) Row
(D) Page, table and row level locking allow the same degree of concurrency
22. Which one of the following statements is FALSE?
(A) Packet switching leads to better utilization of bandwidth resources than circuit switching.
(B) Packet switching results in less variation in delay than circuit switching.
(C) Packet switching requires more per packet processing than circuit switching.
(D) Packet switching can lead to reordering unlike in circuit switching.
23. Which one of the following statements is FALSE?
(A) TCP guarantees a minimum communication rate
(B) TCP ensures in-order delivery
(C) TCP reacts to congestion by reducing sender window size
(D) TCP employs retransmission to compensate for packet loss
24. Which one of the following statements is FALSE?
(A) HTTP runs over TCP
(B) HTTP describes the structure of web pages
(C) HTTP allows information to be stored in a URL
(D) HTTP can be used to test the validity of a hypertext link
25. A sender is employing public key cryptography to send a secret message to a receiver.
Which one of the following statements is TRUE?
(A) Sender encrypts using receiver’s public key
(B) Sender encrypts using his own public key
(C) Receiver decrypts using sender’s public key
(D) Receiver decrypts using his own public key
26. A subnet has been assigned a subnet mask of 255.255.255.192. What is the maximum
number of hosts that can belong to this subnet?
(A) 14
(B) 30
(C) 62
(D)126
27. A host is connected to a Department network which is part of a University network. The
University network, in turn, is part of the Internet. The largest network in which the Ethernet
address of the host is unique is:
(A) the subnet to which the host belongs
(B) the Department network
(C) the University network
(D) the Internet
28. In TCP, a unique sequence number is assigned to each
(A) byte
(B) word
(C) segment
(D)message
29. Which of the following objects can be used in expressions and scriplets in JSP
(Java Server Pages) without explicitly declaring them?
(A) session and request only
(B) request and response only
(C) response and session only
(D) session, request and response
30. Consider the following statements:
I. telnet, ftp and http are application layer protocols.
II. EJB (Enterprise Java Beans) components can be deployed in a J2EE (Java2 Enterprise
Edition) application server.
III. If two languages conform to the Common Language Specification (CLS) of the
Microsoft.NET framework,, then a class defined in any one of them may be inherited in the
other.
Which statements are true?
(A) land II only
(B) II and III only
(C) land III only
(D)I, II and III
Q.31 — 90 Carry Two Marks Each
31. Let p, q. r and s be four primitive statements. Consider the following arguments:
P : [(p V q) A (r s) A (p V r)1(s q) s
S:[pA(p r)A(qvr)q
Which of the above arguments are valid?
(A) P and Q only
(B) P and R only
(C) P and S only
(D) P, Q, R and S
32. Let A be an
n x n
matrix of the following form.
31000...000
13100...000
01310...000
0
0 1 3 1 0 0 0
0 0000... 131
o o 0 0 0 0 1 3
What is the value of the determinant of A?
33. Let X and Y be two exponentially distributed and independent random variables with mean
c and 3, respectively. If Z = min(X,Y), then the mean of Z is given by
(A) 1
(B) min(a,fl)
(C)
(D)a+fl
34. Let
H1,H2,H3,...
be harmonic numbers. Then, for
neZ
can be expressed as
(A)
nH1—(n+1)
(B)
(n+1)H—n
(C)
nH—n
(D)
(n+1)H1—(n+1)
35. In how many ways can we distribute 5 distinct balls,
B1,B2,...,B5
in 5 distinct cells,
C1,C2,...,C5
such that Ball B,is not in cell
C,,Vi=1,2,...,5and
each cell contains exactly one
ball?
(A) 44
(B) 96
(C) 120
(D)3125
Statement for Linked Answer Questions 82a and 82b:
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.
82. (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 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 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 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
= 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 100 but finite
(B)
(C) 3
(D) >3 and 100
1. This question paper contains 90 objective questions. Q.1 to Q.30 carry One mark each
and Q.31 to Q.90 carry Two marks each.
2. Answer all the questions.
3. Questions must be answered on special machine gradable Objective Response Sheet
(ORS) by darkening the appropriate bubble (marked A, B, C, D) against the question number
on the left hand side of the ORS, using HB pencil. Each question has only one correct answer.
In case you wish to change an answer, erase the old answer completely using a good soft
eraser.
4. There will be NEGATIVE marking. In Q.1 to Q.30, 0.25 mark will be deducted for each
wrong answer and in Q.31 to Q.90, 0.5 mark will be deducted for each wrong answer. More
than one answer marked against a question will be deemed as an incorrect response and will
be negatively marked.
5. Write your registration number, name and name of the Centre at the specified locations
on the right half of the ORS.
6. Using HB pencil, darken the appropriate bubble under each digit of your registration
number and the letters corresponding to your paper code.
7. No charts or tables are provided in the examination hall.
8. Use the blank pages given at the end of the question paper for rough work.
9. Choose the closest numerical answer among the choice given.
10. Please check all pages and report, if there is any discrepancy.
Q.1 — Q.30 Carry One Mark Each
1. In a population of N families, SOS/c of the families have three children, 3O/c of the families
have two children and the remaining families have one child. What is the probability that a
randomly picked child belongs to a family with two children?
(A) 23
(B) 25
(C) 10
(D) 5
2. In a class of 200 students, 125 students have taken Programming Language course, 85
students have taken Data Structures course, 65 students have taken Computer Organization
course; 50 students have taken both Programming Language and Data Structures, 35
students have taken both Data Structures and Computer Organization; 30 students have
taken both Data Structures and Computer Organizational, 15 students have taken all the three
course. How many students have not taken any of the three courses?
(A) 15
(B) 20
(C) 25
(D)35
3. Let
a(x,y),b(x,y)
and
c(x,y)
be three statements with variables x and y chosen from some
universe. Consider the following statement:
(x)(vy)[(a(x,y)
A
b(x,y)c,y)
Which one of the following is its equivalent?
(A) (vx) (ny) [(a (x, y) v b (x, y)) - c (x, )1
(B) (x)(vy)[(a(x,y) vb(x,y))A-1c(x,y)
(C) (vx)(y)[(a(x,y) Ab(x,y)) c(x,y)
(D) (Vx) (ny) [(a (x, y) v b (x, y)) - c (x, )1
4. Let
R1
be a relation from
A
={1,3,5,7} to
B
= {2,4,6,8} and
R2
be another relation from B
to
C
={1,2,3,4}as defined below:
(i) An element x in A is related to an element y in B (under
R1)
if x+y is divisible by 3.
(ii) An element x in B is related to an element y in C (under
R2)
if x+y is even but not divisible
by 3.
Which is the composite relation R1R2 from A to C?
(A)
R1R2
={(1,2),(1,4),(3,3),(5,4),(7,3)
(B)
R1R2
={(1,2),(1,3),(3,2),(5,2),(7,3))
(C)
R1R2
= {(1,2),(3,2),(3,4),(s,4),(7,2))
(D)
R1R2
={(3,2),(3,4),(5,i),(5,3),(7,i))
5. What is the maximum number of edges in an acyclic undirected graph with n
vertices?
(A) n-i
(B) n
(C) n + 1
(D)2n - 1
6. What values of x, y and z satisfy the following system of linear equations?
i23x 6
134 y=8
2 2 3
z
i2
(A) x=6,y=3,z=2
(B) x=i2,y=3,z=—4
(C)
x=6,y=6,z=—4
(D) x=12,y=—3,z=O
36. If matrix x=r 2 a 1 1 and
X2 —X+I
=0(1 is the identity matrix and 0
—a +a—l 1—a]
is the zero matrix), then the inverse of X is:
(A) r1a _11
(B) r 1-a -1
(C) r —a 1 1
(D) a2—a+i a
37. What is the number of vertices in an undirected connected graph with 27 edges,
6 vertices of degree 2, 3 vertices of degree
4
and remaining of degree 3?
(A) 10
(B) 11
(C) 18
(D)19
38. If
f(1)
= 2,f(2) =
4
and
f(4)
= 16,what is the value of f(3)using Lagrange’s interpolation
formula?
(A) 8
(B) 8
(C) 8
(D)9
39. Consider the following iterative root finding methods and convergence properties:
Iterative root finding Convergence properties methods
(Q) False Position (I) Order of convergence = 1.62
(R) Newton Raphson (II) Order of convergence = 2
(S) Secant (III) Order of convergence = 1 with guarantee of
convergence
(T) Successive Approximation (IV) Order of convergence = 1 with no guarantee of
convergence
(A)Q-II R-IV S-lIlT-I
(B)Q-IIIR-II S-I T-IV
(C)Q-IIR-I S-IVT-III
(D)Q-I R-IV S-Il T-III
40. Let
M (K,Z,r,A,s,F)be a
pushdown automaton, where
K={s,f},F={f},Z={a,b},r
= {a}and
A ={((s,a,s),(s,a)),((s,b,s),(s,a)),((s,a,s),(f,s)),((f,a,a),(f,s)),((f,b,a),(f,s))
Which one of the following strings is not
a
member of
L (M)?
(A)
aaa
(B)
aabab
(C)
baaba
(D) bab
41. Using
a
4-bit 2’s complement arithmetic, which of the following additions will
result in an overflow?
(i) 1100 + 1100 (ii) 0011 + 0111 (iii) 1111 + 0111
(A) (i) only
(B) (ii) only
(C) (iii) only
(D) (i) and (iii) only
42. The number (123456)8 is equivalent to
(A)
(A72E)16
and (22130232)4
(B)
(A72E)16
and (22131122)4
(C)
(A73E)16
and (22130232)4
(D)
(A62E)16
and (22120232)4
43. The function
AB’C
+
A’BC
+
ABC’
+
A’B’C
+
AB’C’
is equivalent to
(A)
AC’+AB+A’C
(B)
AB’+AC’+A’C
(C)
A’B+AC’+AB’
(D)
A’B+AC+AB’
44. A serial transmission Ti uses 8 information bits, 2 start bits, 1 stop bit and 1 parity bit for
each character. A synchronous transmission T2 uses 3 eight bit sync characters followed by 30
eight bit information characters. If the bit rate is 1200 bits/second in both cases, what are the
transfer rates of Ti and T2?
(A) 100 characters/sec, 153 characters/sec
(B) 80 characters/sec, i36 characters/sec
(C) 100 characters/sec, i36 characters/sec
(D) 80 characters/sec, 153 characters/sec
45. If we use internal data forwarding to speed up the performance of a CPU (Ri, R2 and R3
are registers and M[iOO] is a memory reference), then the sequence of operations
Ri
—
M[iOOl
M[iOOl
—* R2
M[iOOl
— R3
Can be replaced by
(A) M[iOOl —* R2
Ri — R3
R2—M[i001 Ri—R2
Ri — R3
(C) (D)
Ri — R2
Ri — M[iOOl
Ri — R3
R2—R3 Ri—M[i001
47. Consider a pipeline processor with 4 stages Si to S4. We want to execute the following
loop: for(i = 1;i <= 1000;i ++) {I1,12,13,14} where the time taken (in ns) by instructions Ii to 14 for stages Si to S4 are given below: The output of Ii for i = 2will be available after (A) ii ns (B) 12 ns (C) 13 ns (D)28 ns Si S2 S3 S4 Ii: 1 2 1 2 12: 2 1 2 1 13: 1 1 2 1 14: 2 1 2 1 48. Consider a fully associative cache with 8 cache blocks (numbered 0-7) and the following sequence of memory block requests: 4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7 If LRU replacement policy is used, which cache block will have memory block 7? (A) 4 (B) 5 (C) 6 (D)7 49. A CPU has only three instructions Ii, 12 and 13, which use the following signals in time steps Ti-T5: Ii: Ti:Ain, Bout, Cm T2:PCout, Bin T3:Zout, Am T4:PCin, Bout T5:End 12: Ti:Cin, Bout, Din T2:Aout, Bin T3:Zout, Am T4:Bin, Cout T5:End 13: Ti:Din,Aout T2:Din, Bout T3:Zout, Am T4:Dout, Am T5:End Which of the following logic functions will generate the hardwired control for the signal Am? (A) Ti.Ii + T2.13 + T4.13 + T3 (B) (Ti + T2 + T3). 13 + Ti.Ii (C) (Ti + T2). Ii + (T2 + T4). 13 + T3 (D) (Ti + T2). 12 + (Ti + T3). Ii + T3 50. In an enhancement of a design of a CPU, the speed of a floating point until has been increased by 20°h and the speed of a fixed point unit has been increased by iO%. What is the overall speedup achieved if the ratio of the number of floating point operations to the number of fixed point operations is 2:3 and the floating point operation used to take twice the time taken by the fixed point operation in the original design? (A) 1.155 (B) 1.185 (C) 1.255 (D)i.285 51. The storage area of a disk has innermost diameter of 10 cm and outermost diameter of 20 cm. The maximum storage density of the disk is 1400 bits/cm. The disk rotates at a speed of 4200 RPM. The main memory of a computer has 64-bit word length and ips cycle time. If cycle stealing is used for data transfer from the disk, the percentage of memory cycles stolen for transferring one word is: (A) O.5°h (B) 1°h (C) 5°h (D)1O°h 52. A program attempts to generate as many permutations as possible of the string ‘abcd’ by pushing the characters a, b, c, d in the same order onto a stack, but it may pop off the top character at any time. Which one of the following strings CANNOT be generated using this program? (A) abcd (B) dcba (C) cbad (D)cabd 53. An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node L(n—1)/2], and doing this adjustment up to the root node (root node is at index 0) in ther order L(n—1)/2],L(n—3)/2],...,0. The time required to construct a heap in this manner is (A) 0(logn) (B) 0(n) (C) 0(nlog logn) (D) 0(nlogn) 54. Which one of the following binary trees has its in-order and preorder traversals as BCAD and ABCD, respectively? 55. Let f(n),g(n) and h(n) be functions defined for positive integers such that f(n) = O(g(n),g(n)) O(f (n)),g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE? (A) f(n)+g(n)=O(h(n))+h(n)) (B) f(n)=O(h(n)) (C) h(n) O(f(n)) (D) f(n)h(n) O(g(n)h(n)) 56. Consider the undirected graph below: Using Prim’s algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree? (A) (E, G), (C, F), (F, G), (A, D), (A, B), (A, C) (B) (A, D), (A, B), (A, C), (C, F), (G, E), (F, G) (C) (A, B), (A, D), (D, F), (F, G), (G, E), (F, C) (D) (A, D), (A, B), (D, F), (F, C), (F, G), (G, E) 57. Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm. Recursive Algorithm Recurrence Relation (P) Binary search (Q) Merge sort (R) Quick sort (S) Tower of Hanoi (I) T(n)=T(n—k)+T(k)+cn (II) T (n) = 2T (n — 1) + 1 (III) T (n) = 2T(n/2) + cn (IV) T(n)=T(n/2)+1 Which of the following is the correct match between the algorithms and their recurrence relations? (A)P-IIQ-III R-IVS-I (B)P-IVQ-IIIR-I S-Il (C)P-III Q-II R-IVS-I (D)P-IV Q-II R-I S-Ill 58. Consider the following C program which is supposed to compute the transpose of a given 4 x 4 matrix M. Note that, there is an X in the program which indicates some missing statements. Choose the correct option to replace X in the program. #include
#define ROW 4
#define CCL 4
mt M[RCW][CCL] ={1,2,3,4,5,6,7,8,9,1O,1 1,12,13,14,15,16};
main ()
{
mt i,j,t;
for (i=O;i<4;++i) { x } fo r( i = 0; i <4; + + i) fo r(j = 0 ;j <4; + +j) printf(”°!od”, M[i][j]); } (A) for(j=0;j<4;++j){ JATE F Li t= M[i][j]; M[i][j]= M[j] [i]; M [j] [i] = t; } (B) for(j=0;j<4;++j){ M[ i] [ii = t; t= M[j][i]; M[j][i]= M[i][j]; } (C) for(j=i;j<4;++j){ t= M[j][i]; M[i][j]= M[j][i]; M [j] [i] = t; } (D) for(j=i;j<4;++j){ M[ i] [ii = t; t= M[j][i]; M[j][i]= M[i][j]; } 59. What is the output of the following program? #include
mt funcf(int x);
mt funcg(int y);
main ()
{
mt x = 5, y = 10, count;
for (count = 1; count <=2; ++count){ y+=funcf(x) + funcg(x); pri ntf (“°Iod “,y); } } funcf (mt x) { mt y; y=funcg(g); return(y); } funcg (intx) { - static mt y = 10; y+=1; return (y+x); } (A) 43 80 (B) 42 74 (C) 33 37 (D)32 32 60. Choose the correct option to fill the ?1 and ?2 so that the program prints an input string in reverse order. Assume that the input string is terminated by a new line character. #include
void wrt_it (void);
mt main (void)
{
printf(”Etner Text”);
pri ntf(”/n”);
wrt_itQ;
pri ntf(”/n”);
return 0;
}
void wrt_it(void)
{
mt C;
if (?l)
wrt_itQ;
}
(A) ?l is getchar() !=‘/n’
?2 is getchar(c);
(B) ?l is (c=getchar() !=‘/n’
?2 is getchar(c);
(C) ?l is c !=‘/n’
?2 is putchar(c);
(D) ?l is (c=getcharQ) !=‘/n’
?2 is putchar(c);
61. Consider the following C program:
#include
typedef struct {
char *a;
char *b;
} t;
void fi (t 5);
void f2 (t *p);
main 0
{
static t s = {“A”, “B”};
printf(”%s % n”, s.a, s.b);
fl(s);
printf(”°Ios
%5 n”, s.a, s.b);
fl(&s);
}
void fl (t 5)
{
s.a = “U”;
s. b =
“I”,
printf(”°Ios
%5 n”, s.a, s.b);
return;
}
void f2 (t *p)
p -
a
=
p - b =
printf(”%s
°IoS
n”, p - a,p - b);
return;
}
What is the output generated by the program?
(A)
AB AB AB AB
(B) uv uv uv uv
(C) VW AB UV VW
(D) vw vw vw uv
62. A disk has 200 tracks (numbered 0 through 199). At a given time, it was servicing the
request of reading data from track 120, and at the previous request, service was for track 90.
the pending requests (in order of their arrival) are for track numbers.
30 70 115 130 110 80 20 25.
How many times will the head change its direction for the disk scheduling policies
SSTF (Shortest Seek Time First) and FCFS (First Come First Serve)?
(A) 2 and 3
(B) 3 and 3
(C) 3 and 4
(D)4 and 4
63. In a certain operating system, deadlock prevention is attempted using the following
scheme. Each process is assigned a unique timestamp, and is restarted with the same
timestamp if killed. Let
P
be the process holding a resource R,
P
be a process requesting for the same resource R, and
T(Ph)
and
T(PP)be
their timestamps
respectively. The decision to wait or preempt one of the processes is
based on the following algorithm.
if
T()y)
x=x-y;
else y = y -
}
return x;
}
What is Cyclomatic complexity of the above module?
(A) 1
(B) 2
(C) 3
(D)4
70. Assume that the delivered liens of code L of a software is related to the effort E in person
months and duration t in calendar months by the relation
LP
*
(E/B)113
* t413, where P and
B are two constants for the software process and skills factor. For a software project, the
effort was estimated to be 20 person months and the duration was estimated to be 8 months.
However, the customer asked the project team to complete the software project in 4 months.
What would be the required effort in person months?
(A) 10
(B) 40
(C) 160
(D)320
71. A software was tested using the error seeding strategy in which 20 errors were seeded in
the code. When the code was tested using the complete test suite, 16 of the seeded errors
were detected. The same test suite also detected 200 non- seeded errors. What is the
estimated number of undetected errors in the code
after this testing?
(A) 4
(B) 50
(C) 200
(D)250
72. What is the availability of a software with the following reliability figures?
Mean Time Between Failure (MTBF) = 25 days
Mean Time To Repair (MTTR) = 6 hours
(A)
i°h
(B) 24°h
(C)
99°h
(D)99.009°h
73. Consider the following entity relationship diagram (ERD), where two entities El and E2
have a relation R of cardinality l:m.
El ____________ m E2
The attributes of El are All, A12 and A13 where All is the key attribute. The attributes of E2
are A21, A22 and A23 where A21 is the key attribute and A23 is a multi-valued attribute.
Relation R does not have any attribute. A relational database containing minimum number of
tables with each table satisfying the requirements of the third normal form (3NF) is designed
from the above ERD. The number of tables in the database is:
(A) 2
(B) 3
(C) 5
(D)4
74. A relational database contains two table student and department in which student table
has columns roll_no, name and dept_id and department table has columns dept_id and
detp_name. the following insert statements were executed successfully to populate the empty
tables:
Insert into department values (1, ‘Mathematics’)
Insert into department values (2, ‘Physics’)
Insert into student values (1, ‘Navin’,l)
Insert into student values (2, ‘Mukesh’,2)
Insert into student values (3, ‘Gita’,l)
How many rows and columns will be retrieved by the following SQL statement?
Select * from student, department
(A) 0 row and 4 columns
(B) 3 rows and 4 columns
(C) 3 rows and 5 columns
(D) 6 rows and 5 columns
75. A relation Empdtl is defined with attributes empcode (unique), name, street, city, state
and pincode. For any pincode, there is only one city and state. Also, for any given street, city
and state, thereis just one pincode. In normalization terms, Empdtl is a relation in
(A) 1 NF only
(B) 2 NF and hence also in 1 NF
(C) 3 NF and hence also in 2 NF and 1 NF
(D) BCNF and hence also in 3 NF, 2NF and 1NF
76. A table Ti in a relational database has the following rows and columns:
The following sequence of SQL statements was successfully executed on table Ti.
Update Ti set marks = marks + 5
Select avg(marks) from Ti
What is the output of the select statement?
Roll
no Marks
i io
2 20
3 30
4 Null
(A) i8.75
(B) 20
(C) 25
(D)Null
77. Consider the following schedule S of transactions Ti and T2:
Ti T2
Read (A)
A = A - iO
Read (A)
Temp = 0.2*A
Write (A)
Read(B)
Write(A)
Read(B)
B=B+iO
Write(B)
B = B+Te m p
Write(B)
Which of the following is TRUE about the schedule 5?
(A) S is serializable only as Ti, T2
(B) S is serializable only as T2, Ti
(C) S is serializable both as Ti, T2 and T2, Ti
(D) S is serializable either as Ti or as T2
78. Consider two tables in a relational database with columns and rows as follows:
Table: Student
Roll_no Name Dept_id
1 ABC 1
2 DEF 1
3 GHI 2
4 JKL 3
Table: Department
Dept_id Dept_Name
1 A
2 B
3 C
Roll_no is the primary key of the Student table, Dept_id is the primary key of the
Department table and Studetn.Dept_id is a foreign key from
Department. Dept_id.
What will happen if we try to execute the following two SQL statements?
(i) update Student set Dept_id = Null where Roll_no =1
(ii) update Department set Dept_id = Null where Dept_id =1
(A) Both (i) and (ii) will fail (B) (i) will fail but (ii) will succeed
(C) (i) will succeed but (ii) will fail (D) Both (i) and (ii) will succeed
79. Consider a table T in a relational database with a key field K. A B-tree of order p is used as
an access structure on K, where p denotes the maximum number of tree pointers in a B-tree
index node. Assume that K is 10 bytes long; disk block size is 512 bytes; each data pointer D
is 8 bytes long and each block pointer
PB
is 5 bytes long. In order for each B-tree node to fit
in a single disk block, the maximum value of p is:
(A) 20
(B) 22
(C) 23
(D)32
80. In a data link protocol, the frame delimiter flag is given by 0111. Assuming that bit
stuffing is employed, the transmitter sends the data sequence 01110110 as
(A) 01101011 (B) 011010110 (C) 011101100 (D)0110101100
81. In a sliding window ARQ scheme, the transmitter’s window size is N and the receiver’s
window size is M. The minimum number of distinct sequence numbers required to ensure
correct operation of the ARQ scheme is:
(A) min(M,N)
(B) max(M,N)
(C) M+N
(D)MN
82. Consider a 10 Mbps token ring LAN with a ring latency of 400ps. A host that needs to
transmit seizes the token. Then it sends a frame of 1000 bytes, removes the frame after it has
circulated all around the ring, and finally releases the token. This process is repeated for every
frame. Assuming that only a single host wishes to transmit, the effective data rate is:
(A) 1 Mbps
(B) 2 Mbps
(C) 5 Mbps
(D)6 Mbps
83. A 25 Kbps satellite link has a propagation delay of 400 ms. The transmitter employs the
“go back n ARQ” scheme with n set to 10. Assuming that each frame is 100 bytes long, what
is the maximum data rate possible?
(A) 5 Kbps
(B) 10 Kbps
(C) 15 Kbps
(D)20 Kbps
84. Consider a parity check code with three data bits and four parity check bits.
Three of the code words are 0101011, 1001101 and 1110001. Which of the
following are also code words?
I. 0010111 II. 0110110 III. 1011010 IV. 0111010
(A) I and III
(B) I, II and III
(C) II and IV
(D) I, II, III and IV
85. Consider a simplified time slotted MAC protocol, where each host always has data to send
and transmits with probability p=0.2 in every slot. There is no back off and one frame can be
transmitted in one slot. If more than one host transmits in the same slot, then the
transmissions are unsuccessful due to collision. What is the maximum number of hosts which
this protocol can support, if each host has to be provided a minimum throughput of 0.16
frames per time slot?
(A) 1
(B) 2
(C) 3
(D)4
86. In the TCP/IP protocol suite, which one of the following is NOT part of the IP
header?
(A) Fragment offset
(B) Source IP address
(C) Destination IP address
(D) Destination port number
87. A TCP message consisting of 2100 bytes is passed to IP for delivery across two networks.
the first network can carry a maximum payload of 1200 bytes per frame and the second
network can carry a maximum payload of 400 bytes per frame, excluding network overhead.
Assume that IP overhead per packet is 20 bytes. What is the total IP overhead in the second
network for this transmission?
(A) 40 bytes
(B) 80 bytes
(C) 120 bytes
(D) 160 bytes
88. Suppose that the maximum transmit window size for a TCP connection is 12000 bytes.
Each packet consists of 2000 bytes. At some point of time, the connection is is slow-start
phase with a current transmit window of 4000 bytes. Subsequently, the transmitter receives
two acknowledgements. Assume that no packets are lost and there are no time-outs. What is
the maximum possible value of the current transmit window?
(A) 4000 bytes
(B) 8000 bytes
(C) 10000 bytes
(D) 12000 bytes
89. Consider an XML file called intro.xml and a document type definition (DTD) file intro.dtd as
follows:
intro.xml
intro.dtd
A validating parser will classify intro.xml as
(A) Well formed and validated
(B) Well formed but not validated
(C) Validated but not well formed
(D) Neither validated not well formed
90. Given below are several usages of the anchor tag in HTML.
I. TestMe
II. Test Me
III. Test ME
IV. Test Me
Which of the above are valid?
(A) I and II only
(B) I and III only
(C) I, II and III only
(D) I, II, III and IV
This question paper contains all objective questions. Q.1 to Q.30 carry One mark each and
Q.31 to Q.80 carry Two marks each. Q.81 to Q.85 each contains part “a” and “b”. In these
questions, parts “a” as well as “b” carry Two marks each.
2. Answer all the questions.
3. Questions must be answered on special machine gradable Objective Response Sheet (ORS)
by darkening the appropriate bubble (marked A, B, C, D) against the question number on the
left hand side of the ORS, using HB pencil. Each question has only one correct answer. In case
you wish to change an answer, erase the old answer completely using a good soft eraser.
4. There will be NEGATIVE marking. In Q.1 to Q.30, 0.25 mark will be deducted for each
wrong answer and in Q.31 to Q.80, 0.5 mark will be deducted for each wrong answer. In Q.81
to Q.85, for the part “a”, 0.5 marks will be deducted for a wrong answer. Marks for correct
answers to part “b” of Q.81 to Q.85 will be given only if the answer to the corresponding part
“a” is correct. HoWever there is no negative marking for part “b” of Q.81 to Q.85. More than
one answer Liubbled against a question will be deemed as an incorrect response.
5. Write your registration number, name and name of the Centre at the specified locations on
the right half of the ORS.
6. Using HB pencil, darken the appropriate bubble under each digit of your registration
number and the letters corresponding to your paper code.
7. Calculator is allowed in the examination hall.
8. Charts, graph sheets or tables are not allowed.
9. Use the blank pages given at the end of the question paper for rough work.
10. Please check all pages and report, if there is any discrepancy.
Q.1 — Q.30 Carry One Mark Each
A bag contains 10 blue marbles, 20 green marbles and 30 red marbles. A marble is drawn
from the bag, its colour recorded and it is put back in the bag. This process is repeated 3
times. The probability that no two of the marbles drawn have the same colour is
(A) 36
(B) 6
(C) 4
(D) 3
2. If the trapezoidal method is used to evaluate the integral [x2dx, then the value obtained
1 1 1
(A) is always >
(B) is always < (C) is always = (D) may be greater or lesser than 3. The determinant of the matrix givën.below is 0 1 0 2 —1 1 1 3 0 0 0 1 1 —2 0 1 (A) -1 (B) 0 (C) 1 (D)2 4. Let L be a regular language and M be a context free language, both over the alphabet . Let LCand MCdenote the complements of L and M respectively. Which of the following statements about the language LC u MC is TRUE? (A) It is necessarily regular but not necessarily context free (B) It is necessarily context free (C) It is necessarily non-regular (D) None of the above 5. Which of the following statements is TRUE about the regular expression 01*0? (A) It represents a finite set of finite strings. (B) It represents an infinite set of finite strings. (C) It represents a finite set of infinite strings. (D) It represents an infinite set of infinite strings. 6. The language {oi 21 < n < 1061 is: (A) regular (B) context free but not regular (C) context free but its complement is not context free (D) not context free 7. Which of the following expressions is equivalent to (A $ B) $ C (A) (A+B+C)(A++) (C) ABC+A(B$C)+B(A$C) (B) (A+B+C)(A++C) (D) None of the above 8. Using Booth’s algorithm for multiplication, the multiplier — 57 will be recorded as (A) 0 —1 0 0 1 0 0 -1 (C) 0 -1 0 0 1 0 0 0 (B) 1 1 0 0 0 1 1 1 (D) 0 1 0 0 -1 0 0 1 9. A dynamic RAM has a memory cycle time of 64 nsec. It has to be refreshed 100 times per msec and each refresh takes 100 nsec. What percentage of the memory cycle time is used for refreshing? (A) 10 (B) 6.4 (C) 1 (D)0.64 10. A two-way switch has three terminals a, b and c. In ON position (logic value 1) a is connected to b, and in OFF position, a is connected to c. two of these two way switches Si and S2 are connected to a bulb as shown below. Which of the following expressions, if true, will always result in the lighting of the bulb? (A) Si.S2 (B) Si+S2 (C) Si$S2 (D)Si$S2 11. How many pulses are needed to change the contents of a 8 bit up-counter from 10101100 to 00100111 (rightmost bit is the LSB)? (A) 134 (B) 133 (C) 124 (D) 123 12. The numbers 1, 2, n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be (A) p (B) p + 1 (C) n - p (D)n — p + 1 13. A function f defined on stacks of integers satisfies the following properties. f(q5) = Oand f (push(S,i)) = max(f (S),0)+ifor all stacks S and integers i. If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(s)? (A) 6 (B) 4 (C) 3 (D)2 14. In a depth first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is (A) k (B) k + 1 (C) n — k - 1 (D)n - k In the following table, the left column contains the names of standard graph algorithm, and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity. (1) Bellman Ford algorithm (A) 0 (mlog n) (2) Kruskal’s algorithm (B) 0 (n3) (3) Floyd-Warshall algorithm (C) 0 (nm) (4) Topological Sorting (D) 0 (n + m) (A)1-C2-A3-B4-D (B)1-B2-D3-C4-A (C)1-C2-D3-A4-B (D)1-B2-A3-C4-D 16. A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key 0i’o 10. if the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted? (A) 2 (B) 3 (C) 4 (D)6 17. A student wishes to create symbolic links in a computer system running Unix. Three text files named “file 1”, “file 2”, and “file 3” exist in her current working directory and the student has read and write permissions for all three files. Assume that file 1 contains information about her hobbies, file 2 contains information about her friends and file 3 contains information about her courses. The student executes the following sequence of commands from her current working directory? In — s file 1 file 2 In — s file 2 file 3 Which of the following types of information would be lost from her file system I. Hobbies II. Friends III. Courses (A) land II only (B) II and III only (C) II only (D)I and III only 18. The shell command find. —name passwd —print is executed in/etc directory of a computer system running Unix. Which of the following shell commands will give the same information as the above command when executed in the same directory? (A) Is passwd (B) cat passwd (C) grep name passwd (D) grep print passwd 19. A user level process in Unix traps the signal sent on a Ctrl-C input, and has a signal handling routine that saves appropriate files before terminating the process. When a Ctrl-C input is given to this process, what is the mode in which the signal handling routine executes? (A) kernel mode (B) superuser mode (C) privileged mode (D) user mode 20. The Function Point (FP) calculated for a software project are often used to obtain an estimate of Lines of Code (LOC) required for that project. Which of the following statements if FALSE in this context. (A) The relationship between FP and LOC depends on the programming language used to implement the software. (B) LOC requirement for an assembly language implementation will be more for a given FP value, than LOC for implementation in COBOL. (C) On an average, one LOC of C++ provides approximately 1.6 times the functionality of a single LOC of FORTRAN. (D) FP and LOC are not related to each other. 21. Consider the entities ‘hotel room’, and ‘person’ with a many to many relationship ‘lodging’ as shown below: Hotel Room Person If we wish to store information about the rent payment to be made by person(s) occupying different hotel rooms, then this information should appear as an attribute of (A) Person (B) Hotel Room (C) Lodging (D)None of these 22. A table has fields Fl, F2, F3, F4, F5 with the following functional dependencies Fl - F3 F2 - F4 (F1.F2) - F5 In terms of Normalization, this table is in (A) 1 NF (B) 2 NF (C) 3 NF (D)None of these 23. A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are (A) 5 (B) 4 (C) 3 (D)2 24. Amongst the ACID properties of a transaction, the ‘Durability’ property requires that the changes made to the database by a successful transaction persist (A) except in case of an Operating System crash (B) except in case of Disk crash (C) except in case of a power failure (D) always, even if there is a failure of any kind 25. Consider the three commands:, PROMPT, HEAD and RCPT. Which of the following options indicate a correct association of these commands with protocols where these are used? (A) HTTP, SMTP, FTP (B) FTP, HTTP, SMTP (C) HTTP, FTP, SMTP (D) SMTP, HTTP, FTP 26. Trace-route reports a possible route that is taken by packets moving from some host A to some other host B. which of the following options represents the technique used by trace- route to identify these hosts? (A) By progressively querying routers about the next router on the path to B using ICMP packets, starting with the first router. (B) By requiring each router to append the address to the ICMP packet as it is forwarded to B. The list of all routers en-route to B is returned by B in an ICMP reply packet. (C) By ensuring that an ICMP reply packet is returned to A by each router en- route to B, in the ascending order of their hop distance from A (D) By locally computing the shortest path from A to B 27. Which of the following statements is TRUE about CSMA/CD (A) IEEE 802.11 wireless LAN runs CSMA/CD protocol (B) Ethernet is not based on CSMA/CD protocol (C) CSMA/CD is not suitable for a high propagation delay network like statellite network. (D) There is no contention in a CSMA/CD network 28. Which of the following statements is FALSE regarding a bridge (A) Bridge is a layer 2 device (B) Bridge reduces collision domain (C) Bridge is used to connect two or more LAN segments (D) Bridge reduces broadcast domain 29. Count to infinity is a problem associated with (A) link state routing protocol (B) distance vector routing protocol (C) DNS while resolving host name (D) TCP for congestion control 30. A HTML form is to be designed to enable purchase of office stationery. Required items are to be selected (checked). Credit card details are to be entered and then the submit button is to be pressed. Which one of the following options would be appropriate for sending the data to the server? Assume that security is handled in a way that is transparent to the form design. (A) only GET (B) only POST (C) either of GET or POST (D) neither gET not POST Q.31 - Q.80 Carry Two Marks Each. 31. Let f be a function from a set A to a set B, g a function from B to C, and h a function from A to C, such that h(a) = g(f (a))for all a E A. Which of the following statements is always true for all such functions f and g? (A) g is onto h is onto (B) h is onto f is onto (C) h is onto g is onto (D) h is onto f and g are onto 32. Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S1 and S2 in C, either S1 S or 2 S1. What is the maximum cardinality of C? (A) n (B) n+1 (C) 2fh+1 (D)n! 33. An unbiased coin is tossed repeatedly until the outcome of two successive tosses is the same. Assuming that the trials are independent, the expected number of tosses is: (A) 3 (B) 4 (C) 5 (D)6 34. Let n = p2q,where p and q are distinct prime numbers. How many numbers m satisfy 1 m nand gcd(m,n) = 1? Note that gcd(m,n) is the greatest common divisor of m and n. (A) p(q—i) (C) (p2 —i)(q—i) 35. What is the value of [(x — r)3 (sin x) dx (A) -1 (B) 0 (B) pq (D) p(p—i)(q—i) (C) 1 (D)t 36. Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE? (A) ((vxP (x) v Q (x))) ((vx ( (x) v (vxQ (x))) (B) (vx(P (x) Q(x))) ((vx(P (x) (vxQ(x))) (C) (vx(P(x)) (vxQ(x))) ((vx(P(x) Q(x))) (D) (vx(P(x))) (vxQ(x))) 37. Consider the non-deterministic finite automation (NFA) shown in the figure. State X is the starting state of the automaton. Let the language accepted by the NFA with Y as the only accepting state be Li. Similarly, let the language accepted by the NFA with Z as the only accepting state be L2. Which of the following statements about Li and L2 is TRUE? (A) Li = L2 (B) LicL2 (C) L2cLi (D) None of the above 38. Let P be a non-deterministic pushdown automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be . Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack. Which of the following statements is TRUE? (A) L(P) is necessarily *but N(P) is not necessarily * (B) N(P) is necessarily * but L(P) is not necessarily * (C) Both L(P) and N(P) is necessarily E* (D) Neither L(P) nor N(P) are necessarily * 39. Consider the regular grammar: S - XaYa X-Za Z - S a B Y — Wa W - Sa Where S is the starting symbol, the set of terminals is {al and the set of non- terminals is {S,W,X,Y,Z}. We wish to construct a deterministic finite automaton (DFA) to recognize the same language. What is the minimum number of states required for the DFA? (A) 2 (B) 3 (C) 4 (D)5 40. A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context free languages. Which of the following statements about L is TRUE? (A) L is necessarily a regular language (B) L is necessarily a context free language, but not necessarily a regular language (C) L is necessarily a non-regular language (D) None of the above 41. Given below is a program which when executed spawns two concurrent processes: Semaphore X:=0; 1* Process now forks into concurrent processes P1 & P2 *1 P1 : repeat forever P2 : repeat forever V(X); P(X); Compute; Compute; P(X); V(X); Consider the following statements about processes P1 and P2: I: It is possible for process P1 to starve. II. It is possible for process P2 to starve. Which of the following holds? (A) Both I and II are true (B) I is true but II is false (C) II is true but I is false (D) Both I and II are false 42. Two concurrent processes P1 and P2 use four shared resources Ri, R2, R3 and R4, as shown below. P1: P2: Compute; Compute; Use Ri; Use Ri; Use R2; Use R2; Use R3; Use R3; Use R4; Use R4; Both processes are started at the same time, and each resource an be accessed by only one process at a time. The following scheduling constraints exist between the access of resources by the processes: P2 must complete use of Ri before P1 gets access to Ri. P1 must complete use of R2 before P2 gets access to R2. P2 must complete use of R3 before P1 gets access to R3. P1 must complete use of R4 before P2 gets access to R4. There are no other scheduling constraints between the processes. If only binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed? (A) 1 (B) 2 (C) 3 (D)4 44. We have two designs Di and D2 for a synchronous pipeline processor. Di has 5 pipeline stages with execution times of 3 nsec, 2 nsec, 4 nsec, 2 nsec and 3 nsec while the design D2 has 8 pipeline stages each with 2 nsec execution time. How much time can be saved using design D2 over design Di for executing 100 instructions? (A) 214 nsec (B) 202 nsec (C) 86 nsec (D)-200 nsec 45. A hardwired CPU uses 10 control signals Si to SiO in various time steps Ti to T5 to implement 4 instructions ii to 14 as shown below. Ti T2 T3 T4 T5 S2, S4, Ii Si, S3, S5 S6 Si, S7 Sb S3, S8 1 Si, S3, 2 S5 S8, S9, Sb S5, S6, S7 S6 Sb 1 Si, S3, 3 S5 S7, S8, Sb S2, S6, S9 Sb Si, S3 1 Si, S3, S2, S6, 4 S5 S7 S5, Sb S6, S9 SiO Which of the following pairs of expressions represent the circuit for generating control signals S5 and Sb respectively [(Ij+Ik)Tnindicates that the control signal should be generated in time step Tnif the instruction being executed is If or 1k]. (A) S5 =Ti + 12 .T3&SiO = (Ii + 13) .T4+ (12 + 14) .T5 (B) S5 = Ti + (12 + 14) . T3 & Sb = (Ii + 13) . T4 + (12 + 14) . T5 (C) S5 =Ti + (12 + 14) .T3&SiO = (12 + 13 + 14) .T2 + (Ii + 13) .T4+ (12 + 14). T5 (D) S5 = Ti + (12 + 14) . T3 & Sb = (12 + 13) . T2 + 14. T3 +(Ii + 13) . T4 + (12 + 14) . T5 46. A line L in a circuit is said to have a stuck at 0 fault if the lien permanently has a logic value 0. Similarly a line L in a circuit is said to have a stuck at 1 fault if the line permanently has a logic value 1. a circuit is said to have a multiple stuck at fault if one or more lines have stuck at faults. The total number of distinct multiple stuck at faults possible in a circuit with N lines is: (A) 3” (B) 3”' — 1 (C) 2”' — 1 (D) 2”' (A) (1053.6)8 (B) (1053.2)8 (C) (1024.2)8 (D) None of these 49. An instruction set of a processor has 125 signals which can be divided into 5 groups of mutually exclusive signals as follows: Group 1: 20 signals, Group 2: 70 signals, Group 3: 2 signals, Group 4: 10 signals, Group 5: 23 signals. How many bits of the control words can be saved by using vertical microprogramming over horizontal microprogramming? (A) 0 (B) 103 (C) 22 (D)55 50. In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number
of nodes in the tree is:
(A)
T(n)=8(logn)
(C)
T(n)=8(n)
(B)
T(fl)r=8(fi)
(D)
T(n) = 8(nlogn)
52. Let G be a weighted undirected graph and e be an edge with maximum weight in G.
Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the
following statements is always TRUE?
(A) There exists a cutest in G having all edges of maximum weight
(B) There exits a cycle in G having all edges of maximum weight
(C) Edge e cannot be contained in a cycle
(D) All edges in G have the same weight
53. The following C function takes two ASCII strings and determines whether one is an
anagram of the other. An anagram of a string s is a string obtained by permuting the letters in
s.
mt anagram (char *a, char *b){
mt count [1281,1;
for (j = 0; j < 128; j++) count[j]=0; j = 0; while (a[j] && b[j]){ A; B; } for (j = 0; 1 < 128; j++) if (count[j]) return 0; return 1; } Choose the correct alternative for statements A and B. (A) A: count [a[j]]++ and B: count[b[j]] (B A: count [a[j]]++ and B: count[b[j]]++ (C) A: count[a[j++]]++ and B: count[b[j]] (D A: count[a[j]]++ and B: count[b[j++]] 54 54. The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution? struct node (mt value; struct node * next;}; void rearrange (struct node *list) { struct node *p, *q; mt temp; if (!list list - next) return; p = list; q = list - next; while (q) { temp = p - value; p - value = q - value; q - value = temp; p = q - next; q = p? p - next; 0; } } (A) 1, 2, 3, 4, 5, 6, 7 (B) 2, 1, 4, 3, 6, 5, 7 (C) 1, 3, 2, 5, 4, 7, 6 (D) 2, 3, 4, 5, 6, 7, 1 A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be (A) 8, 7, 6, 5, 4, 3, 2, 1 (B) 1, 2, 3, 4, 8, 7, 6, 5 (C) 2, 1, 4, 3, 6, 7, 8, 5 (D) 2, 1, 4, 3, 7, 8, 6, 5 56. Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is: (A) 4 (B) 7 (C) 23 (D)99 57. What is the output printed by the following program? # include
mt f(int n, mt k) {
if (n = = 0) return 0;
else if
(n°1o2)
return f(n/2, 2*k) + k;
else return f(n/2, 2*k) — k;
mt main () {
printf(”°Iod”,f(20,1));
return 0;
(A) 5
(B) 8
(C) 9
(D)20
58. Let a be an array containing n integers in increasing order. The following algorithm
determines whether there are two distinct numbers in the array whose difference is a specified
number S > 0.
= 0; j =1;
while (j < n) { if (E) j++; else if (a[j] — a[i] ==S) break; else i++; } if (j < n) printf(”yes”) else printf (“no”); Choose the correct expression for E. (A) a[j] — a[i] > S
(B) a[j] — a[i] < S (C) a[i] — a[J] < S (D) a[i] — a[J] > S
59. Let a and b be two sorted arrays containing n integers each, in non-decreasing order. Let
c be a sorted array containing 2n integers obtained by merging the two arrays a and b.
assuming the arrays are indexed starting from 0, consider the following four statements.
I. a[i] b[i] c[2i] a[i]
II. a[i] b[i] c[2i] b[i]
III. a[i] b[i] c[2i] a[i]
IV. a[i] b[i] c[2i] b[i]
Which of the following is TRUE?
(A) only I and II
(B) only I and IV
(C) only II and III
(D) only III and IV
60. We wish to schedule three processes P1, P2 and P3 on a uniprocessor system. The
priorities, CPU time requirements and arrival times of the processes are as shown below.
We have a choice of preemptive or non-preemptive scheduling. In preemptive scheduling, a
late-arriving higher priority process can preempt a currently running process with lower
priority. In non-preemptive scheduling, a late arriving higher priority process must wait for the
currently executing process to complete before it can be scheduled on the processor.
What are the turnaround times (time from arrival till completion) of P2 using preemptive and
non-preemptive scheduling respectively?
Process Priority CPU time
required Arival time (hh:mm:ss)
P1 10
(highest) 20 sec 00:00:05
P2 9 10 sec 00:00:03
P3 8 (lowest) 15 sec 00:00:00
(A) 30 sec, 30 sec
(B) 30 sec, 10 sec
(C) 42 sec, 42 sec
(D) 30 sec, 42 sec
61. Consider a 2-way set associative cache memory with 4 sets and total 8 cache blocks (0-7)
and a main memory with 128 blocks (0-127). What memory blocks will be present in the
cache after the following sequence of memory block references if LRU policy is used for cache
block replacement? Assuming that initially the cache did not have any memory block from the
current job?
(A)03571655
(B)035791655
(C)05791655
(D)35791655
62. Two shared resources
R1
and R2are used by processes
F
and
P2.
Each process has a
certain priority for accessing each resource. Let denote the priority of P,for accessing
R.
A
process P,can snatch a resource Rkfrom process Pif T,kis greater than
TJk.
Given the following:
I. i 100000, enhance it by
6°h
The IT staff has written three different SQL scripts to calculate enhancement for
each slab, each of these scripts is to run as a separate transaction as follows:
Ti Update salesinfo
Set commission = commission * 1.02
Where commission < = 50000; T2 Update salesinfo Set commission = commission * 1.04 Where commission > 50000 and commission is <= 100000; T3 Update salesinfo Set commission = commission * 1.06 Where commission > 100000;
Which of the following options of running these transactions will update the
commission of all salespersons correctly?
(A) Execute Ti followed by T2 followed by T3
(B) Execute T2, followed by T3; Ti running concurrently throughout
(C) Execute T3 followed by T2; Ti running concurrently throughout
(D) Execute T3 followed by T2 followed by Ti
68. A table ‘student’ with schema (roll, name, hostel, marks) and another table ‘hobby’ with
schema (roll, hobbyname) contains records as shown below.
The following SQL query is executed on the above tables:
select hostel
from student natural join hobby
where marks >
=
75 and roll between 2000 and 3000;
Relations S and H with the same schema as those of these two tables respectively contain the
same information as tuples. A new relation S’ is obtained by the following relational algebra
operation:
S =
‘1hose/ ((Js.ro//_H.ro// (marks>75
and
ro//>2000 and ro//<3000 (s)) X (H)) The difference between the number of rows output by the SQL statement and the number of tuples in S’ is: (A) 6 (B) 4 (C) 2 (D)O Table student Table hobby Mark Roll Name Hoste l s Roll Hobbyname 179 8 Manoj Rathod 7 95 179 8 Chess 215 4 Soumic Banerjee 5 68 179 8 Music 236 9 Gumma Reddy 7 86 215 4 Music 258 1 Pradeep Pendse 6 92 236 9 Swimming 264 3 Suhas Kulkarni 5 78 258 1 Cricket 271 1 Nitin Kadam 8 72 264 3 Chess 287 2 Kiran Vora 5 92 264 3 Hockey 292 6 Manoj Kunkalikar 5 94 271 1 volleyball 295 Hemant 9 Karkhanis 7 88 287 2 Football 312 5 Rajesh Doshi 5 82 292 6 Cricket 295 9 Photography 312 5 Music 312 5 Chess 69. 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 70. 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 71. 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 72. 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 73. 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 74. 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) 75. 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 76. 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 77. 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. 78. 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 79. 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 80. Given below is an excerpt of an xml specification.
10237623786
0024154807
Given below are several possible excerpts from “libratry.dtd”. For which excerpt would the
above specification be valid?
(A)
(B)
(C)
(D)
Linked Answer Questions: Q.81a to Q85b Carry Two Marks Each.
Statement for Linked Answer Questions 81a and 81b:
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.
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 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
