1.If one uses straight two-way, merge sort algorithm to sort the following elements in ascending order:

20, 47, 15, 8, 9, 4, 40, 30, 12, 17

then the order of these elements after second pass of the algorithm is :

• 8,9, 15,20,47,4, 12, 17,30,40
• 8, 15,20,47,4,9,30,40, 12, 17
• 15,20,47, 4, 8, 9,12,30,40,17
• 4,8,9,15, 20,47, 12, 17,30,40

• The number of articulation points of the following graph is

• 0
• 1
• 2
• 3

2. If n is a power of 2, then the minimum number of multiplications needed to compute a* is

• log 2n
• 
• n-I
• n

3. Which of the following is the most powerful parsing method?

• LL (I)
• Canonical LR
• SLR
• LALR

4. Consider the join of a relation R with a relation S. If R has m tuples and S has n tuples then the maximum and minimum sizes of the join respectively are

• m+n and O
• mn and O
• m+ n and |m-n |
• mn and m+ n

5. The relational algebra expression equivalent to the following tuple calculus expression:

{t | t Î r Ù (t [A] = 10 Ù t = 20)} is :

• s (A=10vB=20) (r)
• s (A=l0) (r) È s (B=20) (r)
• s (A= 10) (r) Ç s (B=20) (r)
• s (A=IO) (r) - s (B=20) (r)

6. Booth's coding in 8 bits for the decimal number - 57 is

• 0 - 100 + 1000
• 0 - 100 + 100 – I
• 0 - 1 + 100 -10 + I
• 00- 10 + 100-1

7. The maximum gate delay for any output to appear in an array multiplier for multiplying two n bit number is

• O(n 2)
• O(n)
• O (log n)
• O (I)

8. The main memory of a computer has 2 cm blocks while the cache has 2 c blocks. If the cache uses the set associative mapping scheme with 2 blocks per set, then block k of the main memory maps to the set

• (k mod m) of the cache
• (k mod c) of the cache
• (k mod 2c) of the cache
• (k mod 2 cm) of the cache

9. The Newton-Raphson method is to be used to find the root of the equation f (x) = 0 where Xo is the initial approximation and f 1 is the derivative of f. The method converges

• always
• only if f is a polynomial
• only if f (x o) < 0
• none of the above

10. Let R = (a, b, c, d, e, f) be a relation scheme with the following dependencies c ® f, e ® a, ec ® d, a ® b. Which of the following is a key for R ?

• CD
• EC
• AE
• AC

11. Which of the following is correct?

• B-trees are for storing data on disk and B* trees are for main memory.
• Range queries are faster on B* trees.
• B-trees are for primary indexes and B* trees are for secondary indexes.
• The height of a B* tree is independent of the number of records.