1. Randomized quick sort is an extension of quick sort where the pivot is chosen randomly. What is the worst-case complexity of sorting n numbers using randomized quick sort?

• O(n)
• O(n log n)
• O (n 2)
• O(n!)

2. Consider an array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i £ n), the index of the parent is

• i-I
• ë i/2 û
• é i/21 ù
• (i+1)/2

3.  Let f(n) = n 2 1 g n and g(n) = n (1 g n) 10 be two positive functions of n. Which of the following statements is correct ?

• f(n) = O(g(n) and g(n) ¹ O(f(n))
• g(n) = O(f(n) and f(n) ¹ O(g(n))
• f(n) ¹ O(g(n)) and g(n) ¹ O(f(n))

(d) f(n) = O(g(n)) and g(n) = O(f(n))

4. The process of assigning load addresses to the various parts of the program and adjusting the code and date in the program to reflect the assigned addresses is called

(a) Assembly (b) Parsing

(c) Relocation (d) Symbol resolution

5. Which of the following statements is false? ­

• An unambiguous grammar has same leftmost and rightmost derivation
• An LL(1) parser is a top-down parser
• LALR is more powerful than SLR

(d) An ambiguous grammar can never be LR(k) for any k

6. Consider a set of n tasks with known runtimes r 1, r 2, ... r n to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput?

(a) Round-Robin (b) Shortest-Job-First

(c) Highest-Response-Ratio-Next (d) First-Come-First-Served

7. Where does the swap space reside ?

(a) RAM (b) Disk

(c) ROM (d) On-chip cache

8. Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will

• always decrease the number of page faults
• always increase the number of page faults
• some times increase the number of page faults
• never affect the number of page faults

9. Which of the following requires a device driver?

• Register
• Cache
• Main memory
• Disk

10. Consider a schema R(A, B, C, D) and functional dependencies A ® B and C ® D. Then the decomposition of R into R 1 (AB) and R 2(CD) is

• dependency preserving and loss less join
• loss less join but not dependency preserving
• dependency preserving but not loss less join
• not dependency preserving and not loss less join

11. Suppose the adjacency relation of vertices in a graph is represented in a table Adj(X, Y). Which of the following queries cannot be expressed by a relational algebra expression of constant length?

(a) List all vertices adjacent to a given vertex

• List all vertices which have self loops
• List all vertices which belong to cycles of less than three vertices
• List all vertices reachable from a given vertex

12. Let r and s be two relations over the relation schemes R and S respectively, and let A be an attribute in R. Then the relational algebra expression s A=a (r |X| s) is always equal to

(a) s A=a (r) (b) r

(e) s A=a (r) |X| s (d) none of the above