1.Suppose you are given an array s[1..n] and a procedure reverse (s, i, j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 £ k £ n:

reverse (s, 1, k) ;

reverse (s, k + 1, n);

reverse (s, l, n) ;

(a) Rotates s left by k positions (b) Leaves s unchanged

(c) Reverses all elements of s (d) None of the above

2. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal, respectively, of a complete binary tree. Which of the following is always true?

(a) LASTIN = LASTPOST (b) LASTIN = LASTPRE

(c) LASTPRE = LASTPOST (d) None of the above

3. Consider the following functions

Which of the following is true?

(a) h (n) is O (f (n) ) (b) h (n) is O (g (n))

(c) g (n) is not O (f (n) ) (d) f(n) is O(g (n))

4. Let G be an undirected connected graph with distinct edge weight. Let e max be the edge with maximum weight and e min the edge with minimum weight. Which of the following statements is false?

• Every minimum spanning tree of G must contain e min
• If e max is in a minimum spanning tree, then its removal must disconnect G
• No minimum spanning tree contains e max
• G has a unique minimum spanning tree

5. Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

(a) {u,v} must be an edge in G, and u is a descendant of v in T

(b) {u,v} must be an edge in G, and v is a descendant of u in T

(c) If {u,v} is not an edge in G then u is a leaf in T

(d) If {u,v} is not an edge in G then u and v must have the same parent in T

6.The value of j at the end of the execution of the following C program

int incr (int i)

{

static int count = 0 ;

count = count + i ;

return ( count) ;

}

main ( ) {

int i, j ;

for (i = 0; i < = 4 ; i++)

j = incr (i) ;

}

is

• 10
• 4
• 6
• 7

7.Given the following expression grammar:

E ® E * F | F+E | F

F ® F-F | id

Which of the following is true?

(a) * has higher precedence than + (b) - has higher precedence than *

(c) + and - have same precedence (d) + has higher precedence than *

8. Suppose the time to service a page fault is on the average 10 milliseconds, while a memory access takes 1 microsecond. Then a 99.99% hit ratio results in average memory access time of

(a) 1.9999 milliseconds (b) 1 millisecond

(c) 9.999 microseconds (d) 1.9999 microseconds

9. Which of the following is NOT a valid deadlock prevention scheme?

(a) Release all resources before requesting a new resource

(b) Number the resources uniquely and never request a lower numbered resource than the last one requested

(c) Never request a resource after releasing any resource

(d) Request and all required resources be allocated before execution

10. Given the following relation instance

1 4 2

1 5 3

1 6 3

3 2 2

11.Which of the following functional dependencies are satisfied by the instance?

(a) XY ® Z and Z ® Y (b)YZ ® X and Y ® Z

(c)YZ ® X and X ® Z (d) XZ ® Y and Y ® X

12. Given relations r (w, x) and s (V, 1,), the result of

select distinct w, x

from r, s

is guaranteed to be same as r, provided

• r has no duplicates and s is non-empty
• r and shave no duplicates
• s has no duplicates and r is non-empty
• r and s have the same number of tuples

13. In SQL, relations can contain null values, and comparisons with null values are treated as unknown. Suppose all comparisons with a null value are treated as false. Which of the following pairs is not equivalent?

(a) x = 5 not (not (x = 5 ) )

(b) x= 5 x> 4 and x < 6, where x is an integer

(c) x ¹ 5 not (x = 5)

(d) None of the above