# Tries and Suffix Tree MCQs

Q1. 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.

Q2. Which of the following is not true?.
A. Trie requires less storage space than hashing.
B. Trie allows listing of all the words with same prefix.
C. Tries are collision free.
D. Trie is also known as prefix tree.
Answer= Trie requires less storage space than hashing

Q3. A program to search a contact from phone directory can be implemented efficiently using ______.
A. a BST.
B. a trie.
C. a balanced BST.
D. a binary tree.

Q4. What can be the maximum depth of the trie with n strings and m as the maximum sting the length?.
A. log2n.
B. log2m.
C. n.
D. m.

Q5. Which of the following is true about the trie?.
A. root is letter a.
B. path from root to the leat yields the string.
C. children of nodes are randomly ordered.
D. each node stores the associated keys.
Answer= path from root to the leat yields the string

Q6. Auto complete and spell checkers can be implemented efficiently using the trie..
A. TRUE.
B. FALSE.
C.  Nothing Can be said.
D.  None of the mentioned.

Q7. What is the other name for Suffix Tree?.
A. Array.
B. Stack.
C. Priority Queue
D. PAT Tree.

Q8. Which tree allows fast implementation of string operation?.
A. Rope Tree.
B. Suffix Tree.
C. Tango Tree.
D. Top Tree.

Q9. 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.
Answer= Linear to Length of Tree

Q10. 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.
Answer= Linear to Length of Tree

Q11. Which tree provides a linear time solution for substring operation?.
A. Rope Tree.
B. Suffix Tree.
C. Tango Tree.
D. Top Tree.

Q12. Who proposed the concept of Suffix Tree?.
A. Weiner.
B. Samuel F. B. Morse.
C. Friedrich Clemens Gerke.
D. Alexander Morse.

Q13. Who among the following provided the first online contribution of Suffix Tree?.
A. Weiner.
B. Samuel F. B. Morse.
C. Ukkonen.
D. Alexander Morse.

Q14. What is the time complexity of Uttkonen's algorithm?.
A. O (log n!).
B. O (n!).
C. O (n2).
D. O (n log n).

Q15. Who among the following provided the first suffix tree contribution for all alphabet?.
A. Weiner.
B. Farach.
C. Ukkonen.
D. Alexander Morse.

Q16. 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.

Q17. 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.
Answer= The tree has n leaves.

Q18. Do all the nodes have at least two children in suffix tree..
A. TRUE.
B. FALSE.
C.  Nothing can be said.
D.  None of the mentioned.

Q19. Can the two edges that are coming out of a node have labels of string beginning with the same character?.
A. TRUE.
B. FALSE.
C.  Nothing can be said.
D.  None of the mentioned.

Q20. Which tree allows fast implementation of a set of string operation?.
A. Rope Tree.
B. Tango Tree.
C. Generalized Suffix Tree.
D. Top Tree.

Q21. 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).

Q22. What is a time complexity for x pattern occurrence of length n?.
A. O (log n!).
B. Theta (n!).
C. O (n2).
D. Theta (n + x).

Q23. What is a time complexity for finding the longest substring that is common in string S1 and S2?.
A. O (log n!).
B. Theta (n!).
C. O (n2+ n1).
D. Theta (n1 + n2).

Q24. What is a time complexity for finding the longest substring that is repeated in a string?.
A. O (log n!).
B. Theta (n!).
C. O (n2+ n1).
D. Theta (n).

Q25. What is a time complexity for finding frequently occurring of a substring of minimum length in a string?.
A. Theta (n).
B. Theta (n!).
C. O (n2+ n1).
D. O (log n!).

Q26. What is a time complexity for finding the longest prefix that is common between suffix in a string?.
A. Theta (n).
B. Theta (n!).
C. Theta (1).
D. O (log n!).

Q27. What is a time complexity for finding all the maximal palindrome in a string?.
A. Theta (n).
B. Theta (n!).
C. Theta (1).
D. O (log n!).

Q28. What is a time complexity for finding all the tandem repeats?.
A. Theta (n).
B. Theta (n!).
C. Theta (1).
D. O (n log n + z).

Q29. 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.

Q30. 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.
Answer= Lempel - Ziv - Welch's algorithm

Q31. 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.

Q32. Can suffix tree be used in string problems occurring in a text editor..
A. TRUE.
B. FALSE.
C.  Nothing Can be said.
D.  None of the mentioned.

Q33. Can suffix tree be used in bioinformatics problems and solutions..
A. TRUE.
B. FALSE.
C.  Nothing Can be said.
D.  None of the mentioned.

Q34. 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.

Q35. 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).

Q36. What is a hash table?.
A. A structure that maps values to keys.
B. A structure that maps keys to values.
C. A structure used for storage.
D. A structure used to implement stack and queue.
Answer= A structure that maps keys to values

Q37. If several elements are competing for the same bucket in the hash table, what is it called?.
A. Diffusion.
B. Replication.
C. Collision.
D. None of the mentioned.