# Trie Data Structure MCQ

1. Trie is also known as _________

a) Digital Tree
b) Treap
c) Binomial Tree
d) 2-3 Tree

Trie is a very useful data structure that is based on the prefix of a string. Trie is used to represent the “Retrieval” of data and thus the name Trie. And it is also known as a digital tree.

2. What traversal over trie gives the lexicographical sorting of the set of the strings?

a) postorder
b) preorders
c) inorder
d) level order

In trie, we store the strings in such a way that there is one node for every common prefix. Therefore the inorder traversal over trie gives the lexicographically sorted set of strings.

3. Which of the following is the efficient data structure for searching words in dictionaries?

a) BST
c) Balanced BST
d) Trie

In a BST, as well as in a balanced BST searching takes time in order of mlogn, where m is the maximum string length and n is the number of strings in the tree. But searching in trie will take O(m) time to search the key.

4. Which of the following special type of trie is used for fast searching of the full texts?

a) Ctrie
b) Hash tree
c) Suffix tree
d) T tree

The suffix tree, a special type of trie, contains all the suffixes of the given text at the key and their position in the text as their values. So, suffix trees are used for fast searching of the full texts.

5. Following code snippet is the function to insert a string in a trie. Find the missing line.

private void insert(String str)
{
TrieNode node = root;
for (int i = 0; i < length; i++)
{
int index = key.charAt(i) - 'a';
if (node.children[index] == null)
node.children[index] = new TrieNode();

________________________
}

node.isEndOfWord = true;
}

a) node = node.children[index];
b) node = node.children[str.charAt(i + 1)];
c) node = node.children[index++];
d) node = node.children[index++];

In the insert() method we search if the string is present or not. If the string is not present, then we insert the string into the trie. If it is present as the prefix, we mark the leaf node. So, correct option is node = node.children[index];.

6. Which of the following is not true?

a) Trie requires less storage space than hashing
b) Trie allows the listing of all the words with the same prefix
c) Tries are collision-free
d) Trie is also known as a prefix tree

Both the hashing and the trie provide searching in the linear time. But trie requires extra space for storage and it is collision-free. And trie allows finding all the strings with the same prefix, so it is also called a prefix tree.

7. A program to search a contact from a phone directory can be implemented efficiently using ______

a) a BST
b) a trie
c) a balanced BST
d) a binary tree

Dictionaries and phone directories can be implemented efficiently using the trie. Because it trie provides efficient linear time searching over the entries.

8. What can be the maximum depth of the trie with n strings and m as the maximum string length?

a) log2n
b) log2m
c) n
d) m

In the trie, the strings are stored efficiently based on the common prefixes. And trie has a maximum fan-out of 26 if English alphabets are considered. Owing to this, the maximum depth is equal to the maximum string length.

9. Which of the following is true about the trie?

a) root is the letter a
b) path from the root to the least yields the string
c) children of nodes are randomly ordered
d) each node stores the associated keys

A trie is an ordered tree where

(i) the root represents an empty string(“”)

(ii) each node other than the root is labeled with a character

(iii) the children of nodes are lexicographically ordered (iv) the paths from the leaves to the root yield the strings.

10. Autocomplete and spell checkers can be implemented efficiently using the trie.

a) True
b) False

Trie provides fast searching and storing of the words. And tries stores words in lexicographical order so, a trie is the efficient data structure for the implementation of spell checkers and auto-complete.

1. What is the other name for Suffix Tree?

a) Array
b) Stack
c) Priority Queue
d) PAT Tree

In computer science, a suffix tree is also known as a 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

In computer science, a suffix tree is also known as a 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 the construction of the suffix tree take?

a) O (log M)
b) O (M!)
c) Exponential Length of Tree
d) Linear to Length of Tree

A suffix tree is also known as a 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. The total time taken for the construction of the suffix tree is linear to the length of the tree.

4. How much space does the construction of a suffix tree takes?

a) O (log M)
b) Exponential to Length of Tree
c) O (M!)
d) Linear to Length of Tree

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. The total space taken for the 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

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 the suffix tree in linear time.

6. Who proposed the concept of the Suffix Tree?

a) Weiner
b) Samuel F. B. Morse
c) Friedrich Clemens Gerke
d) Alexander Morse

In computer science, a suffix tree is also known as a 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 the 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

In computer science, a suffix tree is also known as a PAT tree or position tree. The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution of the 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)

The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution of the 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

The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution of the 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

The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution to 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

In computer science, a suffix tree is also known as a 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 the suffix tree.

a) True
b) False

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

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 operations?

a) Rope Tree
b) Tango Tree
c) Generalized Suffix Tree
d) Top Tree

In computer science, the generalized suffix is a special suffix tree that contains a set of strings or a set of words instead of a single string-like suffix tree. Hence Different operations can be performed on a set of strings using a generalized suffix tree.

15. What is the 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)

A suffix tree is also known as PAT tree or position tree. It allows fast string operation. The total time taken for the construction of the 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).

1. What is the time complexity for x pattern occurrence of length n?

a) O(log n!)
b) Ɵ(n!)
c) O(n2)
d) Ɵ(n + x)

A suffix tree is also known as a 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).

2. What is the time complexity for finding the longest substring that is common in strings S1 and S2 (n1 and n2 are the string lengths of strings s1, and s2 respectively)?

a) O (log n!)
b) Ɵ (n!)
c) O (n2+ n1)
d) Ɵ (n1 + n2)

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 strings S1 and S2 is Ɵ (n1 + n2).

3. What is the 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)

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 the time complexity for finding frequently occurring substring of minimum length in a string?

a) Ɵ (n)
b) Ɵ (n!)
c) O (n2+ n1)
d) O (log n!)

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 substring of minimum length in a string is Ɵ (n).

5. What is the time complexity for finding the longest prefix that is common between suffixes in a string?

a) Ɵ (n)
b) Ɵ (n!)
c) Ɵ (1)
d) O (log n!)

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 suffixes in a string is Ɵ (1).

6. What is the time complexity for finding all the maximal palindrome in a string?

a) Ɵ (n)
b) Ɵ (n!)
c) Ɵ (1)
d) O (log n!)

A 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 the time complexity for finding all the tandem repeats?

a) Ɵ (n)
b) Ɵ (n!)
c) Ɵ (1)
d) O (n log n + z)

Tandem Repeats are formed in DNA when the nucleotide 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 the 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

A palindrome is a string that is the same when reading forward as well as backward. The time complexity for finding the longest palindromic substring in a string by using a generalized suffix tree in 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

The concept of Suffix Tree was introduced by Weiner in 1973. Ukkonen provided the first online contribution to 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.

10. Which of the following data clustering algorithm uses suffix trees in search engines?

a) Weiner’s algorithm
b) Farach’s algorithm
c) Lempel – Ziv – Welch’s algorithm
d) Suffix Tree Clustering

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 trees in search engines.

11. What is the time complexity for finding the total length of all strings on all edges of a tree?

a) Ɵ (n)
b) Ɵ (n!)
c) Ɵ (1)
d) O (n2)

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

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 the suffix tree be used in bioinformatics problems and solutions.

a) True
b) False

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.

14. For what size of nodes, is the worst case of usage of space in suffix tree seen?

a) n Nodes
b) 2n Nodes
c) 2n nodes
d) n! nodes

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 the usage of space is found to be O (n).

15. What is the 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)