10 practice sets · Page 1 of 1
Given input string = "ABCDABCATRYCARCABCSRT" and pattern string = "CAT". Find the first index of the pattern match using Quick search algorithm.
2
6
11
14
Correct Answer: B — 6
Explanation:
Using Quick search algorithm, searching starts from the leftmost character and finds the first occurrence of the pattern "CAT" at index 6.
The searching phase in Quick search algorithm has good practical behaviour.
True
False
Correct Answer: A — True
Explanation:
During the searching phase, comparisons can be done in any order. It has quadratic worst-case behaviour but good practical behaviour.
What is the worst case running time in the searching phase of Boyer-Moore's algorithm?
O(n)
O(log n)
O(m+n)
O(mn)
Correct Answer: D — O(mn)
Explanation:
If the pattern occurs in the text, the worst case running time of Boyer-Moore's algorithm is O(mn).
What character shift tables does Boyer-Moore's search algorithm use?
Good-character shift tables
Bad-character shift tables
Next-character shift tables
Both good and bad character shift tables
Correct Answer: D — Both good and bad character shift tables
Explanation:
Boyer-Moore's algorithm uses both good-character and bad-character shift tables, whereas Quick search uses only bad-character shift tables.
Quick search algorithm starts searching from the rightmost character to the left.
True
False
Correct Answer: B — False
Explanation:
Quick search algorithm starts searching from the leftmost character to the right, and uses only bad-character shift tables.
What is the space complexity of the Quick search algorithm?
O(n)
O(log n)
O(m+n)
O(mn)
Correct Answer: A — O(n)
Explanation:
The space complexity of the Quick search algorithm is O(n), where n represents the input size.
What character shift tables does the Quick search algorithm use?
Good-character shift tables
Bad-character shift tables
Next-character shift tables
Both good and bad character shift tables
Correct Answer: B — Bad-character shift tables
Explanation:
Quick search algorithm uses only bad-character shift tables, which is one of the reasons for its increased speed over Boyer-Moore's algorithm.
What is the time complexity of the Quick search algorithm?
O(n)
O(log n)
O(m+n)
O(mn)
Correct Answer: C — O(m+n)
Explanation:
The time complexity of the Quick search algorithm is O(m+n), which is proven to be faster than Boyer-Moore's algorithm.
Which of the following algorithms formed the basis for the Quick search algorithm?
Boyer-Moore's algorithm
Parallel string matching algorithm
Binary search algorithm
Linear search algorithm
Correct Answer: A — Boyer-Moore's algorithm
Explanation:
Quick search algorithm was developed to overcome the drawbacks of Boyer-Moore's algorithm, improving speed and efficiency.
Which of the following is the fastest algorithm in the string matching field?
Boyer-Moore's algorithm
String matching algorithm
Quick search algorithm
Linear search algorithm
Correct Answer: C — Quick search algorithm
Explanation:
Quick search algorithm is the fastest algorithm in the string matching field, whereas linear search searches for an element in an array sequentially.
