A vocabulary (voc for short) is a set of (word, frequency) pairs. Find() is a function that takes a string and a voc as arguments and checks whether the string is a word in the voc. If it is, return the frequency of the word; if not, return -1.

Suppose a voc has n (word, frequency) pairs, and there are many ways to store the voc. When the voc is stored as the following data structures, explain how the Find() function finds the frequency of a given word and what is the worst-case time complexity of the function.

(a) An array

(b) A hash table

(c) A binary search tree (BST)

(d) Please describe another data structure that is appropriate for this purpose. How does it work?