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

«
»

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

1. What is the other name for Suffix Tree?
a) Array
b) Stack
c) Priority Queue
d) PAT Tree
View Answer

Answer: d
Explanation: In computer science, a suffix tree is also known as PAT tree or position tree. It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position.
advertisement

2. Which tree allows fast implementation of string operation?
a) Rope Tree
b) Suffix Tree
c) Tango Tree
d) Top Tree
View Answer

Answer: b
Explanation: In computer science, a suffix tree is also known as PAT tree or position tree. It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. It allows fast string operation to be carried out by the user.

3. How much time does construction of suffix tree take?
a) O (log M)
b) O (M!)
c) Exponential to Length of Tree
d) Linear to Length of Tree
View Answer

Answer: d
Explanation: Suffix tree is also known as PAT tree or position tree. It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. It allows fast string operation. Total time taken for construction of suffix tree is linear to the length of the tree.

4. How much space does construction of suffix tree takes?
a) O (log M)
b) Exponential to Length of Tree
c) O (M!)
d) Linear to Length of Tree
View Answer

Answer: d
Explanation: Suffix tree is also known as PAT tree or position tree. It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. It allows fast string operation. Total space taken for construction of a suffix tree is linear to the length of the tree.

5. Which tree provides a linear time solution for substring operation?
a) Rope Tree
b) Suffix Tree
c) Tango Tree
d) Top Tree
View Answer

Answer: b
Explanation: It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. It allows fast string operation to be carried out by the user. The substring operation can be performed by suffix tree in linear time.
advertisement

6. Who proposed the concept of Suffix Tree?
a) Weiner
b) Samuel F. B. Morse
c) Friedrich Clemens Gerke
d) Alexander Morse
View Answer

Answer: a
Explanation: In computer science, a suffix tree is also known as PAT tree or position tree. It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. The concept of Suffix Tree was introduced by Weiner in 1973.

7. Who among the following provided the first online contribution of Suffix Tree?
a) Weiner
b) Samuel F. B. Morse
c) Ukkonen
d) Alexander Morse
View Answer

Answer: c
Explanation: In computer science, a suffix tree is also known as PAT tree or position tree. The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution of Suffix tree which had the time complexity of the fastest algorithm of that period.

8. What is the time complexity of Uttkonen’s algorithm?
a) O (log n!)
b) O (n!)
c) O (n2)
d) O (n log n)
View Answer

Answer: d
Explanation: The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution of Suffix tree which had the time complexity of the fastest algorithm of that period. Ukkonen’s algorithm had a time complexity of n log n.

9. Who among the following provided the first suffix tree contribution for all alphabet?
a) Weiner
b) Farach
c) Ukkonen
d) Alexander Morse
View Answer

Answer: b
Explanation: The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution of Suffix tree which had the time complexity of the fastest algorithm of that period. Farach gave the first suffix tree contribution for all alphabets in 1997.
advertisement

10. Who among the following algorithm is used in external memory and compression of the suffix tree?
a) Weiner’s algorithm
b) Farach’s algorithm
c) Ukkonen’s algorithm
d) Alexander Morse
View Answer

Answer: b
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. Farach’s algorithm is used in external memory and compression.

11. Which statement is correct of suffix tree with a string of length n?
a) The tree has n leaves.
b) The tree has n roots
c) Height of Tree is n
d) Depth of tree is n
View Answer

Answer: a
Explanation: In computer science, a suffix tree is also known as PAT tree or position tree. It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. For a string of length n, the suffix tree has leaves equal to n.

12. Do all the nodes have at least two children in suffix tree.
a) True
b) False
View Answer

Answer: b
Explanation: It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. All the nodes (internal) except for the root nodes have at least two children.

13. Can the two edges that are coming out of a node have labels of string beginning with the same character?
a) True
b) False
View Answer

Answer: b
Explanation: It is a compressed search tree or prefix tree in which keys contain the suffix of text values as the text position. All the nodes (internal) except for the root nodes have at least two children. No two edges that are coming out of a node have labels of string beginning with the same character.
advertisement

14. Which tree allows fast implementation of a set of string operation?
a) Rope Tree
b) Tango Tree
c) Generalized Suffix Tree
d) Top Tree
View Answer

Answer: c
Explanation: In computer science, the generalized suffix is a special suffix tree which contains a set of strings or set of words instead of a single string like suffix tree. Hence Different operation can be performed on a set of strings using a generalized suffix tree.

15. What is a time complexity for checking a string of length n is substring or not?
a) O (log n!)
b) O (n!)
c) O (n2)
d) O (n)
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. 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).

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