String Matching MCQ question and answer with solution | Data Structure MCQs Page-7 section-1

61.
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 & Solution Discuss in Board Save for Later

62.

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

Answer & Solution Discuss in Board Save for Later

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

Answer & Solution Discuss in Board Save for Later

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

A. true

B. false

Answer & Solution Discuss in Board Save for Later

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

Answer & Solution Discuss in Board Save for Later

66.
What is a Rabin and Karp Algorithm?

A. String Matching Algorithm

B. Shortest Path Algorithm

C. Minimum spanning tree Algorithm

D. Approximation Algorithm

Answer & Solution Discuss in Board Save for Later

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

Answer & Solution Discuss in Board Save for Later

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

A. O(n)

B. O(log n)

C. O(m+n)

D. O(mn)

Answer & Solution Discuss in Board Save for Later

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

Answer & Solution Discuss in Board Save for Later

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

A. true

B. false

Answer & Solution Discuss in Board Save for Later

String Matching MCQ question and answer with solution | Data Structure MCQs

61. Who created the Rabin Karp Algorithm?

Answer & Solution

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

Answer & Solution

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

Answer & Solution

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

Answer & Solution

65. What character shift tables does Boyer-Moore's search algorithm use?

Answer & Solution

66. What is a Rabin and Karp Algorithm?

Answer & Solution

67. Given input string = "ABCDABCATRYCARCABCSRT" and pattern string = "CAT". Find the first index of the pattern match using quick search algorithm.

Answer & Solution

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

Answer & Solution

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

Answer & Solution

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

Answer & Solution

61.
Who created the Rabin Karp Algorithm?

62.
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`

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

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

65.
What character shift tables does Boyer-Moore's search algorithm use?

66.
What is a Rabin and Karp Algorithm?

67.
Given input string = "ABCDABCATRYCARCABCSRT" and pattern string = "CAT". Find the first index of the pattern match using quick search algorithm.

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

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

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