ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
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
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
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)
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
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
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)
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
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)
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
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
Quick search algorithm is the fastest algorithm in the string matching field, whereas linear search searches for an element in an array sequentially.
