Engineering Questions with Answers - Multiple Choice Questions

# Suffix Tree Multiple Choice MCQ – 1

1 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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.

6 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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

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 - Question

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)