Suffix Tree MCQ - Sanfoundry

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

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.

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.

Note: Join free Sanfoundry classes at Telegram or Youtube

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 (n²)
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.

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

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.

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 (n²)
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).

More MCQs on Suffix Tree: