Quick Search Algorithm Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Matching Multiple Choice Questions & Answers (MCQs) focuses on “Quick Search Algorithm”.

1. Which of the following is the fastest algorithm in string matching field?
a) Boyer-Moore’s algorithm
b) String matching algorithm
c) Quick search algorithm
d) Linear search algorithm
View Answer

Answer: c
Explanation: Quick search algorithm is the fastest algorithm in string matching field whereas Linear search algorithm searches for an element in an array of elements.

2. Which of the following algorithms formed the basis for the Quick search algorithm?
a) Boyer-Moore’s algorithm
b) Parallel string matching algorithm
c) Binary Search algorithm
d) Linear Search algorithm
View Answer

Answer: a
Explanation: Quick search algorithm was originally formed to overcome the drawbacks of Boyer-Moore’s algorithm and also for increased speed and efficiency.

3. What is the time complexity of the Quick search algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)
View Answer

Answer: c
Explanation: The time complexity of the Quick search algorithm was found to be O(m+n) and is proved to be faster than Boyer-Moore’s algorithm.
advertisement
advertisement

4. What character shift tables does quick search algorithm use?
a) good-character shift tables
b) bad-character shift tables
c) next-character shift tables
d) both good and bad character shift tables
View Answer

Answer: b
Explanation: Quick search algorithm uses only bad character shift tables and it is one of the reasons for its increased speed than Boyer-Moore’s algorithm.

5. What is the space complexity of quick search algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)
View Answer

Answer: a
Explanation: The space complexity of quick search algorithm is mathematically found to be O(n) where n represents the input size.
Note: Join free Sanfoundry classes at Telegram or Youtube

6. Quick search algorithm starts searching from the right most character to the left.
a) true
b) false
View Answer

Answer: b
Explanation: Quick search algorithm starts searching from the left most character to the right and it uses only bad character shift tables.

7. What character shift tables does Boyer-Moore’s search algorithm use?
a) good-character shift tables
b) bad-character shift tables
c) next-character shift tables
d) both good and bad character shift tables
View Answer

Answer: d
Explanation: Boyer-Moore’s search algorithm uses both good and bad character shift tables whereas quick search algorithm uses only bad character shift tables.
advertisement

8. What is the worst case running time in searching phase of Boyer-Moore’s algorithm?
a) O(n)
b) O(log n)
c) O(m+n)
d) O(mn)
View Answer

Answer: d
Explanation: If the pattern occurs in the text, the worst case running time of Boyer-Moore’s algorithm is found to be O(mn).

9. The searching phase in quick search algorithm has good practical behaviour.
a) true
b) false
View Answer

Answer: a
Explanation: During the searching phase, the comparison between pattern and text characters can be done in any order. It has a quadratic worst case behaviour and good practical behaviour.
advertisement

10. Given input string = “ABCDABCATRYCARCABCSRT” and pattern string = “CAT”. Find the first index of the pattern match using quick search algorithm.
a) 2
b) 6
c) 11
d) 14
View Answer

Answer: b
Explanation: By using quick search algorithm, the given input text string is preprocessed and starts its search from the left most character and finds the first occurrence of the pattern at index=2.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.