Design & Analysis of Algorithm MCQs
A) Linear Search
B) Binary Search
C) Depth-First Search
D) Breadth-First Search
Answer: B) Binary Search
---
Question 2: Which of the following is NOT a characteristic of binary search?
A) It requires the array to be sorted.
B) It has a time complexity of O(log n).
C) It can search through unsorted arrays efficiently.
D) It divides the search space in half at each step.
Answer: C) It can search through unsorted arrays efficiently.
---
Question 3: In binary search, what is the term used to describe the process of narrowing down the search space to find the target element?
A) Halving
B) Conquering
C) Recursion
D) Partitioning
Answer: A) Halving
---
Question 4: Which data structure is commonly used to implement binary search?
A) Linked List
B) Stack
C) Queue
D) Array
Answer: D) Array
---
Question 5: What is the worst-case time complexity of binary search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: B) O(log n)
Question 6: Which searching technique involves traversing the entire list or array sequentially until the target element is found?
A) Linear Search
B) Binary Search
C) Depth-First Search
D) Breadth-First Search
Answer: A) Linear Search
Question 7: In linear search, what is the best-case time complexity when the target element is found at the beginning of the list?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: A) O(1)
Question 8: Which searching technique is commonly used for searching in graphs or trees by exploring as far as possible along each branch before backtracking?
A) Linear Search
B) Binary Search
C) Depth-First Search
D) Breadth-First Search
Answer: C) Depth-First Search
Question 6: Which searching technique is suitable for unsorted arrays and sequentially checks each element until a match is found?
A) Linear Search
B) Binary Search
C) Interpolation Search
D) Depth-First Search
Answer: A) Linear Search
---
Question 7: What is the primary advantage of linear search over binary search?
A) It has a lower time complexity.
B) It does not require the array to be sorted.
C) It always finds the target element in fewer steps.
D) It consumes less memory.
Answer: B) It does not require the array to be sorted.
---
Question 8: Which searching technique is an enhancement of binary search, particularly effective when the elements are uniformly distributed?
A) Linear Search
B) Jump Search
C) Exponential Search
D) Interpolation Search
Answer: D) Interpolation Search
---
Question 9: In jump search, what is the role of the "jump" step?
A) It involves making large jumps in the array.
B) It determines the size of the next jump.
C) It decides whether to switch to binary search.
D) It is used to calculate the average jump length.
Answer: A) It involves making large jumps in the array.
---
Question 10: Which searching technique works best when the elements are uniformly distributed and the array is sorted?
A) Binary Search
B) Interpolation Search
C) Jump Search
D) Linear Search
Answer: C) Jump Search
---
Question 11: Which searching technique divides the array into blocks and performs a binary search on each block?
A) Block Search
B) Jump Search
C) Exponential Search
D) Interpolation Search
Answer: A) Block Search
---
Question 12: What is the primary disadvantage of linear search compared to binary search?
A) Higher time complexity
B) Requires sorted array
C) Requires more memory
D) Limited applicability
Answer: A) Higher time complexity
---
Question 13: In which scenario does linear search perform better than binary search?
A) When the array is very large
B) When the array is sorted in descending order
C) When the target element is located in the middle of the array
D) When the target element is located near the beginning of the array
Answer: D) When the target element is located near the beginning of the array
---
Question 14: Which searching technique involves recursively dividing the array into smaller subarrays until the target element is found or the array is empty?
A) Linear Search
B) Binary Search
C) Depth-First Search
D) Exponential Search
Answer: C) Depth-First Search
---
Question 15: In which situation does binary search perform poorly?
A) When the array is small
B) When the array is sorted in descending order
C) When the target element is located at the end of the array
D) When the array contains duplicate elements
Answer: B) When the array is sorted in descending order
Question 1: What is the average-case time complexity of linear search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: C) O(n)
---
Question 2: What is the worst-case time complexity of binary search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: B) O(log n)
---
Question 3: Which searching algorithm has a time complexity of O(log n) in both average and worst cases?
A) Linear Search
B) Binary Search
C) Interpolation Search
D) Exponential Search
Answer: B) Binary Search
---
Question 4: What is the worst-case time complexity of linear search?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: C) O(n)
---
Question 5: Which of the following searching algorithms has the best time complexity?
A) Linear Search
B) Binary Search
C) Jump Search
D) Interpolation Search
Answer: B) Binary Search
---
Question 6: What is the time complexity of binary search when the array is not sorted?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: B) O(log n)
---
Question 7: In the average case, which searching algorithm has a time complexity of O(log log n)?
A) Linear Search
B) Binary Search
C) Interpolation Search
D) Exponential Search
Answer: D) Exponential Search
---
Question 8: What is the time complexity of linear search when the target element is at the beginning of the array?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: A) O(1)
---
Question 9: Which searching algorithm has a time complexity of O(sqrt(n)) when the elements are uniformly distributed?
A) Linear Search
B) Binary Search
C) Jump Search
D) Interpolation Search
Answer: C) Jump Search
---
Question 10: What is the time complexity of binary search when implemented iteratively?
A) O(1)
B) O(log n)
C) O(n)
D) O(n^2)
Answer: B) O(log n)
Certainly! Here are some multiple-choice questions on the time complexity of sorting algorithms:
Question 1: What is the time complexity of the bubble sort algorithm?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Answer: C) O(n^2)
---
Question 2: Which sorting algorithm has the best-case time complexity of O(n) when the elements are already sorted?
A) Insertion Sort
B) Merge Sort
C) Quick Sort
D) Bubble Sort
Answer: A) Insertion Sort
---
Question 3: What is the average-case time complexity of quick sort?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Answer: B) O(n log n)
---
Question 4: Which sorting algorithm always performs in O(n log n) time complexity, regardless of the input data?
A) Quick Sort
B) Selection Sort
C) Merge Sort
D) Bubble Sort
Answer: C) Merge Sort
---
Question 5: Which sorting algorithm has the worst-case time complexity of O(n^2) but can be improved with certain optimizations?
A) Bubble Sort
B) Insertion Sort
C) Selection Sort
D) Quick Sort
Answer: D) Quick Sort
---
Question 6: What is the time complexity of merge sort in the worst-case scenario?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Answer: B) O(n log n)
---
Question 7: Which sorting algorithm typically performs better for smaller datasets due to its simplicity?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Heap Sort
Answer: C) Insertion Sort
---
Question 8: In which case does heap sort exhibit a time complexity of O(n log n)?
A) Best-case scenario
B) Average-case scenario
C) Worst-case scenario
D) All cases
Answer: D) All cases
---
Question 9: Which sorting algorithm is not comparison-based and has a time complexity of O(n+k)?
A) Bucket Sort
B) Quick Sort
C) Radix Sort
D) Merge Sort
Answer: A) Bucket Sort
---
Question 10: Which sorting algorithm is inherently stable, meaning it preserves the relative order of equal elements?
A) Quick Sort
B) Merge Sort
C) Selection Sort
D) Bubble Sort
Answer: B) Merge Sort
---
Question 11: What is the time complexity of selection sort in all cases?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Answer: C) O(n^2)
---
Question 12: Which sorting algorithm is known for its space efficiency and stability?
A) Quick Sort
B) Insertion Sort
C) Radix Sort
D) Heap Sort
Answer: B) Insertion Sort
---
Question 13: Which sorting algorithm has a time complexity of O(n log n) in the best-case scenario?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Bubble Sort
Answer: A) Merge Sort
---
Question 14: Which sorting algorithm is not suitable for large datasets due to its quadratic time complexity?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Radix Sort
Answer: C) Insertion Sort
---
Question 15: Which sorting algorithm has a time complexity that can degrade to O(n^2) in the worst-case scenario but is widely used due to its average-case performance?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Bucket Sort
Answer: B) Quick Sort
Question 16: Which sorting algorithm has a time complexity that remains O(n log n) even in the worst-case scenario?
A) Insertion Sort
B) Merge Sort
C) Quick Sort
D) Bubble Sort
Answer: B) Merge Sort
---
Question 17: What is the time complexity of shell sort in its worst-case scenario?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Answer: C) O(n^2)
---
Question 18: Which sorting algorithm is most efficient for sorting linked lists due to its ability to perform well with minimal data movement?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Selection Sort
Answer: A) Merge Sort
---
Question 19: Which sorting algorithm is also known as partition-exchange sort?
A) Bubble Sort
B) Quick Sort
C) Heap Sort
D) Selection Sort
Answer: B) Quick Sort
---
Question 20: What is the time complexity of counting sort, assuming the range of elements is known and small?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(k)
Answer: A) O(n)
---
Question 21: Which sorting algorithm is based on the concept of divide and conquer?
A) Insertion Sort
B) Bubble Sort
C) Quick Sort
D) Selection Sort
Answer: C) Quick Sort
---
Question 22: What is the time complexity of radix sort?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(k)
Answer: A) O(n)
---
Question 23: Which sorting algorithm is not suitable for large datasets due to its memory requirements?
A) Quick Sort
B) Merge Sort
C) Radix Sort
D) Insertion Sort
Answer: C) Radix Sort
---
Question 24: Which sorting algorithm is commonly used for sorting small datasets due to its simplicity and low overhead?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Heap Sort
Answer: C) Insertion Sort
---
Question 25: What is the time complexity of bubble sort in its average-case scenario?
A) O(n)
B) O(n log n)
C) O(n^2)
D) O(log n)
Answer: C) O(n^2)
---
Question 26: Which sorting algorithm is most affected by the order of elements in the input array?
A) Quick Sort
B) Merge Sort
C) Bubble Sort
D) Insertion Sort
Answer: C) Bubble Sort
---
Question 27: Which sorting algorithm is stable, meaning it preserves the relative order of equal elements?
A) Quick Sort
B) Selection Sort
C) Radix Sort
D) Merge Sort
Answer: D) Merge Sort
---
Question 28: In which scenario does selection sort perform best?
A) When the dataset is nearly sorted
B) When the dataset is already sorted
C) When the dataset is randomly arranged
D) When the dataset is large
Answer: C) When the dataset is randomly arranged
---
Absolutely! Here are some multiple-choice questions about recursive functions:
Question 1: What is a recursive function?
A) A function that calls itself directly or indirectly.
B) A function that only accepts integer arguments.
C) A function that performs a linear search.
D) A function that sorts elements using a recursive approach.
Answer: A) A function that calls itself directly or indirectly.
---
Question 2: What is the base case in a recursive function?
A) The case where the function returns an error.
B) The case where the function calls itself infinitely.
C) The case where the function stops calling itself and returns a value.
D) The case where the function contains no conditional statements.
Answer: C) The case where the function stops calling itself and returns a value.
---
Question 3: Which of the following is true about recursion?
A) Recursion is always more efficient than iteration.
B) Recursion uses less memory than iteration.
C) Recursion can lead to infinite loops if not implemented correctly.
D) Recursion is limited to mathematical calculations.
Answer: C) Recursion can lead to infinite loops if not implemented correctly.
---
Question 4: In a recursive function, what is the role of the "recursive step"?
A) To perform the final computation.
B) To return the result.
C) To call the function itself with a smaller input.
D) To check if the base case has been reached.
Answer: C) To call the function itself with a smaller input.
---
Question 5: What is tail recursion?
A) A recursive function with no base case.
B) A recursive function where the recursive call is the last operation in the function.
C) A recursive function with multiple base cases.
D) A recursive function that uses a loop instead of recursion.
Answer: B) A recursive function where the recursive call is the last operation in the function.
---
Question 6: Which of the following is NOT a characteristic of recursive functions?
A) They can solve problems by breaking them down into smaller, similar subproblems.
B) They can be less intuitive to understand compared to iterative solutions.
C) They always result in better performance than iterative solutions.
D) They require a base case to terminate the recursion.
Answer: C) They always result in better performance than iterative solutions.
---
Question 7: What is the primary advantage of using recursion?
A) Recursion always results in faster execution time.
B) Recursion is easier to implement than iteration.
C) Recursion can solve problems that have a natural recursive structure more elegantly.
D) Recursion does not require a base case.
Answer: C) Recursion can solve problems that have a natural recursive structure more elegantly.
---
Question 8: What happens if a recursive function lacks a base case?
A) The function will return an error.
B) The function will go into an infinite loop.
C) The function will terminate immediately.
D) The function will output incorrect results.
Answer: B) The function will go into an infinite loop.
---
Question 9: Which programming languages typically support recursion?
A) Only functional programming languages.
B) Only object-oriented programming languages.
C) Both functional and procedural programming languages.
D) Recursion is not supported in any programming languages.
Answer: C) Both functional and procedural programming languages.
---
Question 10: When should you use recursion instead of iteration?
A) When performance is critical.
B) When the problem can be easily solved iteratively.
C) When the problem can be broken down into smaller, similar subproblems.
D) When the problem involves complex mathematical calculations.
Answer: C) When the problem can be broken down into smaller, similar subproblems.
Question 1:
```python
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
print(factorial(5))
```
What will be the output of the code?
A) 0
B) 1
C) 5
D) 120
Answer: D) 120
---
Question 2:
```python
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(6))
```
What will be the output of the code?
A) 8
B) 13
C) 21
D) 34
Answer: B) 13
---
Question 3:
```python
def power(base, exponent):
if exponent == 0:
return 1
else:
return base * power(base, exponent-1)
print(power(2, 3))
```
What will be the output of the code?
A) 6
B) 8
C) 16
D) 64
Answer: C) 16
---
Question 4:
```python
def reverse_string(s):
if len(s) == 0:
return s
else:
return reverse_string(s[1:]) + s[0]
print(reverse_string("hello"))
```
What will be the output of the code?
A) "olleh"
B) "olleh"
C) "hello"
D) "eholl"
Answer: A) "olleh"
---
Question 5:
```python
def sum_of_digits(n):
if n == 0:
return 0
else:
return n % 10 + sum_of_digits(n // 10)
print(sum_of_digits(12345))
```
What will be the output of the code?
A) 15
B) 10
C) 14
D) 5
Answer: A) 15
---
Question 6:
```python
def print_odd_numbers(n):
if n > 0:
print_odd_numbers(n - 1)
if n % 2 != 0:
print(n)
print_odd_numbers(7)
```
What will be the output of the code?
A) 1 3 5 7
B) 7 5 3 1
C) 2 4 6
D) 1 2 3 4 5 6 7
Answer: B) 7 5 3 1
Question 7:
```python
def print_numbers(n):
if n > 0:
print_numbers(n - 1)
print(n)
print_numbers(5)
```
What will be the output of the code?
A) 1 2 3 4 5
B) 5 4 3 2 1
C) 1 2 3 4
D) 5 4 3 2
Answer: B) 5 4 3 2 1
---
Question 8:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
print(gcd(48, 18))
```
What will be the output of the code?
A) 6
B) 12
C) 18
D) 24
Answer: A) 6
---
Question 9:
```python
def print_triangle(n):
if n > 0:
print_triangle(n - 1)
print('*' * n)
print_triangle(5)
```
What will be the output of the code?
A)
```
*
**
***
****
*****
```
B)
```
*****
****
***
**
*
```
C)
```
*****
****
***
**
*
```
D)
```
*
**
***
****
*****
```
Answer: D)
```
*
**
***
****
*****
```
---
Number of comparisons required to search an element X = 18 in the list A = [ 5, 44, 89, 22, 18, 9, 3, 15, 8 ] using linear search.
A. 2
B. 3
C. 4
D. 5
Which of the following algorithms use recursion for sorting an array of integers?
A. Bubble sort
B. Insertion sort
C. Merge sort
D. Selection sort
What is an external sorting algorithm?
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’
Answer: a
a) Algorithm that uses tape or disk during the sort
b) Algorithm that uses main memory during the sort
c) Algorithm that involves swapping
d) Algorithm that are considered ‘in place’
a) 4
b) 2
c) 1
d) 0
a) The input is already sorted
b) A large file has to be sorted
c) Large values need to be sorted with small keys
d) Small values need to be sorted with large keys
Answer: c
a) 5 and 4
b) 4 and 5
c) 2 and 4
d) 2 and 5
Explanation: Since the input array is not sorted, bubble sort takes 5 ie n iterations and selection sort takes 4 ie(n-1) iterations
a) N
b) N-1
c) N+1
d) N2
14, 12,16, 6, 3, 10
a) 6
b) 5
c) 7
d) 1
Answer: b
Explanation: The number of passes is given by N-1. Here, N=6. Therefore,
6-1=5 passes.
34, 8, 64, 51, 32, 21
a) 8, 21, 32, 34, 51, 64
b) 8, 32, 34, 51, 64, 21
c) 8, 34, 51, 64, 32, 21
d) 8, 34, 64, 51, 32, 21
a) partitioning
b) merging
c) exchanging
d) selection
Answer: b
Design & Analysis of Algorithm
![Design & Analysis of Algorithm]()
Reviewed by Asst. Prof. Sunita Rai
on
February 14, 2024
Rating:
No comments: