1. The running time of an algorithm 𝑇(𝑛 ) where 𝑛 the input size is given by: 

= 𝑝 , if 𝑛 = 1
where, 𝑝 and 𝑞 are constants.

What is the complexity (order) of the algorithm?

Answer: (c)

2. Consider the following statements regarding automata theory:
1. The pumping length must always be equal to the number of states in a machine
2. A non-regular expression can have a finite pumping length
3. In a regular language/expression, a string of pumping length can be repeated arbitrarily
3. The language 
has a pumping length

Which of the above statements is/are correct?
(a) 1, 2 and 4
(b) 1, 3 and 4
(c) 2 only
(d) 3 only

Answer: (d)

4. Consider the following machines regarding Finite automatas:
1. DFA
2. NFA
3. E - NFA
4. Any automaton

Which of the above are correct about the applicability of Arden’s Theorem?
(a) 1 and 4
(b) 1 and 2
(c) 2 and 3
(d) 3 and 4

Answer: (b)

5. In C programming, the qualifiers ‘signed’ and ‘unsigned’ apply to
1. Char
2. Float
3. Int
4. Double

(a) 1 and 4
(b) 2 and 3
(c) 1 and 3
(d) 2 and 4

Answer: (c)

6. When a compiler encounters a function parameter for a single-subscripted array of the form int a [ ], it converts the parameter to:
(a) Int a
(b) Int & a
(c) Int * a
(d) No conversion is required

Answer: (c)

7. The dominator node in DAG represents
(a) Any node of DAG which represents start of loop
(b) Last node of DAG
(c) Node with highest degree of DAG
(d) Isolated node of DAG

Answer: (a)

8. Which of the following is used for grouping of characters into tokens?
(a) Parser
(b) Code optimization
(c) Code generator
(d) Lexical analyzer

Answer: (d)

9. Consider the following contents of different registers:

Offset (displacement) = 5000 H
[AX]−1000 𝐻 , [BX]−2000𝐻 , [SI]−4000𝐻 , [DI]−3000𝐻
[BP]−5000 𝐻 , [SP]−6000𝐻 , [CS]−0000𝐻 , [DS]−2000𝐻
[SS]−3000 𝐻 , [IP]−7000𝐻 ,

What is the effective address of the data for the following instruction?

MOV  AX,  [BX ] [SI]

(a) 20000𝐻
(b) 25000𝐻
(c) 26000𝐻
(d) 30000𝐻

Answer: (c)

10. A computer company wants to hire 25 programmers to handle systems programming jobs and 40 programmers for applications programming. Of those hired, 10 will be expected to perform jobs of both types, the number of programmers hired must be:

(a) 40
(b) 45
(c) 50
(d) 55

Answer: (d)