CS502 Midterm MCQs by Talha Sajid

Q1. . Heap sort is a/an _______ and ________ sorting algorithm.

1. Not in-place, not stable one
2. In-place, not stable one
3. Not in-place, stable one
4. In-place, stable one

Correct answer: In-place, not stable one

Q2. The sequence of merge sort algorithm is:

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

Correct answer: Divide-Conquer-Combine

Q3. 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

Correct answer: 0/1

4. In Heap Sort algorithm (using max heap), when every time

maximum elements removed from top ________. a) We call merge Sort Algorithm b) it becomes Order n2 Algorithm c) Divide and Conquer strategy helps us

d) We are left with a hole

Q5. In Bucket sort, if there are duplicates then each bin can be replaced by a __________.

1. Hash table
2. Heap
3. Stack
4. Linked list

Correct answer: Linked list

6. If there are duplicates in __________ sort, then each bin can be

replaced by a linked list. a) Heap b) Merge

c) Bucket

d) Quick

Q7. The average case running time of quick sort algorithm is theta _________.

1. n x n log(n)
2. Log(n)
3. nlog(n)
4. (n)

Correct answer: nlog(n)

Q8. Quick sort algorithm required a lot of comparisons in the ____________ condition.

1. Worst case
2. Best and Average case
3. Average case
4. Best case

Correct answer: Worst case

Q9. Memorization is a part of ________ programming strategy.

1. dynamic
2. fast
3. memory
4. slow

Correct answer: dynamic

Q10. ____________ programming is essentially recursion without repetition.

1. array
2. Dynamic
3. N log n
4. Fast

Correct answer: array

Q11. The main shortcoming of counting sort is that it is useful for__________.

1. large integers
2. large real numbers
3. small real numbers
4. small integers

Correct answer: small integers

Q12. 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
3. First
4. Any

Correct answer: Last

Q13. Quick sort algorithm was developed by -

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

Correct answer: Tony Hoare