· 6 years ago · Mar 23, 2020, 01:40 AM
1Elementary ST: Questions
2
3
4Elementary ST: Introduction
51. What is the primary purpose of a symbol table?
6
7The primary purpose of a symbol table is to associate a value with a key.
8
92. What is the client’s expectation for a symbol table?
10
11The expectation is that a client can search for a value associated with a key that they inserted into the symbol table as a key and value pair.
12
133. Type the API (just the header for each method and constructor(s)) for ST for a generic symbol table.
14
15Public class ST<Key, Value>
16
17ST()
18
19void put (Key key, Value val)
20
21Value get (Key key)
22
23void delete(Key key)
24
25boolean contains(Key key)
26
27boolean isEmpty()
28
29int size()
30
31Iterable<Key> keys()
32
334. Do the methods of ST use generics?
34
35The methods of ST us generics by not specifying the type of keys and values being used.
36
375. What happens when a key is a duplicate?
38
39When a key is inserted into the ST and that key is already present, then the new key that was inserted replaces the old key because a ST can’t contain duplicate keys.
40
416. Can a key value be “null”? Why?
42
43No key can have a value of null because the methods in ST such as get are intented to return null if the value is not present and not if there is a value that is equal to null.
44
457. What strategies are used when deleting an association in a ST?
46
47One strategy that is used to delete is the lazy deletion which associates the keys with null so that they can be removed at a later time. The other strategy is eager deletion which removes the key from ST right away.
48
498. What does the method keys() return and what does that mean?
50
51The keys() method returns an Iterable<Key> which can be used to iterate through the set of keys in the ST.
52
539. Is the “equals()” method required?
54
55The equals() method is not required and the built in implementation from the object class or the class of the value type. That is because these values usually hold some sort of data type such as an Integer or Double which already has an equals method built into them.The .equals method for keys is however required.
5610. What component would make a ST an ordered symbol table?
57
58If the keys in a ST are Comparable then you can create an ordered symbol table using the provided api with methods such as compare, min, max, floor, ceiling, and rank.
59
60
6111. What type of ST is the trace about in the attached image?
62
63The ST that is in this trace is a linked list ST implementation. The linked list is not sorted so is therefore an unordered link list ST. It is tracing a sequential search.