# String Matching in Data Structure and Algorithms MCQs

Q1. Rabin Karp Algorithm makes use of elementary number theoretic notions..

A. TRUE.

B. FALSE.

C. Nothing Can be Said.

D. None of the mentioned.

Q2. What is the basic formula applied in Rabin Karp Algorithm to get the computation time as Theta(m)?.

A.  Halving rule.

B.  Horner’s rule.

C.  Summation lemma.

D.  Cancellation lemma.

Q3. What is the worst case running time of Rabin Karp Algorithm?.

A.  Theta(n).

B.  Theta(n-m).

C.  Theta((n-m+1)m).

D.  Theta(nlogm).

Q4. What happens when the modulo value(q) is taken large?.

A.  Complexity increases.

B.  Spurious hits occur frequently.

C.  Cost of extra checking is low.

D.  Matching time increases.

Answer=  Cost of extra checking is low

Q5. If the expected number of valid shifts is small and modulus is larger than the length of pattern what is the matching time of Rabin Karp Algorithm?.

A.  Theta(m).

B.  Big-Oh(n+m).

C.  Theta(n-m).

D.  Big-Oh(n).

Q6. What is the basic principle in Rabin Karp algorithm?.

A.  Hashing.

B.  Sorting.

C.  Augmenting.

D.  Dynamic Programming.

Q7. Who created the Rabin Karp Algorithm?.

A.  Joseph Rabin and Michael Karp.

B.  Michael Rabin and Joseph Karp.

C.  Richard Karp and Michael Rabin.

D.  Michael Karp and Richard Rabin.

Answer=  Richard Karp and Michael Rabin

Q8. 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.

Q9. 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.

Q10. What is the time complexity of the Quick search algorithm?.

A.  O(n).

B.  O(log n).

C.  O(m+n).

D.  O(mn).

Q11. What character shift tables does quick search algorithm use?.

A.  good-character shift tables.

C.  next-character shift tables.

D.  both good and bad character shift tables.

Q12. What is the space complexity of quick search algorithm?.

A.  O(n).

B.  O(log n).

C.  O(m+n).

D.  O(mn).

Q13. Quick search algorithm starts searching from the right most character to the left..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q14. What character shift tables does Boyer-Moore’s search algorithm use?.

A.  good-character shift tables.

C.  next-character shift tables.

D.  both good and bad character shift tables.

Q15. What is the running time of Boyer-Moore’s algorithm?.

A.  O(n).

B.  O(log n).

C.  O(m+n).

D.  O(mn).

Q16. The searching phase in quick search algorithm has good practical behaviour..

A.  true.

B.  false.

C. Nothing Can be Said.

D. None of the mentioned.

Q17. 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.

Q18. Euclid’s algorithm is used for finding ___________.

A.  GCD of two numbers.

B.  GCD of more than three numbers.

C.  LCM of two numbers.

D.  LCM of more than two numbers.