This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Trie”.
1. Trie is also known as _________
a) Digital Tree
b) Treap
c) Binomial Tree
d) 2-3 Tree
View Answer
Explanation: Trie is a very useful data structure which 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
View Answer
Explanation: 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
b) Linked List
c) Balancded BST
d) Trie
View Answer
Explanation: 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 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
View Answer
Explanation: 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++];
View Answer
Explanation: 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 listing of all the words with same prefix
c) Tries are collision free
d) Trie is also known as prefix tree
View Answer
Explanation: Both the hashing and the trie provides 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 same prefix, so it is also called prefix tree.
7. 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
View Answer
Explanation: Dictionaries, phone directories can be implemented efficiently using the trie. Because it trie provides the 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 sting the length?
a) log2n
b) log2m
c) n
d) m
View Answer
Explanation: In the trie, the strings are stored efficiently based on the common prefixes. And trie has maximum fan-out 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 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
View Answer
Explanation: A trie is an ordered tree where (i) the root represents an empty string(“”) (ii) each node other than root is labeled with a character (iii) the children of a nodes are lexicographically ordered (iv) the paths from the leaves to the root yields the strings.
10. Auto complete and spell checkers can be implemented efficiently using the trie.
a) True
b) False
View Answer
Explanation: Trie provides fast searching and storing of the words. And tries stores words in lexicographical order so, trie is the efficient data structure for implementation of spell checkers and auto complete.
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.
If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]
- Practice Design & Analysis of Algorithms MCQ
- Check Computer Science Books
- Check Programming Books
- Apply for Computer Science Internship
- Practice Computer Science MCQs
