Trie Multiple Choice Questions and Answers (MCQs)

«
»

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

Answer: a
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.
advertisement

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

Answer: c
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

Answer: d
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.
advertisement
advertisement

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

Answer: c
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.

advertisement
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

Answer: a
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];.
advertisement

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

Answer: a
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

Answer: b
Explanation: Dictionaries, phone directories can be implemented efficiently using the trie. Because it trie provides the efficient linear time searching over the entries.
advertisement

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

Answer: d
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

Answer: b
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

Answer: a
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.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter