Elementary Symbol Table quiz



What value is associated with the key "Hello" after executing the following code?
    ST<String, Integer> st = new ST<String, Integer>();
    st.put("Hello", 12);
    st.put("World", 21);
    st.put("Hello", 49);

12
49
Both 12 and 49
Either 12 or 49, depending on the implementation


Suppose we implement a symbol table with an ordered array (and not a binary search tree). What is the maximum number of array accesses needed to search for a key in such a symbol table?

constant
logarithmic
linear
linearithmic


Now consider the problem of finding the rank of a key. How many array accesses does this take for an ordered array based symbol table?

constant
logarithmic
linear
linearithmic


Suppose we instead implement our symbol table with a binary search tree. What is the maximum number of compares needed to search for a key in such a symbol table?

constant
logarithmic
linear
linearithmic


Suppose we build a binary search tree by inserting the keys in a random order. What is the expected number of compares needed to find the rank of a key?

constant
logarithmic
linear
linearithmic