Trie Multiple choice Questions and Answers (MCQs)
Click on any option to know the CORRECT ANSWERS
Which of the following is not true?
Trie requires less storage space than hashing
Trie allows listing of all the words with same prefix
Tries are collision free
Trie is also known as prefix tree
Question 6 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 prefi, x so it is also called prefix tree.
A program to search a contact from phone directory can be implemented efficiently using .....
a balanced BST
a binary tree
Question 7 Explanation:
Dictionaries, phone directories can be implemented efficiently using the trie. Because it trie provides the efficient linear time searching over the entries.
What can be the maximum depth of the trie with n strings and m as the maximum sting the length?
Question 8 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.
Which of the following is true about the trie?
root is letter a
path from root to the leat yields the string
children of nodes are randomly ordered
each node stores the associated keys
Question 9 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.
Auto complete and spell checkers can be implemented efficiently using the trie.
Question 10 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.
There are 10 questions to complete.