Trie - Data Structure Quiz

Which of the following statements are true about Trie Data structure?

P1: There is one root node in each Trie.

P2: Each path from the root to any node represents a word or string.

P3: We can not do prefix search (or auto-complete) with Trie.

P4: There is no use of Hash functions in a Trie data structure

• P1 & P3 Only

• P2 & P3 Only

• P1 Only

• P1, P2 and P4

A program to search a contact from phone directory can be implemented efficiently using a ______

• BST

• Trie

• Balanced BST

• Binary tree

What can be the maximum depth of the Trie with n strings and m as the maximum string length?

• log2n

• log2m

• n

• m

Which of the following is true about the Trie?

• Root is letter a

• Path from root to the leaf yields the string

• Children of nodes are randomly ordered

• Each node stores the associated keys

Given the following C++ code snippet for inserting a string into a Trie, find the missing line:
Which of the following lines should replace ________________________ to correctly insert the string into the Trie?

• node = node->children[index];

• node = node->children[str[i + 1]];

• node = node->children[index++];

• node = node->children[index + 1];

Which of the following is the efficient data structure for searching words in dictionaries?

• BST

• Linked List

• Balanced BST

• Trie

Trie is also known as _________

• Digital Tree

• Treap

• Binomial Tree

• 2-3 Tree

Answer explanation

It stores characters digitally (like bits) from the root to the leaf, hence the name Digital Tree.

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

• 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

Given a Trie with strings "apple", "appetizer", and "apply", what is the maximum number of nodes in the Trie?

• 10

• 13

• 12

• 14

Given a Trie data structure, what would be the result of deleting a string from the Trie when it is a prefix of another string?

• The string is removed, but the prefix remains.

• The entire Trie is deleted.

• The prefix and all other strings are removed.

• The operation fails and the string is not deleted.