Rabin-Karp Algorithm Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Rabin-Karp Algorithm”.

1. What is a Rabin and Karp Algorithm?
a) String Matching Algorithm
b) Shortest Path Algorithm
c) Minimum spanning tree Algorithm
d) Approximation Algorithm
View Answer

2. What is the pre-processing time of Rabin and Karp Algorithm?
a) Theta(m²)
b) Theta(mlogn)
c) Theta(m)
d) Big-Oh(n)
View Answer

3. Rabin Karp Algorithm makes use of elementary number theoretic notions.
a) True
b) False
View Answer

4. 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
View Answer

5. 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)
View Answer

6. Rabin- Karp algorithm can be used for discovering plagiarism in a sentence.
a) True
b) False
View Answer

7. If n is the length of text(T) and m is the length of the pattern(P) identify the correct pre-processing algorithm. (where q is a suitable modulus to reduce the complexity)
p=0; t0=0;
a)

for i=1 to n
do t0=(dt0 + P[i])mod q 
p=(dp+T[i])mod q

b)

for i=1 to n
do p=(dp + P[i])mod q 
t0=(dt0+T[i])mod q

c)

for i=1 to m
do t0=(dp + P[i])mod q 
p=(dt0+T[i])mod q

d)

for i=1 to m
do p=(dp + P[i])mod q 
t0=(dt0+T[i])mod q

8. If n is the length of text(T) and m is the length of the pattern(P) identify the correct matching algorithm.
a)

for s=0 to n
		do if p=t0	
			then if P[1..m]=T[s+1..s+m]
				then print “Pattern occurs with shift” s

b)

for s=0 to n-m
		do if p=ts	
			then if P[1..m]=T[s+1..s+m]
				then print “Pattern occurs with shift” s

c)

 for s=0 to m
		do if p=ts	
			then if P[1..m]=T[s+1..s+m]
				then print “Pattern occurs with shift” s

d)

 for s=0 to n-m
		do if p!=ts	
			then if P[1..m]=T[s+1..s+m]
				then print “Pattern occurs with shift” s

9. 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
View Answer

10. Given a pattern of length-5 window, find the suitable modulo value.

					4 3 2 5 0

a) 13
b) 14
c) 12
d) 11
View Answer

11. Given a pattern of length- 5 window, find the valid match in the given text.

Pattern: 2 1 9 3 6 
Modulus: 21
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Text:   9 2 7 2 1 8 3 0 5 7 1   2   1   2   1   9   3   6   2   3   9  7

a) 11-16
b) 3-8
c) 13-18
d) 15-20
View Answer

12. Given a pattern of length- 5 window, find the spurious hit in the given text string.

Pattern: 3 1 4 1 5 
Modulus: 13
Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Text:   2 3 5 9 0 2 3 1 4 1 5   2   6   7   3   9   9   2   1   3   9

a) 6-10
b) 12-16
c) 3-7
d) 13-17
View Answer

13. 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)
View Answer

14. What is the basic principle in Rabin Karp algorithm?
a) Hashing
b) Sorting
c) Augmenting
d) Dynamic Programming
View Answer

15. 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
View Answer

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]