Trie Multiple Choice Questions and Answers (MCQs)

Uncategorized

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Trie”.

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

Explanation: Both hashing and the trie allow for linear time searching. Trie, on the other hand, needs more storage space and is collision-free. Trie is also known as a prefix tree because it helps you to locate all strings with the same prefix.

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

Explanation: The trie can be used to effectively enforce dictionaries and phone directories. Since it trie provides a quick linear time search over all the entries.

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

Explanation: The strings are efficiently stored in the trie using common prefixes. If English alphabets are taken into account, trie has a maximum fan-out of 26. As a result, the maximum string length equals the maximum depth.

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

Explanation: A trie is an ordered tree in which the root is an empty string (“”). (ii) Each node other than the root is labelled with a character (iii) each node’s children are lexicographically ordered (iv) the paths from the leaves to the root yield the strings

5. Auto complete and spell checkers can be implemented efficiently using the trie.
A) True
B) False

Explanation: Trie allows for quick word searching and storage. Trie is an effective data structure for implementing spell checkers and auto complete since it stores words in lexicographical order.

6. Trie is also known as _________
A) Digital Tree
B) Treap
C) Binomial Tree
D) 2-3 Tree

Explanation: Trie is a useful data structure that is built on a string’s prefix. The name Trie comes from the fact that it is used to denote the “Retrieval” of data. It’s often referred to as a digital tree.

7. What traversal over trie gives the lexicographical sorting of the set of the strings?
A) postorder
B) preorders
C) inorder
D) level order

Explanation: We store the strings in trie in such a way that each common prefix has its own node. As a result, traversing trie in reverse order yields the lexicographically ordered set of strings.

8. Which of the following is the efficient data structure for searching words in dictionaries?
A) BST
B) Linked List
C) Balancded BST
D) Trie

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

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

Explanation: A suffix tree is a type of trie that contains all of the suffixes in a given text as a key and their place in the text as values. As a result, suffix trees are used to scan complete texts quickly.

10. 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++];

Explanation: The insert() method checks to see if the string is present. We insert the string into the trie if it isn’t already there. We mark the leaf node if it appears as a prefix. As a result, the correct choice is node = node. [index]; 

A trie, also known as a digital tree or a prefix tree, is a type of search tree that is used to locate specific keys within a collection of data. These keys are usually strings, with links between nodes identified by individual characters rather than the entire key. The trie is traversed depth-first in order to access a key (to recover its value, alter it, or delete it), following the links between nodes that represent each character in the key.

Leave a Reply

Your email address will not be published. Required fields are marked *