# YOU may join our Telegram for all subjects PDF BOOKS.

https://t.me/+Ccx9McEia7wyODg1

## Suffix Array Multiple choice Questions and Answers (MCQs)

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Which of the following is false?

Suffix array is always sorted | |

Suffix array is used in string matching problems | |

Suffix array is always unsorted | |

Suffix array contains all the suffixes of the given string |

Question 1 Explanation:

Suffix array is always sorted as it contains all the suffixes of a string in sorted order. Suffix arrays are used to solve problems related to string, like string matching problems.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Suffix array of the string "statistics" is .....

2 8 7 4 9 0 5 1 6 3 | |

2 7 4 9 8 0 5 1 6 3 | |

2 4 9 0 5 7 8 1 6 3 | |

2 8 7 0 5 1 6 9 4 3 |

Question 2 Explanation:

The suffix array of the string statistics will be:

2 atistics

8 cs

7 ics

4 istics

9 s

0 statistics

5 stics

1 tatistics

6 tics

3 tistics

In Suffix array, we only store the indices of suffixes. So, correct option is 2 8 7 4 9 0 5 1 6 3.

Question 3 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Suffix array can be created by performing ..... traversal of a suffix tree.

breadth-first | |

level order | |

depth-first | |

either breadth-first or level order |

Question 3 Explanation:

A suffix tree is a trie, which contains all the suffixes of the given string as their keys and positions in the string as their values. So, we can construct a suffix array by performing the depth-first traversal of a suffix tree.

Question 4 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

Suffix array is space efficient and faster than the suffix tree.

True | |

Fasle |

Question 4 Explanation:

Suffix arrays are more space efficient than the suffix trees as they just store the original string and an array of integer. But working with suffix tree is faster than that of the suffix array.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER] |

If comparison based sorting algorithm is used construct the suffix array, then what will be time required to construct the suffix array?

O(nlogn) | |

O(n ^{2}) | |

O(n ^{2}logn) | |

O(n ^{2}) + O(logn) |

Question 5 Explanation:

On average comparison based sorting algorithms require O(nlogn) comparisons. But comparing a suffix takes O(n). So, overall time to construct the suffix array will be O(nlogn) * O(n) = O(n

^{2}logn). There are 5 questions to complete.