ā˜‘ MCQ PRACTICE

Design and Analysis of Algorithms Unit 1

Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.

šŸ“š Design and Analysis of Algorithms
šŸ“– Unit 1
šŸŽÆ MCQs
Design and Analysis of Algorithms MCQs - Unit 1

Design and Analysis of Algorithms MCQs - Unit 1

1

Which of the following is NOT a characteristic of an algorithm?

A Ambiguity
B Definiteness
C Finiteness
D Effectiveness
Correct Answer Ambiguity
2

The space needed by an algorithm is the sum of a fixed part and a

A constant part only
B variable part
C hidden part
D compile-time part
Correct Answer variable part
3

The time complexity of an algorithm is usually measured using

A step count (frequency count)
B the color of the output
C the size of the source file
D the programmer's experience
Correct Answer step count (frequency count)
4

Big-oh notation gives an asymptotic

A lower bound
B exact bound only
C average bound only
D upper bound
Correct Answer upper bound
5

Omega notation gives an asymptotic

A upper bound
B lower bound
C loose upper bound
D constant bound
Correct Answer lower bound
6

Theta notation gives an asymptotic

A upper bound only
B lower bound only
C no bound
D tight bound (both upper and lower)
Correct Answer tight bound (both upper and lower)
7

Little-oh notation represents an upper bound that is

A asymptotically tight
B a lower bound
C not asymptotically tight
D always constant
Correct Answer not asymptotically tight
8

If f(n) = 3n + 2, then f(n) is

A O(1)
B O(log n)
C O(n²) only and not O(n)
D O(n)
Correct Answer O(n)
9

Which is the correct order of growth from slowest to fastest?

A n < log n < n² < n log n
B log n < n < n log n < n²
C n² < n log n < n < log n
D n log n < n < log n < n²
Correct Answer log n < n < n log n < n²
10

The worst-case time complexity of binary search is

A O(log n)
B O(n)
C O(n log n)
D O(1)
Correct Answer O(log n)
11

Binary search can be applied only to

A a sorted list
B an unsorted list
C a linked list only
D a list of strings only
Correct Answer a sorted list
12

The time complexity of merge sort in the best, average and worst cases is

A O(n²)
B O(n)
C O(log n)
D O(n log n)
Correct Answer O(n log n)
13

The extra space required by merge sort is

A O(1)
B O(n)
C O(log n) only
D O(n²)
Correct Answer O(n)
14

The average-case and worst-case time complexities of quick sort are

A O(n) and O(n log n)
B O(n log n) and O(n²)
C O(n²) and O(n²)
D O(log n) and O(n)
Correct Answer O(n log n) and O(n²)
15

The worst case of quick sort occurs when

A the array is already sorted and the first or last element is the pivot
B the pivot is always the median
C the array has one element
D the array is randomly shuffled
Correct Answer the array is already sorted and the first or last element is the pivot
16

Quick sort is based on the

A divide-and-conquer technique
B greedy technique
C dynamic programming
D backtracking
Correct Answer divide-and-conquer technique
17

The time complexity of Strassen's matrix multiplication is approximately

A O(n³)
B O(n²)
C O(n log n)
D O(n^2.81)
Correct Answer O(n^2.81)
18

Strassen's method multiplies two 2 Ɨ 2 matrices using how many multiplications?

A 8
B 7
C 6
D 4
Correct Answer 7
19

The recurrence relation for merge sort is

A T(n) = 2T(n/2) + n
B T(n) = T(n āˆ’ 1) + n
C T(n) = T(n/2) + 1
D T(n) = 7T(n/2) + n²
Correct Answer T(n) = 2T(n/2) + n
20

The recurrence relation for binary search is

A T(n) = 2T(n/2) + n
B T(n) = T(n āˆ’ 1) + 1
C T(n) = T(n/2) + 1
D T(n) = 2T(n āˆ’ 1)
Correct Answer T(n) = T(n/2) + 1
21

The three steps of the divide-and-conquer method are

A sort, search and delete
B read, write and print
C push, pop and peek
D divide, conquer and combine
Correct Answer divide, conquer and combine
22

The best-case time complexity of binary search is

A O(1)
B O(log n)
C O(n)
D O(n log n)
Correct Answer O(1)
23

Which of the following is a stable sorting algorithm?

A Quick sort
B Heap sort
C Selection sort
D Merge sort
Correct Answer Merge sort
24

The recurrence relation for Strassen's matrix multiplication is

A T(n) = 7T(n/2) + O(n²)
B T(n) = 8T(n/2) + O(n²)
C T(n) = 2T(n/2) + n
D T(n) = T(n/2) + 1
Correct Answer T(n) = 7T(n/2) + O(n²)
25

f(n) = Θ(g(n)) means that f(n) is bounded

A only above by g(n)
B only below by g(n)
C both above and below by constant multiples of g(n)
D by no function
Correct Answer both above and below by constant multiples of g(n)

Fill in the Blanks

26 The space complexity of an algorithm is the sum of a fixed part and a ______ part.
Correct Answer variable
27 Big-oh notation gives an asymptotic ______ bound.
Correct Answer upper
28 Omega notation gives an asymptotic ______ bound.
Correct Answer lower
29 Theta notation gives an asymptotic ______ bound.
Correct Answer tight
30 Binary search can be applied only to a ______ list.
Correct Answer sorted
31 The worst-case time complexity of binary search is ______.
Correct Answer O(log n)
32 The worst-case time complexity of merge sort is ______.
Correct Answer O(n log n)
33 The worst-case time complexity of quick sort is ______.
Correct Answer O(n²)
34 In quick sort, the element used to partition the array is called the ______.
Correct Answer pivot
35 Strassen's method multiplies two 2 Ɨ 2 matrices using ______ multiplications.
Correct Answer 7
36 The time complexity of Strassen's matrix multiplication is O(n^______) approximately.
Correct Answer 2.81
37 The three steps of divide and conquer are divide, conquer and ______.
Correct Answer combine
38 The recurrence relation of merge sort is T(n) = 2T(n/2) + ______.
Correct Answer n
39 ______ notation represents an upper bound that is not asymptotically tight.
Correct Answer Little-oh
40 Merge sort needs ______ additional space.
Correct Answer O(n)
← Back to All MCQs