# GATE Computer Science and Information Technology Solved Paper 2013 - Part 5

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
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
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
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)
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

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
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))

#### 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