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.
Answer= TRUE
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.
Answer= Halving rule
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).
Answer= Theta((n-m+1)m)
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).
Answer= Big-Oh(n+m)
Q6. What is the basic principle in Rabin Karp algorithm?.
A. Hashing.
B. Sorting.
C. Augmenting.
D. Dynamic Programming.
Answer= Hashing
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.
Answer= Quick 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.
Answer= Boyer-Moore’s 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).
Answer= O(m+n)
Q11. 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= 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).
Answer= O(n)
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.
Answer= false
Q14. 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= 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).
Answer= 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.
Answer= true
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.
Answer= 6
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.
Answer= GCD of two numbers
Q19. Who invented Euclid’s algorithm?.
A. Sieve.
B. Euclid.
C. Euclid-Sieve.
D. Gabriel lame.
Answer= Euclid