CS502 Quiz Mega File 3

Q1. The sequence of merge sort algorithm is:

1. Divide Combine-Conquer
2. Conquer-Divide-Combine
3. Divide-Conquer-Combine
4. Combine-Divide-Conquer

Q2. In ______ Knapsack Problem, limitation is that an item can either be put in the bag or not. Fractional items are not allowed.

1. 0
2. 1
3. 0/1
4. Fractional

Q3. In Selection algorithm, we assume pivot selection takes theta _______ running time.

1. n

Page - 36 · b. n2 · c. n3 · d. log (n)

Q4. In Heap Sort algorithm (using max heap), when every time maximum elements removed from top ________.

1. We call merge Sort Algorithm
2. it becomes Order n2 Algorithm
3. Divide and Conquer strategy helps us
4. We are left with a hole

Page – 41

Q5. If matrix A of dimension p x q is multiply with matrix B of dimension q x r, then each entry in resultant matrix takes _______ time.

1. O (q)

Page - 84 · b. O (1) · c. O (p x q) · d. O (q x r)

AL-JUNAID INSTITUTE OF GROUP

Q6. _________ is a method of solving a problem in which we check all possible solutions to the problem to find the solution we need.

1. Plane-Sweep Algorithm
2. Sorting Algorithm
3. Brute-Force Algorithm

google

d. Greedy approach

Q7. The worst case running time of Quick sort algorithm _____.

1. Cannot be quadratic
2. Is quadratic
3. ls always Exponential
4. Is linear

Q8. In max heap (for Heap Sort algorithm), when every time maximum element is removed from top we replace it with _____ leaf in the tree.

1. second last
2. Last

Page -41 · c. First · d. Any

Q9. Quick sort algorithm was developed by -

1. AlferdAho
2. Sedgewick
3. John Vincent Atanasoff
4. Tony Hoare

– Google wikipedia

Q10. If Matrix-A has dimensions "3x2" and Matrix-B has dimensions "2x3", then multiplication of Matrix-A and Matrix-B will result a new Matrix-C having dimensions.

1. 3x2
2. 2x3
3. 2x2
4. 3x3

Q11. For comparison-based sorting algorithms, it is possible to sort more efficiently than Omega n log(n) time.

1. Always
2. Not

P-54 · c. Sometimes · d. Sometimes not

Q12. Dynamic Programming approach is usually useful in solving optimization problems.

1. True
2. False

Q13. In Sorting the key value or attribute_____ from an ordered domain.

1. Must be
2. Not always
3. May be
4. Occasionally

Q14. Result of asymptotical analysis of n(n -3) and 4n*n is that _______

1. n(n-1) is asymptotically Less
2. n(n-1) is asymptotically Greater
3. Both are asymptotically Not equivalent
4. Both are asymptotically Equivalent

page 23 (4n*n= 4n2)

Q15. Floor and ceiling are ______ to calculate while analyzing algorithms a. Very easy

1. Usually considered difficult

P-31 · c. 3rd Option is missing · d. 4th Option is missing

Q16. _____ of reference is an important fact of current processor technology.

1. Defining
2. Assigning
3. Formality
4. Locality

P-8

Q17. In max-heap, largest element is stored at root node. Where is the smallest element stored?

1. Right Node
2. Leaf Node
3. Middle Node
4. Left Node