Question 1

A 
any paper

much paper


no paper


a few paper

Question 2

She enjoyed herself immensely at the party.
She had a terrible time at the party


B 
She had a horrible time at the party

C 
She had a terrific time at the party

She had a terrifying time at the party

ANSWER IS C
Question 3

A 
0.20

0.25


C 
0.30

0.33

ANSWER IS A
(2, 14) (3, 13) (4, 12) (5, 11) Probability = Favorable Outcomes/Total Outcomes Probability = 4/20 = 0.20 Therefore option A is correct
Question 4

Statements: 1. Each step is 3/4 foot high. 2. Each step is 1 foot wide.
A 
Statement 1 alone is sufficient, but statement 2 alone is not sufficient

Statement 2 alone is sufficient, but statement 1 alone is not sufficient


C 
Both statement together are sufficient, but neither statement alone is sufficient

Statement 1 and 2 together are not sufficient

Question 5

A 
Acquiescence – Submission

B 
Wheedle – Roundabout

Flippancy – Lightness


Profligate – Extravagant

Flippancy > lack of respect or seriousness. Acquiescence > the reluctant acceptance of something without protest. Wheedle > use endearments or flattery to persuade someone to do something or Profligate > recklessly extravagant
Explanation:
Question 6

Q.No. Marks AnsweredCorrectly AnsweredWrongly NotAttempted 1 2 21 17 6 2 3 15 27 2 3 1 11 29 4 4 2 23 18 3 5 5 31 12 1
What is the average of the marks obtained by the class in the examination?
2.290


2.970


C 
6.795

D 
8.795

Total marks = 2*21 + 3*15 + 1*11 + 2*23 + 5*31 = 299 Average marks = 299/44 = 6.795
Question 7

took shelter in a thick jungle


B 
open indiscriminate fire

C 
took to flight

unconditionally surrendered

Question 8

Statement: There has been a significant drop in the water level in the lakes supplying water to the city. Course of action: 1. The water supply authority should impose a partial cut in supply to tackle the situation. 2. The government should appeal to all the residents through mass media for minimal use of water. 3. The government should ban the water supply in lower areas
A 
Statement 1 and 2 follow

Statement 1 and 3 follow


Statement 2 and 3 follow


D 
All statements follow

ANSWER IS A
Question 9

A 
32

16


C 
48

8

Question 10

1. p + m + c = 27/20 2. p + m + c = 13/20 3. (p) × (m) × (c) = 1/10
Only relation 1 is true


B 
Only relation 2 is true

Relations 2 and 3 are true


D 
Relations 1 and 3 are true

1  (1  m) (1  p) (1  c) = 0.75 (1) (1  m)pc + (1  p)mc + (1  c)mp + mpc = 0.5 (2) (1  m)pc + (1  p)mc + (1  c)mp = 0.4 (3) From last 2 equations, we can derive mpc = 0.1 After simplifying equation 1, we get. p + c + m  (mp + mc + pc) + mpc = 0.75 p + c + m  (mp + mc + pc) = 0.65 (4) After simplifying equation 3, we get pc + mc + mp  3mpc = 0.4 Putting value of mpc, we get pc + mc + mp = 0.7 After putting above value in equation 4, we get p + c + m  0.7 = 0.65 p + c + m = 1.35 = 27/20
Question 11

ListI ListII A. Condition coverage 1. Blackbox testing B. Equivalence class partitioning 2. System testing C. Volume testing 3. Whitebox testing D. Alpha testing 4. Performance testing Codes: A B C D (a) 2 3 1 4 (b) 3 4 2 1 (c) 3 1 4 2 (d) 3 1 2 4
a


b


C 
c

d

ANSWER IS C
Question 12

T(n) = 2T (n/2) + cn


B 
T(n) = T(n – 1) + T(0) + cn

T(n) = 2T (n – 2) + cn


D 
T(n) = T(n/2) + cn

Question 13

1. L1' (complement of L1) is recursive 2. L2' (complement of L2) is recursive 3. L1' is contextfree 4. L1' ∪ L2 is recursively enumerable
1 only


3 only


C 
3 and 4 only

D 
1 and 4 only

Question 14

∞


0


1


Not Defined

Question 15

A 
a

b


c


B 
d

g(h(x)) = g(x/(x1)) = 1  x/(x1) = 1/(x1) h(g(x)) = h(1x) = (1x)/((1x)  1) = (1x)/x g(h(x)) / h(g(x)) = [1/(x1)] / [(1x)/x] = x/(x1)^{2} x/(x1)^{2} is same as h(x) / g(x)
Question 16

ListI A. Prim’s algorithm for minimum spanning tree B. FloydWarshall algorithm for all pairs shortest paths C. Mergesort D. Hamiltonian circuit ListII 1. Backtracking 2. Greed method 3. Dynamic programming 4. Divide and conquer Codes: A B C D (a) 3 2 4 1 (b) 1 2 4 3 (c) 2 3 4 1 (d) 2 1 3 4
a


b


C 
c

D 
d

Question 17

the selection operation in relational algebra


the selection operation in relational algebra, except that select in SQL retains duplicates


C 
the projection operation in relational algebra

D 
the projection operation in relational algebra, except that select in SQL retains duplicates

Question 18

S1: A memory operand S2: A processor register S3: An implied accumulator register
A 
Either S1 or S2

B 
Either S2 or S3

Only S2 and S3


All of S1, S2 and S3

Question 19

P1() { C = B – 1; B = 2*C; } P2() { D = 2 * B; B = D  1; }
The number of distinct values that B can possibly take after the execution is
A 
3

2


5


D 
4

C = B – 1; // C = 1 B = 2*C; // B = 2 D = 2 * B; // D = 4 B = D  1; // B = 3 C = B – 1; // C = 1 D = 2 * B; // D = 4 B = D  1; // B = 3 B = 2*C; // B = 2 C = B – 1; // C = 1 D = 2 * B; // D = 4 B = 2*C; // B = 2 B = D  1; // B = 3 D = 2 * B; // D = 4 C = B – 1; // C = 1 B = 2*C; // B = 2 B = D  1; // B = 3 D = 2 * B; // D = 4 B = D  1; // B = 3 C = B – 1; // C = 2 B = 2*C; // B = 4
There are 3 different possible values of B: 2, 3 and 4.
Question 20

1. 3, 5, 7, 8, 15, 19, 25 2. 5, 8, 9, 12, 10, 15, 25 3. 2, 7, 10, 8, 14, 16, 20 4. 4, 6, 7, 9, 18, 20, 25
A 
1 and 4 only

B 
2 and 3 only

2 and 4 only


2 only

Question 21

void f1 ( int a, int b) { int c; c=a; a=b; b=c; } void f2 ( int *a, int *b) { int c; c=*a; *a=*b;*b=c; } int main() { int a=4, b=5, c=6; f1(a, b); f2(&b, &c); printf (“%d”, cab); return 0; } 
A 
5

4


C 
5

3

Question 22

2


B 
4

8


D 
16

Explanation: Number of entries in page table = 2^{32} / 4Kbyte = 2^{32 / 212 = 220 Size of page table = (No. page table entries)*(Size of an entry) = 220 * 4 bytes = 222 = 4 Megabytes }
Question 23

Viable prefixes appear only at the bottom of the stack and not inside


Viable prefixes appear only at the top of the stack and not inside


C 
The stack contains only a set of viable prefixes

D 
The stack never contains viable prefixes

Question 24

A


B 
B

C 
C

D

D is a different way of writing A p ↔ q
(p→ q) ∧ (q→p) (⌉p ∨ q) ∧ (q → p) ( As p→ q = ⌉p ∨ q ) (⌉p ∨ q) ∧ (⌉q ∨ p) (⌉p ∧ ⌉q) ∨ (p ∧ q) So, answer C
Question 25

1. XML overcomes the limitations in HTML to support a structured way of organizing content. 2. XML specification is not case sensitive while HTML specification is case sensitive. 3. XML supports user defined tags while HTML uses predefined tags. 4. XML tags need not be closed while HTML tags must be closed.
2 only


1 only


C 
2 and 4 only

3 and 4 only

Explanation:
1.TRUE XML is a structured way of organizing content. 2.FALSE XML is CASE SENSITIVE whereas HTML is NOT case sensitive. 3.TRUE XML facilitates User Defined tags whereas HTML has only PreDefined tags 4.FALSE XML tags MUST be closed while HTML tags may NOT be closed.
Question 26

A 
I and III only

II and III only


C 
I, II and III only

I, II and IV only

Explanation: A = {5, {6}, {7}} Below is Powerset of A { φ, 5, {6}, {7}, {5, {6}}, {5, {7}}, {{6}, {7}}, {5, {6}, {7}} }
I is true, as φ belongs to Powerset. II is true, as an empty set is a subset of every set. III is true as {5, {6}} belongs to Powerset. IV is false, {5, {6}} is not a subset, but {{5, {6}}} is.
Question 27

A 
HTTP, FTP

B 
HTTP, TELNET

FTP, SMTP


HTTP, SMTP

Question 28

 2 2   4 9 
, if the diagonal elements of U are both 1, then the lower diagonal entry l_{22} of L is
A 
4

B 
5

6


7

 2 2  =  l_{11 } 0  *  1 u_{12}   4 9   l_{21} l_{22}   0 1  l_{21} * u_{12} + l_{22} * 1 = 9  (1) We need to find l_{21} and u_{12} l_{21} * 1 + l_{22} * 0 = 4 l_{21} = 4 l_{11} * U_{12} + 0 * 1 = 2 l_{11} = 2 U_{12} = 1 Putting value of l_{21} and u_{12} in (1), we get 4 * 1 + l_{22} * 1 = 9 l_{22} = 5
Question 29

1. If the sequence number of a segment is m, then the sequence number of the subsequent segment is always m+1. 2. If the estimated round trip time at any given point of time is t sec, the value of the retransmission timeout is always set to greater than or equal to t sec. 3. The size of the advertised window never changes during the course of the TCP connection. 4. The number of unacknowledged bytes at the sender is always less than or equal to the advertised window
A 
3 only

B 
1 and 3 only

1 and 4 only


2 and 4 only

Question 30

0, 1, 3, 7, 15, 14, 12, 8, 0


B 
0, 1, 3, 5, 7, 9, 11, 13, 15, 0

0, 2, 4, 6, 8, 10, 12, 14, 0


C 
0, 8, 12, 14, 15, 7, 3, 1, 0

Question 31

2N


N(N – 1)


C 
N(N – 1)/2

(N – 1)^{2}

Question 32

Checksum


B 
Source address

Time to Live (TTL)


D 
Length

Question 33

Θ(logn) for both insertion and deletion


B 
Θ(n) for both insertion and deletion

Θ(n) for insertion and Θ(logn) for deletion


D 
Θ(logn) for insertion and Θ(n) for deletion

Question 34

Dense


Sparse


C 
Clustered

Unclustered

Question 35

A 
63 and 6, respectively

64 and 5, respectively


32 and 6, respectively


31 and 5, respectively

Number of nodes is maximum for a perfect binary tree. A perfect binary tree of height h has 2^{h+1}  1 nodes Number of nodes is minimum for a skewed binary tree. A perfect binary tree of height h has h+1 nodes.
Question 36
CORRECT

A 
0.99

1


99


0.9

S = 1/1*2 + 1/2*3 + 1/3*4 + ..... + 1/99*100 = (1  1/2) + (1/2  1/3) + (1/3  1/4) + .... + (1/99  1/100) = (1 + 1/2 + 1/3 .... 1/99)  (1/2 + 1/3 + 1/4 ... 1/100) = 1  1/100 = 99/100 = 0.99
Question 37

SELECT S. Student_Name, sum(P.Marks) FROM Student S, Performance P WHERE S.Roll_No = P.Roll_No GROUP BY S.Student_Name
The number of rows that will be returned by the SQL query is _________
0


1


C 
2

D 
3

Student_Name Marks Raj 310 Rohit 140
Question 38

A 
Both commutative and associative

Commutative but not associative


Not commutative but associative


Neither commutative nor associative

Question 39

A 
0.462

0.711


0.5


D 
0.652

The probability of sending a frame in the first slot without any collision by any of these four stations is sum of following 4 probabilities Probability that S1 sends a frame and no one else does + Probability thatS2 sends a frame and no one else does + Probability thatS3 sends a frame and no one else does + Probability thatS4 sends a frame and no one else does = 0.1 * (1  0.2) * (1  0.3) *(1  0.4) + (1 0.1) * 0.2 * (1  0.3) *(1  0.4) + (1 0.1) * (1  0.2) * 0.3 *(1  0.4) + (1 0.1) * (1  0.2) * (1  0.3) * 0.4 = 0.4404
Question 40

8


9


C 
10

D 
11

Given a disk with 100 tracks And Sequence 45, 20, 90, 10, 50, 60, 80, 25, 70. Initial position of the R/W head is on track 50. In SSTF, requests are served as following Next Served Distance Traveled 50 0 45 5 60 15 70 10 80 10 90 10 25 65 20 5 10 10  Total Dist = 130 If Simple SCAN is used, requests are served as following Next Served Distance Traveled 50 0 60 10 70 10 80 10 90 10 45 65 [disk arm goes to 100, then to 45] 25 20 20 5 10 10  Total Dist = 140 Extra Distance traveled in SSTF = 140  120 = 10
If SCAN with LOOK is used, requests are served as following
Next Served Distance Traveled 50 0 60 10 70 10 80 10 90 10 45 45 [disk arm comes back from 90] 25 20 20 5 10 10  Total Dist = 120 Extra Distance traveled in SSTF = 130  120 = 10
Question 41

int fun1 ( int n) { int i, j, k, p, q = 0; for (i = 1; i<n; ++i) { p = 0; for (j=n; j>1; j=j/2) ++p; for (k=1; k<p; k=k*2) ++q; } return q; } 
Which one of the following most closely approximates the return value of the function fun1?
n^{3}


n (logn)^{2}


nlogn


D 
nlog(logn)

int fun1 (int n) { int i, j, k, p, q = 0; // This loop runs Θ(n) time for (i = 1; i < n; ++i) { p = 0; // This loop runs Θ(Log n) times. Refer this for (j=n; j > 1; j=j/2) ++p; // Since above loop runs Θ(Log n) times, p = Θ(Log n) // This loop runs Θ(Log p) times which loglogn for (k=1; k < p; k=k*2) ++q; } return q; }
T(n) = n(logn + loglogn) T(n) = n(logn) dominant But please note here we are return q which lies in loglogn so ans should be T(n) = nloglogn Refer this for details.
Question 42

40, 30, 20, 10, 15, 16, 17, 8, 4, 35


B 
40, 35, 20, 10, 30, 16, 17, 8, 4, 15

40, 30, 20, 10, 35, 16, 17, 8, 4, 15


D 
40, 35, 20, 10, 15, 16, 17, 8, 4, 30

40 / \ 30 20 / \ / \ 10 15 16 17 / \ 8 4
After insertion of 35, we get
40 / \ 30 20 / \ / \ 10 15 16 17 / \ / 8 4 35
After swapping 35 with 15 and swapping 35 again with 30, we get
40 / \ 35 20 / \ / \ 10 30 16 17 / \ / 8 4 15
Question 43

begin q := 0 r := x while r >= y do begin r := r – y q := q + 1 end end
The post condition that needs to be satisfied after the program terminates is
{r = qx + y ∧ r < y}


B 
{x = qy + r ∧ r < y}

{y = qx + r ∧ 0 < r < y}


{ q + 1 < r–y ∧ y > 0}

1) It initializes r as x. 2) It repeatedly subtracts y from r until r becomes smaller than y. For every subtraction, it increments count q. 3) Finally r contains remainder, i.e., x%y and q contains ⌊x/y⌋
See below pseudo code with comments.
begin q := 0 // q is going to contain floor(x/y) r := x // r is going to contain x % y // Repeatedly subtract y from x. while r >= y do begin r := r – y q := q + 1 end end
Question 44

Pr = 0


B 
Pr = 1

0 < Pr ≤ 1/5


D 
1/5 < Pr < 1

Number of triplets in L^{3} = Number of ways in which we can choose 3 elements from 5 with repetition = 5 * 5 * 5 = 125. Now, when we take x = t, then the given condition for L is satisfied for any y and z. Here, y and z can be taken in 5 * 5 = 25 ways. Take x = r, y = p, z = p. Here also, the given condition is satisfied. So, pr > 25 / 125 > 1/5. For x = q, y = r, z = s, the given condition is not satisfied as q ⋁ (r ⋀ s) = q ⋁ p = q, while (q ⋁ r) ⋀ (q ⋁ s) = t ⋀ t = t. So, pr ≠ 1. ANSWER IS D
Question 45

#include <stdio.h> int main() { unsigned int x[4][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 11, 12}}; printf ( "%u, %u, %u" , x+3, *(x+3), *(x+2)+3); } 
A 
2036, 2036, 2036

2012, 4, 2204


C 
2036, 10, 10

2012, 4, 6

x = 2000 Explanation: Since x is considered as a pointer to an array of 3 integers and an integer takes 4 bytes, value of x + 3 = 2000 + 3*3*4 = 2036 The expression, *(x + 3) also prints same address as x is 2D array. The expression *(x + 2) + 3 = 2000 + 2*3*4 + 3*4 = 2036
Question 46

A =  1 4   b a 
a = 6, b = 4


B 
a = 4, b = 6

a = 3, b = 5


D 
a = 5, b = 3

The character equation for given matrix is  1λ 4  = 0  b aλ (1λ)*(aλ)  4b = 0 Putting λ = 1, => (1  (1)) * (a  (1))  4b = 0 => 2a + 2  4b = 0 => 2b  a = 1 Putting λ = 7, => (1  7) * (a  7)  4b = 0 => 6a + 42  4b = 0 => 2b + 3a = 21 Solving the above two equations, we get a = 5, b = 3
Question 47

A 
0110110…

0100100…


011101110…


D 
011001100…

 Toggle: J = K = 1
 Hold : J = K = 0
We see from table Q output of DFF is going to next state input of JKFF and the bits sequence produced is like 110110….. Including initial condition (0) we get output as 0110110110…. Hence answer is (A) part. Another Explanation: Here, it is given that JK flip flop will toggle when J = K = 1 and it will retain the output if J = K = 0. Also, the output of the D flip flop would remain the same as the input. So, we have Initial output : D = 1JK = 0
After clock 1 : D = 0 (D gets 0 as input from initial output of JK, so output = 0)
JK = 1 (J = K = 1 from initial output of D, so output would be toggled from 0 to 1)
After clock 2 : D = 1 (D gets 1 as input from previous output of JK, so output = 1)
JK = 1 (J = K = 0 from previous output of D, so output would be retained to 1)
After clock 3 : D = 1 (D gets 1 as input from previous output of JK, so output = 1)
JK = 0 (J = K = 1 from previous output of D, so output would be toggled from 1 to 0)
After clock 4 : D = 0 (D gets 0 as input from previous output of JK, so output = 0)
JK = 1 (J = K = 1 from previous output of D, so output would be toggled from 0 to 1)
After clock 5 : D = 1 (D gets 1 as input from previous output of JK, so output = 1)
JK = 1 (J = K = 0 from previous output of D, so output would be retained to 1)
Thus, the bit sequence generated at the Q output of the JK flip flop will be 0110110…
Question 48

A 
3.2

3.0


2.2


2.0

Speedup = ExecutionTime_{Old} / ExecutionTime_{New} ExecutionTime_{Old} = CPI_{Old} * CycleTime_{Old} [Here CPI is Cycles Per Instruction] = CPI_{Old} * CycleTime_{Old} = 4 * 1/2.5 Nanoseconds = 1.6 ns Since there are no stalls, CPU_{new} can be assumed 1 on average. ExecutionTime_{New} = CPI_{new} * CycleTime_{new} = 1 * 1/2 = 0.5 Speedup = 1.6 / 0.5 = 3.2
Question 49

Both {f} and {g} are functionally complete


B 
Only {f} is functionally complete

C 
Only {g} is functionally complete

Neither {f} nor {g} is functionally complete

 For every 1value of f, the number of 1’s in the corresponding input is odd, and for every 0value of f, the number of 1’s in the corresponding input is even.
or
 For every 1value of f, the number of 1’s in the corresponding input is even, and for every 0value of f, the number of 1’s in the corresponding input is odd.
If one of these statements holds for f, we say that f is linear1. We denote the class of linear boolean functions with L and write f ∈ L. Property 4: We say that boolean function f is monotone if for every input, switching any input variable from 0 to 1 can only result in the function’s switching its value from 0 to 1, and never from 1 to 0. We denote the class of monotone boolean functions with M and write f ∈ M. Property 5: We say that boolean function f(x1,…,xn) is selfdual if f(x1,…,xn) = ¬f(¬x1,…,¬xn). The function on the right in the equality above (the one with negations) is called the dual of f. We will call the class of selfdual boolean functions S and write f ∈ S. As in our case we can see on giving all i/p to 0 (g )produce 0 so it preserving 0 and can’t be functionally complete. But f is neither preserving 0 nor 1.
 F is not linear(see defn. of linear above)
 F is not monotone(see defn. of monotone above)
 F is not self dual as f(x,y,z) is not equal to –f(x,y,z)
So f is functionally complete. Hence ans is (B) part
Question 50

A 
Unsorted array

B 
Minheap

Sorted array


Sorted doubly linked list

Question 51

A 
2

3


C 
4

5

Entity E1. a1 a12  a11 is key Entity E2 a21 a22  a22 is key Entity E3 a31 a32  a31 is key R12 is m:n Relationship between E1 and E2 R12 a11 a22  (a11, a22) is key. R13 is 1:n Relationship between E1 and E3 R13 a11 a31  (a11, a31) is key. We need minimum no. of tables. Can we remove any of the above tables without loosing information and keeping the relations in 3NF? We can combine R13 and R12 into one. a11 a31 a22  (a11, a31, a22) is key. The relation is still in 3NF as for every functional dependency X > A, one of the following holds 1) X is a superkey or 2) AX is prime attribute
Question 52

while (first <= last) { if (array [middle] < search) first = middle +1; else if (array [middle] == search) found = True; else last = middle – 1; middle = (first + last)/2; } if (first < last) not Present = True; 
The cyclomatic complexity of the program segment is __________.
3


4


C 
5

D 
6

M = E − N + 2P, where E = the number of edges of the graph. N = the number of nodes of the graph. P = the number of connected components.
Source: http://en.wikipedia.org/wiki/Cyclomatic_complexity For a single program (or subroutine or method), P is always equal to 1. So a simpler formula for a single subroutine is
M = E − N + 2
For the given program, the control flow graph is:
E = 13, N = 10. Therefore, E  N + 2 = 5.
Question 53

66


B 
69

C 
68

70

Question 54

0


B 
1

1


infinite

Question 55

1


B 
0

1


D 
2

Question 56

A 
Both incur the same number of page faults

FIFO incurs 2 more page faults than LRU


LRU incurs 2 more page faults than FIFO


D 
FIFO incurs 1 more page faults than LRU

3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3 In both FIFO and LRU, we get following after considering 3, 8, 2, 3, 9, 1, 3 8 2 9 1 FIFO 6 replaces 3 8 2 9 1 6 3 replaces 8 2 9 1 6 3 8 replaces 2 9 1 6 3 8 2 replaces 9 1 6 3 8 2 No more page faults LRU 6 replaces 8 3 2 9 1 6 8 replaces 2 3 9 1 6 8 2 replaces 1 3 9 6 8 2 1 replaces 8 3 9 6 2 1
Question 57

A 
14020

14000


25030


D 
15000

Seek time (given) = 4ms RPM = 10000 rotation in 1 min [60 sec] So, 1 rotation will be =60/10000 =6ms [rotation speed] Rotation latency= 1/2 * 6ms=3ms # To access a file, total time includes =seek time + rot. latency +transfer time TO calc. transfer time, find transfer rate Transfer rate = bytes on track /rotation speed so, transfer rate = 600*512/6ms =51200 B/ms transfer time= total bytes to be transferred/ transfer rate so, Transfer time =2000*512/51200 = 20ms Given as each sector requires seek tim + rot. latency = 4ms+3ms =7ms Total 2000 sector takes = 2000*7 ms =14000 ms To read entire file ,total time = 14000 + 20(transfer time) = 14020 ms
Question 58
WRONG

A 
a_{n–2} + a_{n–1} + 2^{n–2}

a_{n–2} + 2a_{n–1} + 2^{n–2}


C 
2a_{n–2} + a_{n–1} + 2^{n–2}

2a_{n–2} + 2a_{n–1} + 2^{n–2}

a_{0} = 0 a_{1} = 0 a_{2} = 1 ["11"] a_{3} = 3 ["011", "110", "111"] a_{4} = 8 ["0011", "0110", "0111", "1101", "1011", "1100", "1110", "1111"]
If we check for a_{3}, we can see that only A and C satisfy the value. Among (A) and (C), only (A) satisfies for a_{4}. Another Solution (With Proof)
A string of length n (n >= 2) can be formed by following 4 prefixes 1) 11 followed by a string of length n2 2) 00 followed by a string of length n2 3) 01 followed by a string of length n2 4) 10 followed by a string of length n2 Number 1 has already two consecutive 1's so number of binary strings beginning with number 3 is 2^{n2} as remaining n2 bits can have any value. Number 2 has two 0's so remaining n2 bits must have two consecutive 1's. Therefore number of binary strings that can be formed by number 2 is a_{n2}. Number 3 and Number 4 together form all strings of length n1 and two consecutive 1's.
Question 59

1. There exists a statement Sj that uses x 2. There is a path from Si to Sj in the flow graph corresponding to the program 3. The path has no intervening assignment to x including at Si and Sj
The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are
A 
p, s, u

r, s, u


C 
r, u

q, v

Question 60

10110


B 
10010

01010


D 
01001

Question 61
WRONG

0


B 
1

2


D 
3

Question 62

160


B 
320

640


D 
220

Transmission or Link speed = 64 kb per sec Propagation Delay = 20 milisec Since stop and wait is used, a packet is sent only when previous one is acknowledged. Let x be size of packet, transmission time = x / 64 milisec Since utilization is at least 50%, minimum possible total time for one packet is twice of transmission delay, which means x/64 * 2 = x/32 x/32 > x/64 + 2*20 x/64 > 40 x > 2560 bits = 320 bytes
Question 63

A 
24

20


32


64

v − e + f = 2. v > Number of vertices e > Number of edges f > Number of faces As per the question v = 10 And number of edges on each face is three Therefore, 2e = 3f [Note that every edge is shared by 2 faces] Putting above values in v − e + f = 2 10  e + 2e/3 = 2 e = 3*10  6 = 24
Question 64

4


B 
8

C 
7

9

The correct answer is 8. This question was asked as a fill in the blank type question in the exam.
Three address code is an intermediate code generated by compilers while optimizing the code. Each three address code instruction can have atmost three operands (constants and variables) combined with an assignment and a binary operator. The point to be noted in three address code is that the variables used on the left hand side (LHS) of the assignment cannot be repeated again in the LHS side. Static single assignment (SSA) is nothing but a refinement of the three address code.
So, in this question, we have
t1 = r / 3; t2 = t * 5; t3 = u * v; t4 = t3 / w; t5 = q + t1; t6 = t5 + s; t7 = t6  t2; t8 = t7 + t4;
Therefore, we require 8 temporary variables (t1 to t8) to create the three address code in static single assignment form.
Question 65

5


10


C 
12

D 
15

Periods of T1, T2 and T3 are 3ms, 7ms and 20ms Since priority is inverse of period, T1 is the highest priority task, then T2 and finally T3 Every instance of T1 requires 1ms, that of T2 requires 2ms and that of T3 requires 4ms Initially all T1, T2 and T3 are ready to get processor, T1 is preferred Second instances of T1, T2, and T3 shall arrive at 3, 7, and 20 respectively. Third instance of T1, T2 and T3 shall arrive at 6, 14, and 49 respectively. TimeInterval Tasks 01 T1 12 T2 23 T2 34 T1 [Second Instance of T1 arrives] 45 T3 56 T3 67 T1 [Third Instance of T1 arrives] [Therefore T3 is preempted] 78 T2 [Second instance of T2 arrives] 89 T2 910 T1 [Fourth Instance of T1 arrives] 1011 T3 1112 T3 [First Instance of T3 completed]
A  T(n) = 2T (n/2) + cn 
B  T(n) = T(n – 1) + T(0) + cn 
C  T(n) = 2T (n – 2) + cn 
D  T(n) = T(n/2) + cn 