1.How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices?

• n(n-l)/2
• 2 n
• n!
• 2 n(n-1)/2

2. What is the minimum number of stacks of size n required to implement a queue of size n ?

(0) One (b) Two

(c) Three (d) Four

3.What is printed by the print statements in the program P1 assuming call by reference parameter passing?

Program Pl ( )

{

x=10;

y=3;

func1(y, x, x);

print x;

print y;

,

func1 (x, y, z)

{

y=y+4;

z=x+y+z;

}

• 10,3
• 31,3
• 27,7
• None of the above

 

4.Consider the following three C functions :

[PI] int * g (void)

{

int x= 10;

return (& x);

}

[P2] int * g (void)

{

int * px;

*px= 10;

return px;

}

[P3] int * g (void)

{

int * px;

px = (int *) malloc (sizeof(int));

*px= 10;.

return px;

}

5.Which of the above three functions are likely to cause problems with pointers?

(a) OnlyP3 (b) Only P1 and P3

(c) Only P1 and P2 (d) P1,P2,andP3

 

6. Consider the following program

Program P2

Var n: int:

procedure W (var x: int)

begin

x=x+1;

print x;

 

end

procedure D

begin

 

var n: int;

n=3;

W(n); .

 

end

begin \\beginP2

n=10;

D;

end

7.If the language has dynamic scoping and parameters are passed by reference, what will be printed by the program?

• 10
• 11
• 3
• None of the above

 

8. Which of the following does not interrupt a running process? .

(a) A device (b) Timer

(c) Scheduler process (d) Power failure

 

9. Consider a machine with 64 M B physical memory and a 32-bit virtual address space. If the page size is 4KB, what is the approximate size of the page table?

(a) 16 MB (b) 8 MB

(c) 2 MB (d) 24 MB

 

10. Consider Peterson's algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process is shown below.

repeat

 

flag = true;

turn = j;

while ( P ) do no-op;

Enter critical section, perform actions, then exit critical section

flag [ i ] = false;

Perform other non-critical section actions.

until false;

 

11.For the program to guarantee mutual exclusion, the predicate P in the while loop should be

• flag [j] = true and turn = i
• flag [j] = true and turn = j
• flag = true and turn = j
• flag = true and turn = i

 

12. R (A, B, C, D) is a relation. Which of the following does not have a loss less join, dependency preserving BCNF decomposition?

• A ® B,B ® CD
• A ® B,B ® C, C ® D
• AB ® C,C ® AD
• A ® BCD

13. Which of the following relational calculus expressions is not safe?

• {t | $ u Î R 1 (t [A] = u [A] ) Ù Ø $ s Î R 2 (t [A] = s [A]) }
• {t | " u Î R 1(u [A] = "x" Þ $ s Î R 2 (t [A] = s [A] Ù s [A] = u [A] )) }
• {t | Ø (t Î R 1)}
• {t | $ u Î R 1 (t [A] = u [A] ) Ù $ s Î R 2 (t [A] = s [A]) }

 

14. Consider a relation geq which represents "greater than or equal to", that is, (x, y) Î geq only if y ³ x.

create table geq

(Ib integer not null

ub integer not null

primary key Ib

foreign key (ub) references geq on delete cascade)

Which of the following is possible if a tuple (x, y) is deleted?

• A tuple (z, w) with z > y is deleted
• A tuple (z, w) with z > x is deleted
• A tuple (z, w) with w < x is deleted
• The deletion of (x, y) is prohibited