NEW
Font size
WorksheetsAlgorithm UNIT Quiz
Total questions: 30
Worksheet time: 15mins
What is the time complexity of a linear search algorithm?
O(n)
O(log n)
O(n log n)
O(1)
Which asymptotic notation gives the upper bound of an algorithm's time complexity?
Big-O
Big-Ω
Big-Θ
None
What is the worst-case time complexity of a binary search algorithm?
O(n)
O(log n)
O(n log n)
O(1)
Which algorithm has a time complexity of O(n^2)?
Bubble sort
Selection sort
Insertion sort
All of the above
What is the best-case time complexity of a heap sort algorithm?
O(n)
O(log n)
O(n log n)
O(1)
Which data structure is used in a heap sort algorithm?
Array
Linked list
Stack
Queue
What is the time complexity of a naive string-matching algorithm?
O(n)
O(n^2)
O(n log n)
O(1)
Which algorithm is used for finding a pattern in a text?
Rabin-Karp algorithm
Knuth-Morris-Pratt algorithm
Naive string-matching algorithm
All of the above
What is the time complexity of a binary search algorithm in the average case?
O(n)
O(log n)
O(n log n)
O(1)
Which asymptotic notation gives the lower bound of an algorithm's time complexity?
Big-O
Big-Ω
Big-Θ
None
What is the worst-case time complexity of an insertion sort algorithm?
O(n)
O(n^2)
O(n log n)
O(1)
Which data structure is used in a hash table?
A) Array
B) Linked list
C) Stack
D) Queue
What is the best-case time complexity of a quick sort algorithm?
O(n)
O(log n)
O(n log n)
O(1)
Which data structure is used in a merge sort algorithm?
Array
Linked list
Stack
Queue
What is the time complexity of a Knuth-Morris-Pratt algorithm?
O(n)
O(n^2)
O(n log n)
O(1)
Which algorithm is used for finding a pattern in a text?
Rabin-Karp algorithm
Knuth-Morris-Pratt algorithm
Naive string-matching algorithm
All of the above
What is the time complexity of a binary search algorithm in the worst case?
O(n)
O(log n)
O(n log n)
O(1)
Which data structure is used in a binary search algorithm?
A) Array
B) Linked list
C) Stack
D) Queue
What is the worst-case time complexity of a selection sort algorithm?
O(n)
O(n^2)
O(n log n)
O(1)
Akhil is trying to find a specific book in a library. He knows that the library uses a hashing system to categorize its books. Which algorithm has a time complexity of O(1)?
Linear search
Binary search
Hashing
None
What is the difference between best case, worst case, and average case analysis?
Best case: average performance; Worst case: minimum performance; Average case: maximum performance.
Best case: minimum performance; Worst case: maximum performance; Average case: expected performance.
Best case: expected performance; Worst case: average performance; Average case: minimum performance.
Best case: maximum performance; Worst case: expected performance; Average case: minimum performance.
How does binary search improve upon linear search?
Binary search can be applied to unsorted data without any preprocessing.
Binary search is faster than linear search because it reduces the search space exponentially.
Binary search requires more comparisons than linear search.
Linear search is more efficient for large datasets than binary search.
Describe the interpolation search algorithm and its use cases.
Interpolation search is best used for uniformly distributed sorted arrays, particularly when the dataset is large and the values are evenly distributed.
Interpolation search is primarily used for searching in linked lists.
Interpolation search can be used for any type of data distribution.
Interpolation search is effective for small, unsorted datasets.
What is the naive string matching algorithm?
A complex algorithm that uses dynamic programming to find substrings.
The naive string matching algorithm is a straightforward method for finding a substring in a string by checking each position for a match.
An algorithm that sorts the string before searching for the substring.
A method that only checks the first character of the string for matches.
How does the Rabin-Karp algorithm work?
It employs a binary search method to locate patterns.
The algorithm relies on sorting the text and patterns.
The Rabin-Karp algorithm works by using hashing to efficiently search for patterns in a text.
It uses brute force to find patterns in the text.
What is the main advantage of the Knuth-Morris-Pratt algorithm over naive string matching?
It has a linear time complexity compared to the naive algorithm's quadratic time complexity.
It uses a brute-force approach for pattern matching.
It requires more memory than the naive algorithm.
It can only match patterns of fixed length.
In what scenarios would you prefer interpolation search over binary search?
When the data is sorted in descending order.
When the data is uniformly distributed.
When the data is highly skewed.
When the dataset is small and unsorted.
What is the role of the prefix table in the KMP algorithm?
The prefix table determines the length of the pattern to be searched.
The prefix table helps in skipping unnecessary comparisons in the KMP algorithm.
The prefix table is used to store the final results of the KMP algorithm.
The prefix table is a data structure that holds the frequency of characters in the pattern.
What is the purpose of asymptotic notation in algorithm analysis?
To measure the speed of computer hardware.
To determine the exact runtime of an algorithm.
To provide a graphical representation of algorithms.
To describe the efficiency and growth rates of algorithms.
Define time complexity and space complexity.
Time complexity is the measure of time an algorithm takes to run, while space complexity is the measure of memory an algorithm uses.
Space complexity is the speed at which an algorithm executes.
Time complexity refers to the amount of data an algorithm can process.
Time complexity is the total number of lines in an algorithm.
