CS502 Midterm Solved MCQs with References

1. (Handsouts Page 35 Line 4)

precisely

2.

keep elements in increasing or decreasing order (Handsouts Page 39 Line 6)

3.

4. In Sieve Technique we don’t know which item is of interest

True

False

5.

T(n) T(n / 2)

log n

n / 2 + n / 4

6. Divide-and-conquer as breaking the problem into a small number of pivot Sieve

smaller sub problems (handouts page 27)

Selection

7.

heap order (handouts page 40)

8. Slow sorting algorithms run in, T(n^2) T(n) T( log n)

T(n log n) (handsouts page 40)

9. One of the clever aspects of heaps is that they can be stored in arrays without using any

pointers

constants variables functions

10. Sorting is one of the few problems where provable bonds exits on how fast we can sort, upper

lower

2nd

11. For the sieve technique we solve the problem,

precisely

Q12. Sieve Technique can be applied to selection problem?

true

false

13. How much time merge sort takes for an array of numbers? (n^2) T(n) T( log n)

T(n log n)

(handouts page 30)

14. For the Sieve Technique we take time

T(nk)

(handouts page 34)

T(n / 3) n^2 n/3

15. Heaps can be stored in arrays without using any pointers; this is due to the nature of the binary tree,

left-complete

Repeat

right-complete tree nodes tree leaves

Q16. How many elements do we eliminate in each time for the Analysis of Selection algorithm?

n / 2 elements

(n / 2) + n elements

n / 4 elements 2 n elements

17. We do sorting to,

keep elements in increasing or decreasing order ( page 39 Repeat)

Q18. In which order we can sort?

increasing order or decreasing order

Repeat

both at the same time

19. A heap is a left-complete binary tree that conforms to the

heap order (page 40)

20. In the analysis of Selection algorithm, we make a number of passes, in fact it could

T(n) T(n / 2)

log n

(page 37)

n / 2 + n / 4

21. A heap is a left-complete binary tree that conforms to the

heap order (page 40)

22. How much time merge sort takes for an array of numbers? T(n^2) T(n) T( log n)
23. n the analysis of Selection algorithm, we eliminate a constant fraction of the array with each phase; we get the convergent linear

geometric

(page 37)

exponent