1. For a pipelined CPU with a single ALU, consider the following situations

• The j + 1-st instruction uses the result of the j-th instruction as an operand
• The execution of a conditional jump instruction
• The j-th and j + 1-st instructions require the ALU at the same time

Which of the above can cause a hazard?

• I and II only
• II and III only
• III only
• All the three

 

2. Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

• Q (1)
• Q (log n)
• Q (n)
• Q (n 2)

 

3. Ram and Shyam have been asked to show that a certain problem Õis NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Õ, and Shyam shows a polynomial time reduction from Õ to 3-SAT. Which of the following can be inferred from these reductions?

• Õ is NP-hard but not NP-complete
• Õ is in NP, but is not NP-complete
• Õ is NP-complete
• Õ is neither NP-hard, nor in NP

 

4. Nobody knows yet if P = NP. Consider the language L defined as follows:

 

Which of the following statements is true?

• L is recursive
• L is recursively enumerable but not recursive
• L is not recursively enumerable
• Whether L is recursive or not will be known after we find out if P = NP

 

5. The regular expression 0* (10*)* denotes the same set as

• (1*0)*1*
• 0 + (0 + 10)*
• (0 + 1)* 10(0 + 1)*
• none of the above

6. If the strings of a language L .can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?

(a) L is necessarily finite

(b) L is regular but not necessarily finite

(c) L is context free but not necessarily regular

(d) L is recursive but not necessarily context free

 

7. Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar ?

(a) Removing left recursion alone

(b) Factoring the grammar alone

(c) Removing left recursion and factoring the grammar

(d) None of the above

 

8. Assume that the SLR parser for a grammar G has n 1 states and the LALR parser for G has n 2 states. The relationship between n l and n 2 is

(a) n 1 is necessarily less than n2

(b) n 1 is necessarily equal to n2

(c) n 1 is necessarily greater than n2

(d) none of the above

 

9. In a bottom-up evaluation of a syntax directed definition, inherited attributes can

(a) always be evaluated

(b) be evaluated only if the definition is L-attributed

(c) be evaluated only if the definition has synthesized attributes

(d) never be evaluated

 

10. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

• 7 5 1 0 3 2 4 6 8 9
• 0 2 4 3 1 6 5 9 8 7
• 0 1 2 3 4 5 6 7 8 9
• 9 8 6 4 2 3 0 1 5 7