41. Which of the following
is/are undecidable?
1. G is a CFG. Is L(G)=Φ?
2. G is a CFG. IS L(G)=∑* ?
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)
?
(A) 3 only (B)
3 and 4 only
(C) 1, 2 and 3 only (D)
2 and 3 only
Answer: D
42. 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;
}
(A) 3024 (B)
6561
(C) 55440
(D) 161051
Answer: Marks to All
43. 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?
(A) 10,20,15,23,25,35,42,39,30
(B) 15,10,25,23,20,42,35,39,30
(C) 15,20,10,23,25,42,35,39,30
(D) 15,10,23,25,20,35,42,39,30
Answer: D
44. 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>0) {
Dequeue(Q)
m=m-1
}
}
What is the worst case time complexity of a sequence of n
queue operations on an initially empty queue?
(A) Θ(n) (B) Θ(n+k)
(C) Θ(nk) (D)
Θ(n2)
Answer: A
45. 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 I1, I2, I3,....I12
is executed in this pipelined processor. Instruction I4 is the only
branch instruction and its branch target is I9. If the branch is
taken during the execution of this program, the time (in ns)needed to complete
the program is
(A) 132 (B) 165
(C) 176 (D) 328
Answer: B
46. A RAM chip has a capacity
of 1024 words of 8 bits each (1K×8). The number of 2×4 decoders with enable
line needed to construct a 16K×16 RAM from 1K×8 RAM is
(A) 4 (B) 5
(C) 6 (D) 7
Answer: B
47. Which one of the following
is NOT logically equivalent to ¬∃x("y(a)˄"z(b))?
(A) "x(∃z(¬b)→"y(a))
(B) "x("z(b)→∃y(¬a))
(C) "x("y(a)→∃z(¬b))
(D) "x(∃y(¬a)→∃z(¬b))
Answer: Marks to All
Common Data Questions
Common
Data for Questions 48 and 49:
The
following code segment is executed on a processor which allows only register
operands in its instructions. Each instruction can have almost two source
operands and one destination operand. Assume that all variables are dead after
this code segment.
c=a+b;
d=c*a;
e=c+a;
x=c*c;
if(x>a) {
y=a*a;
}
else {
d=d*d;
e=e*e;
}
48. Suppose the instruction set
architecture of the processor has only two registers. The only allowed compiler
optimization is code motion, which moves statements from one place to another
while preserving correctness. What is the minimum number of spills to memory in
the compiled code?
(A) 0 (B) 1
(C) 2 (D) 3
Answer: B
49. What is the minimum number
of registers needed in the instruction set architecture of the processor to
compile this code segment without any spill to memory? Do not apply any
optimization other than optimizing register allocation
(A) 3 (B) 4
(C) 5 (D) 6
Answer: B
0 Comments