This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Suffix Array”.
1. What will be the suffix array of the string “engineering”?
A) 2 3 8 4 9 1 7 5 0 6 10
B) 5 0 6 1 4 9 1 7 0 2 3 8
C) 5 0 6 10 2 4 9 1 7 3 8
D) 5 0 6 10 2 3 8 4 9 1 7
Explanation: Correct choice is : 5 0 6 10 2 3 8 4 9 1 7.
Because the suffix array formed will be: 5 eering 0 engineering 6 ering 10 g 2 gineering 3 ineering 8 ing 4 neering 9 ng 1 ngineering 7 ring.
2. LCP array and ______ is used to construct suffix tree.
A) Hash tree
B) Hash trie
C) Suffix array
D) Balanced tree
Explanation: An LCP array and a suffix array may be used to make a suffix tree. We can build the suffix tree in linear time, i.e. in O(n) time, if we have a string of length (n + 1) and its suffix and LCP arrays.
3. What is the time required to locate the occurrences of a pattern P of length m in a string of length n using suffix array?
Explanation: To find the occurrences of a pattern in a string, suffix arrays are used. Since a pattern of length m requires m characters to compare, we can find occurrences of a pattern in a string of length n in O(mlogn) time using a suffix list.
4. Suffix array can be created in O(nlogn) time.
Explanation: Using sorting algorithms, the suffix array can be built in O(n2logn) time, but using prefix doubling, the suffix array can be built in O(nlogn) time.
5. Which of the following is/are advantages suffix array one suffix tree?
I. Lesser space requirement
II. Improved cache locality
III. Easy construction in linear time
A) Only I
B) All I, II and III
C) Only I and III
D) Only II and III
Explanation: The suffix list has the following advantages over the suffix tree: Simple algorithms to build suffix arrays in linear time I Less space demand (ii) Improved cache locality (iii) Simple algorithms to construct suffix arrays in linear time
6. Which of the following is false?
A) Suffix array is always sorted
B) Suffix array is used in string matching problems
C) Suffix array is always unsorted
D) Suffix array contains all the suffixes of the given string
Explanation: The suffix array is always sorted since it includes all of a string’s suffixes in sorted order. Suffix arrays are used to solve string-related problems, such as string matching.
7. Suffix array of the string “statistics” is ____________
A) 2 8 7 4 9 0 5 1 6 3
B) 2 7 4 9 8 0 5 1 6 3
C) 2 4 9 0 5 7 8 1 6 3
D) 2 8 7 0 5 1 6 9 4 3
Explanation: The suffix array of the string statistics will be:
In Suffix array, we only store the indices of suffixes. So, correct option is 2 8 7 4 9 0 5 1 6 3.
8. Suffix array can be created by performing __________ traversal of a suffix tree.
B) level order
D) either breadth-first or level order
Explanation: A suffix tree is a trie that has all of the suffixes of a given string as keys and their locations in the string as values. As a result, we can construct a suffix array by traversing a suffix tree depth-first.
9. Suffix array is space efficient and faster than the suffix tree.
Explanation: Suffix arrays take up less space than suffix trees since they only store the initial string and an integer array. Working with a suffix tree, on the other hand, is quicker than working with a suffix list.
10. If comparison based sorting algorithm is used construct the suffix array, then what will be time required to construct the suffix array?
D) O(n2) + O(logn)
Explanation: On average, sorting algorithms based on comparisons include O(nlogn) comparisons. However, comparing suffixes takes O time (n). As a result, the total time to construct the suffix array will be O(nlogn) * O(n) = O. (n2logn).
A suffix array is a sorted array of all a string’s suffixes. It’s a data structure that’s used in full text indexes, data compression algorithms, and the area of bibliometrics, among other things. Manber & Myers (1990) proposed suffix arrays as a simple, space-saving alternative to suffix trees. A string’s suffix array can be used as an index to quickly find any instance of the substring pattern displaystyle PP within the string displaystyle SS. Finding every instance of the pattern is the same as looking for every suffix that starts with the substring.