Suffix Tree Multiple Choice Questions and Answers (MCQs) – 2

«
»

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

1. What is a time complexity for x pattern occurrence of length n?
a) O (log n!)
b) Ɵ (n!)
c) O (n2)
d) Ɵ (n + x)
View Answer

Answer: d
Explanation: Suffix tree is also known as PAT tree or position tree. It allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for x pattern occurrence of length n is Ɵ (n + x).
advertisement

2. What is a time complexity for finding the longest substring that is common in string S1 and S2 (n1 and n2 are the string lengths of strings s1, s2 respectively)?
a) O (log n!)
b) Ɵ (n!)
c) O (n2+ n1)
d) Ɵ (n1 + n2)
View Answer

Answer: d
Explanation: Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding the longest substring that is common in string S1 and S2 is Ɵ (n1 + n2).

3. What is a time complexity for finding the longest substring that is repeated in a string?
a) O (log n!)
b) Ɵ (n!)
c) O (n2+ n1)
d) Ɵ (n)
View Answer

Answer: d
Explanation: Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding the longest substring that is repeated in a string is Ɵ (n).

4. What is a time complexity for finding frequently occurring of a substring of minimum length in a string?
a) Ɵ (n)
b) Ɵ (n!)
c) O (n2+ n1)
d) O (log n!)
View Answer

Answer: a
Explanation: Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding frequently occurring of a substring of minimum length in a string is Ɵ (n).

5. What is a time complexity for finding the longest prefix that is common between suffix in a string?
a) Ɵ (n)
b) Ɵ (n!)
c) Ɵ (1)
d) O (log n!)
View Answer

Answer: c
Explanation: Suffix Tree allows fast string operation. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding the longest prefix that is common between suffix in a string is Ɵ (1).
advertisement

6. What is a time complexity for finding all the maximal palindrome in a string?
a) Ɵ (n)
b) Ɵ (n!)
c) Ɵ (1)
d) O (log n!)
View Answer

Answer: a
Explanation: Palindrome is a string that is the same when reading forward as well as backward. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding all the maximal palindrome in a string is Ɵ (n).

7. What is a time complexity for finding all the tandem repeats?
a) Ɵ (n)
b) Ɵ (n!)
c) Ɵ (1)
d) O (n log n + z)
View Answer

Answer: a
Explanation: Tandem Repeats are formed in DNA when the nucleotides pattern repeats more than once. To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding all the tandem repeats in a string is O (n log n + z).

8. What is a time complexity for finding the longest palindromic substring in a string by using the generalized suffix tree?
a) Linear Time
b) Exponential Time
c) Logarithmic Time
d) Cubic Time
View Answer

Answer: a
Explanation: Palindrome is a string that is same when reading forward as well as backward. The time complexity for finding the longest palindromic substring in a string by using generalized suffix tree is linear time.

9. Which of the following algorithm of data compression uses a suffix tree?
a) Weiner’s algorithm
b) Farach’s algorithm
c) Lempel – Ziv – Welch’s algorithm
d) Alexander Morse’s algorithm
View Answer

Answer: c
Explanation: The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution of the Suffix tree. Farach gave the first suffix tree contribution for all alphabets in 1997. Lempel – Ziv – Welch’s algorithm of data compression uses a suffix tree.
advertisement

10. Which of the following data clustering algorithm uses suffix tree in search engines?
a) Weiner’s algorithm
b) Farach’s algorithm
c) Lempel – Ziv – Welch’s algorithm
d) Suffix Tree Clustering
View Answer

Answer: d
Explanation: The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution of Suffix. Farach gave the first suffix tree contribution for all alphabets in 1997. Suffix Tree Clustering is a data clustering algorithm that uses suffix tree in search engines.

11. What is a time complexity for finding the total length of all string on all edges of a tree?
a) Ɵ (n)
b) Ɵ (n!)
c) Ɵ (1)
d) O (n2)
View Answer

Answer: d
Explanation: To check if a substring is present in a string of a length of n, the time complexity for such operation is found to be O (n). The time complexity for finding the total length of all string on all edges of a tree is O (n2).

12. Can suffix tree be used in string problems occurring in a text editor.
a) True
b) False
View Answer

Answer: a
Explanation: It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. So, the suffix tree can be used in string problems occurring in a text editor. The time taken to solve the problem is linear to the length of the string.

13. Can suffix tree be used in bioinformatics problems and solutions.
a) True
b) False
View Answer

Answer: a
Explanation: It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. So, a suffix tree is used in bioinformatics problems and solutions like pattern searching in DNA and protein sequences.
advertisement

14. For what size of nodes, the worst case of usage of space in suffix tree seen?
a) n Nodes
b) 2n Nodes
c) 2n nodes
d) n! nodes
View Answer

Answer: c
Explanation: In computer science, the worst case of usage of space in a suffix tree is found to be for a Fibonacci word for a full 2n nodes. The time complexity for usage of space is found to be O (n).

15. What is a time complexity for inserting an alphabet in the tree using hash maps?
a) O (log n!)
b) O (n!)
c) O (n2)
d) O (1)
View Answer

Answer: d
Explanation: Suffix tree is also known as PAT tree or position tree. It allows fast string operation. Total time taken for construction of suffix tree is linear to the length of the tree. The time complexity for inserting an alphabet in the tree using hash maps is constant, O (1).

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
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn