1. Let L be a set with a relation R which is transitive, anti-symmetric and reflexive and for any two elements a, b Î L let the least upper bound lub (a, b) and the greatest lower bound glb (a, b) exist. Which of the following is/are true?

• L is a poset
• L is a boolean algebra
• L is a lattice
• None of the above

2.If L1 is context free language and L2 is a regular language which of the following is/are false?

• L1 - L2 is not context free
• L1 Ç L2 is context free
• ~ L1 is context free
• ~ L2 is regular

3. Given the programming constructs (i) assignment (ii) for loops where the loop parameter cannot be changed within the loop (iii) If-then-else (iv) forward go to (v) arbitrary go to (vi) non-recursive proce dure call (vii) recursive procedure/function call (viii) repeat loop, which constructs will you not include in a programming language such that it should be possible to program the terminates (i.e. halting) function in the same programming language.

• (ii), (iii), (iv)
• (v), (vii), (viii)
• (vi), (vii), (viii)
• (iii), (vii), (viii)

4.For the schedule given below, which of the following is correct:

1 Read A

2 Read B

3 Write A

4 Read A

5 Write A

6 Write B

7 Read B

8 Write B

(a) This schedule is serialisable and can occur in a scheme using 2PL protocol.

(b) This schedule is serialisable but cannot occur in a scheme using 2PL protocol.

(c) This schedule is not serialisable but can occur in a scheme using 2PL protocol.

(d) This schedule is not serialisable and cannot occur in a scheme using 2PL protocol.

5. Consider the schema R = (S T U V) and the dependencies S ® T, T ® U. U ® V and V ® S. Let R = (R1 and R2) be a decomposition such that R1 Ç R2 = Æ . The decomposition is

• not in 2NF
• in 2NF but not 3NF
• in 3NF but not in 2NF
• in both 2NF and 3NF

• Consider the circuit shown below. In a certain steady state, the line Y is at '1 '. What are the possible values of A, B, and C in this state?

• A = 0, B = 0, C = I
• A = 0, B = 1, C = 1
• A = 1, B = 0, C = 1
• A = 1, B = 1, C = 1

6. Which of the following sets of component (s) is/are sufficient to implement any arbitrary boolean func­ tion?

• XOR gates, NOT gates
• 2 to I multiplexors
• AND gates, XOR gates
• Three-input gates that output (A. B) + C for the inputs A B. and C.

7. A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

• Address translation
• DMA for disk transfer
• At least two modes of CPU execution (privileged and non-privileged)
• Demand paging.

8. Which of the following is/are advantages of virtual memory?

(a) Faster access to memory on an average.

(b) Processes can be given protected address spaces.

(c) Linker can assign addresses independent of where the program will be loaded in physical memory.

(d) Programs larger than the physical memory size can be run.

9. Which of the following actions is/are typically not performed by the operating system when switching context from process A to process B?

(a) Saving current register values and restoring saved register values for process B.

(b) Changing address translation tables.

(c) Swapping out the memory image of process A to the disk

(d) Invalidating the translation look-aside buffer.

10.Consider the following program in a language that has dynamic scoping

var x: real;

procedure show:

begin print (x) ; end;

procedure small :

var x: real;

begin x : = 0.125; show; end:

begin x : = 0.25;

show; small

end.

Then the output of the program is :

• 0.125 0.125
• 0.25 0.25
• 0.25 0.125
• 0.125 0.25

11.The number of tokens in the Fortran statement DO 10I= 1.25 is

• 3
• 4
• 5
• None of the above

12. A grammar that is both left and right recursive for a non-terminal, is

• Ambiguous
• Unambiguous
• Information is not sufficient to decide whether it is ambiguous or unambiguous
• None of the above

13. The number of full and half-adders required to add 16-bit numbers is

• 8 half-adders, 8 full-adders
• 1 half-adder, 15 full-adders
• 16 half-adders, 0 full-adders
• 4 half-adders, 12 full-adders

14. Zero has two representations in

• Sign magnitude
• 1's complement
• 2's complement
• none of the above

15.Raid configurations of disks are used to provide

• Fault-tolerance
• High speed
• High data density
• None of the above

16. Arrange the following configurations for. CPU in decreasing order of operating speeds: Hard wired control, vertical microprogramming, horizontal microprogramming.

• Hard wired control, vertical micro-programming, horizontal micro-programming
• Hard wired control, horizontal micro-programming, vertical micro-programming
• Horizontal micro-programming, vertical micro-programming, hard wired control.
• Vertical micro-programming, horizontal micro-programming, hard wired control.

17. The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 15 records), D (with 5 records) and E (with 25 records) is:

• 165
• 90
• 75
• 65

18. If T 1 = 0 (1), give the correct matching for the following pairs:

(M) T n = T n-1 + n (U) T n = 0 (n)

(N) T n = T n/2 + n (V) T n = 0 (nlog n)

(0) T n =T n/2+n1ogn (W) T n=0(n 2)

(P) T n = T n-1 + log n (X) T n = 0 (log 2 n)

• M-W, N-V, O-U, P-X
• M-W, N-U, O-X, P-V
• M-V, N-W, O-X, P-U
• M-W, N-U, O-V, P-X

19. The main difference(s) between a ClSC and a RISC processor is/are that a RISC processor typically

• has fewer instructions
• has fewer addressing ,modes
• has more registers
• is easier to implement using hard-wired control logic

20. A certain processor supports only the immediate and the direct addressing modes. Which of the follow­ing programming language features cannot be implemented on this processor?

• Pointers
• Arrays
• Records
• Recursive procedures with local variable

21.Consider the following C function definition

int Trial (int a, int b, int c)

{

if ((a> = b)&& (c < b) return b;

else if (a> = b) return Trial (a, c, b);

else return Trial (b, a, c) ;

}

22.The function Trial :

• finds the maximum of a, b and c
• finds the minimum of a, b and c
• finds the middle number of a, b, c
• none of the above

23. Which of the following is/are correct ?

• An SQL query automatically eliminates duplicates
• An SQL query will not work if there are no indexes on the relations
• SQL permits attribute names to be repeated in the same relation
• None of the above