Questions and answers for exam Preparation

MCQs

Total Questions : 65 | Page 4 of 7 pages

The following figure represents access graphs of two modules M1 and M2. The filled circles
represent methods and the unfilled circles represent attributes. IF method m is moved to
module M2 keeping the attributes where they are, what can we say about the average
cohesion and coupling between modules in the system of two modules?

There is no change
Average cohesion goes up but coupling is reduced
Average cohesion goes down and coupling also reduces
Average cohesion and coupling increase

Discuss Question

Answer: Option A. -> There is no change

Coupling = `( number of external links) / (number of modules )` =`2/2`

Cohesion of a module = `(number of internal links) / ( number of methods)`

Cohesion of `M_1` = `8/4`; Cohesion of `M_2` = `6/3`; Average cohesion=2

After moving method m to M2, graph will become

Coupling = `2/2`

Cohesion of `M_1` = `6/3` Cohesion of `M_2` = `8/4` Average cohesion=2

`:.` answer is no change

Question 32.

What is the return value of f p,p ( ) if the value of p is initialized to 5 before the call? Note
that the first parameter is passed by reference, whereas the second parameter is passed by
value

int f int & x, int c {

c = c - 1;

if (c = 0) return 1;

x = x + 1;

return f (x , c)*x;

}

3024
6561
55440
161051

Discuss Question

Answer: Option B. -> 6561

Question 33.

Consider the following two sets of LR(1) items of an LR(1) grammar

X `rightarrow` c.X, c / d X `rightarrow` c.X, $

X `rightarrow` .cX, c / d X `rightarrow` .cX, $

X `rightarrow` .d, c / d X `rightarrow` .d, $

Which of the following statements related to merging of the two sets in the corresponding
LALR parser is/are `FALSE`?

1. Cannot be merged since look aheads are different

2. Can be merged but will result in S - R conflict

3. Can be merged but will result in R - R conflict

4. Cannot be merged since goto on c will lead to two different sets

1 only
2 only
1 and 4 only
1, 2, 3 and 4

Discuss Question

Answer: Option D. -> 1, 2, 3 and 4

X `rightarrow` c.X, c / d X `rightarrow` c.X, $

X `rightarrow` .cX, c / d X `rightarrow` .cX, $

X `rightarrow` .d, c / d X `rightarrow` .d, $

X `rightarrow` c.X, c / d / $

X `rightarrow` .cX, c / d / $

X `rightarrow` .d, c / d / $

1. Merging of two states depends on core part (production rule with dot operator), not on

look aheads.

2. The two states are not containing Reduce item ,So after merging, the merged state can

not
contain any S - R conflict

3. As there is no Reduce item in any of the state, so canâ€™t have R-R conflict.

4. Merging of stats does not depend on further goto on any terminal.
So all statement

are false.

Question 34.

Which of the following is/are undecidable?

1. G is a CFG. Is L (G) = `Phi`?

2. G is a CFG. IS L (G) = `Sigma`*?

3. M is a Turning machine. Is L(M) regular?

4. A is a DFA and N is a NFA. Is L (A) = L(N)?

3 only
3 and 4 only
1, 2 and 3 only
2 and 3 only

Discuss Question

Answer: Option D. -> 2 and 3 only

There is an algorithm to check whether the given CFG is empty, finite or infinite and also to
convert

NFA to DFA hence 1 and 4 are decidable

Question 35.

A certain computation generates two arrays a and b such that a [i] = f (i) for 0 `le` i < n and

b [i] = g (a[i]) for 0 `le` i < n . Suppose this computation is decomposed into two concurrent

processes X and Y such that X computes the array a and Y computes the array b. The
processes

employ two binary semaphores R and S, both initialized to zero. The array a is
shared by the

two processes. The structures of the processes are shown below.

Pr ocess X; Pr ocess Y;

private i; private i;

for (i = 0; i < n; i + + for (i = 0; i < n; i + + {

a[i] = f (i); Entry Y (R, S);

Exit X (R,S); b[i] = g (a[i]);

Which one of the following represents the `CORRECT` implementations of ExitX and
EntryY?

Exit X (R, S) {P(R); V(S); } Entry Y (R, S) { P(S); V(R); }
Exit X (R, S) {V(R); V(S); } Entry Y (R, S) { P(R); P(S); }
Exit X (R, S) {P(S); V(R); } Entry Y (R, S) { V(S); P(R); }
Exit X (R, S) {V(R); P(S); } Entry Y (R, S) { V(S); P(R); }

Discuss Question

Answer: Option C. -> Exit X (R, S) {P(S); V(R); } Entry Y (R, S) { V(S); P(R); }

For computing both the array a[ ] and b[ ], first element a[i] should be computed using

which
b[i] can be computed. So process X and Y should run in strict alteration manner,

starting with
X. This requirement meets with implementation of ExitX and EntryY given

in option C.

Question 36.

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42.

Which one of the following is the postorder traversal sequence of the same tree?

10,20,15,23,25,35,42,39,30
15,10,25,23,20,42,35,39,30
15,20,10,23,25,42,35,39,30
15,10,23,25,20,35,42,39,30

Discuss Question

Answer: Option D. -> 15,10,23,25,20,35,42,39,30

Preorder :30,20,10,15,25,23,39,35,42

Inorder :10,15,20,23,25,30,35,39,42

BST:

20 39

10 25 35 42

15 23

Question 37.

Consider the following operation along with Enqueue and Dequeue operations on queues,
where

k is a global parameter

MultiDequeue Q {

m = k

while (Q is not empty) and (m>o) {

Dequeue (Q)

m = m - 1

}

What is the worst case time complexity of a sequence of n queue operations on an initially

empty queue?

`Theta`(n)
`Theta`(n + k)
`Theta`(nk)
`Theta`(`n^2`)

Discuss Question

Answer: Option A. -> `Theta`(n)

Initially the queue is empty and we have to perform n operations.

i) One option is to perform all Enqueue operations i.e. n Enqueue operations. Complexity

will be `theta` (n)

ii) We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first

n/2 times and then Dequeue for next n/2, or Enqueue and Dequeue alternately, or any

permutation of Enqueues and Dequeues totaling 'n'times. Complexity will be`theta`(n)

iii) We can perform Enqueues and MultiDequeues. A general pattern could be as follows:

Enqueue Enqueue ---- (ktimes) MultiDequeue Enqueue Enqueue ---- (ktimes) MultiDequeue

---- Up to total n

---- k items enqueued -----k items deleted----k items enqueued----k items deleted -- and

so on

The number of times this k-Enqueues, MutiDequeue cycle is performed = n/k + 1

So, Complexity will be k times Enqueue + 1 MultiDequeue) x n/k + 1

Which is `theta`(2k x n/k + 1) = `theta` (n)

iv) We can just perform n MultiDequeues (or n Dequeues for that matter):

Each time the while condition is false (empty queue), condition is checked just once for
each of the 'n' operations. So `theta`(n).

Question 38.

A RAM chip has a capacity of 1024 words of 8 bits each (1K x 8) . The number of 2 x 4

decoders with enable line needed to construct a 16K x 16 RAM from 1K x 8 RAM is

Discuss Question

Answer: Option B. -> 5

RAM chip size = 1k x 8 [1024 words of 8 bits each ]

RAM to construct = 16k x 16

Number of chips required = `(16k xx 16)/(1k xx 8)` = 16 x 2 [16 chips vertically with each having 2 chips horizontally]

So to select one chip out of 16 vertical chips, we need 4 x 16 decoder.

Available decoder is - 2 x 4 decoder

To be constructed is 4 x 16 decoder

EN Q3 D15

Q2 D14

S1 S1 Q1 D13

S0 S0 Q0 D12

EN Q3 D11

1 EN Q3 Q2 D10

Q2 S1 S1 Q1 D9

S3 S1 Q1 S0 S0 Q0 D8

S2 S0 Q0

EN Q3 D7

Q2 D6

S1 S1 Q1 D5

S0 S0 Q0 D4

EN Q3 D3

Q2 D2

S1 S1 Q1 D1

S0 S0 Q0 D0

So we need 5, 2 x 4 decoder in total to construct 4 x 16 decoder.

Question 39.

Consider an instruction pipeline with five stages without any branch prediction: Fetch

Instruction (FI), Decode Instruction (DI), Fetch Operand (FO), Execute Instruction

(EI) and
Write Operand (WO). The stage delays for FI, DI, FO, EI and WO are 5 ns,

7 ns, 10 ns, 8 ns
and 6 ns, respectively. There are intermediate storage buffers after

each stage and the delay of
each buffer is 1 ns. A program consisting of 12 instructions

`I_1`, `I_2`, `I_3`,......`I_12` is executed in this
pipelined processor. Instruction `I_4` is the only

branch instruction and its branch target is `I_9`. If
the branch is taken during the execution

of this program, the time (in ns) needed to complete
the program is

Discuss Question

Answer: Option B. -> 165

Clock period=Maximum stage delay + overhead (Buffer) =10 + 1 = 11 ns

Assume FI - 1, DI - 2, FO - 3, EI - 4, WO - 5

`I_1` : 1 2 3 4 5

`I_2` : - 1 2 3 4 5

`I_3` : - - 1 2 3 4 5

`I_4` : - - - 1 2 3 4 5

`I_5` : - - - - 1 2 3 4 5

`I_6` : - - - - - 1 2 3 4 5

`I_7` : - - - - - - 1 2 3 4 5

`I_8` : - - - - - - - 1 2 3 4 5

`I_9` : - - - - - - - - 1 2 3 4 5

`I_10` : - - - - - - - - - 1 2 3 4 5

`I_11` : - - - - - - - - - - 1 2 3 4 5

`I_12` : - - - - - - - - - - - 1 2 3 4 5

So number of clocks required to complete the program is = 15 clocks and time taken is = 15
Ã—11 ns=165 ns.

Question 40.

Which one of the following is `NOT` logically equivalent to `not` `exists` x(`forall` y(`alpha`) `or` `forall` z(`beta`))?

`forall` x (`exists` z ( `not` `beta` )`rightarrow` `forall` y (`alpha`))
`forall` x (`forall` z ( `beta` )`rightarrow` `exists` y (`not` `alpha`))
`forall` x (`forall` y ( `alpha` )`rightarrow` `exists` z (`not` `beta`))
`forall` x (`exists` y ( `not` `alpha` )`rightarrow` `exists`z (`not` `beta`))

Discuss Question

Answer: Option A. -> `forall` x (`exists` z ( `not` `beta` )`rightarrow` `forall` y (`alpha`))

Answer: (A) and (D)

`not` `exists` x (`forall` y(`alpha`) `and` `forall` z(`beta`))

`equiv` `forall` x [`forall` y (`alpha`) `rightarrow` `exists` z(`not` `beta` )]option "c" [`because` `not` (p `and` q) `equiv` p `Rightarrow` `not` q]

`equiv` `forall` x [`forall` z(`beta`)`rightarrow` `exists` y (`not` `alpha`)]option "B" [`because` p `Rightarrow` q `equiv` `not` q `Rightarrow` `not` p]