Suffix Array Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Suffix Array”.

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

Answer: c
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.

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

Answer: a
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.

3. Suffix array can be created by performing __________ traversal of a suffix tree.
a) breadth-first
b) level order
c) depth-first
d) either breadth-first or level order
View Answer

Answer: c
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.
advertisement
advertisement

4. Suffix array is space efficient than the suffix tree.
a) True
b) Fasle
View Answer

Answer: b
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.

5. If comparison based sorting algorithm is used construct the suffix array, then what will be time required to construct the suffix array?
a) O(nlogn)
b) O(n2)
c) O(n2logn)
d) O(n2) + O(logn)
View Answer

Answer: c
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(n2logn).
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

Answer: d
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.

7. LCP array and ______ is used to construct suffix tree.
a) Hash tree
b) Hash trie
c) Suffix array
d) Balanced tree
View Answer

Answer: c
Explanation: Suffix tree can be created using an LCP array and a suffix array. If we are given a string of length (n + 1) and its suffix array and LCP array, we can construct the suffix tree in linear time i.e in O(n) time.
advertisement

8. 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?
a) O(nm)
b) O(n2)
c) O(mnlogn)
d) O(mlogn)
View Answer

Answer: d
Explanation: Suffix arrays are used to find the occurrences of a pattern in a string. Pattern of length m will require m characters to compare, so using suffix array we can find occurrences of a pattern in the string of length n in O(mlogn) time.

9. Suffix array can be created in O(nlogn) time.
a) True
b) False
View Answer

Answer: a
Explanation: Suffix array can be constructed in O(n2logn) time using sorting algorithms but it is possible to build the suffix array in O(nlogn) time using prefix doubling.
advertisement

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

Answer: b
Explanation: Advantages of the suffix array over suffix tree are : (i) Lesser space requirement (ii) Improved cache locality and (iii) Simple algorithms to construct suffix arrays in linear time.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.