1. Semi generic code is relatively free from implementation considerations, such as what data type will be used in an actual list. Some manual effort is still needed to re-code the module to take a new data type, but this may be as little as one line near the beginning if the design is well done.
2. Before implementing a list ADT, one must decide what data is to be listed, whether the list is a generic one (re-usable), whether the list is to be unidirectional or bidirectional, sorted or unsorted, and how many pointers to data in the list will be kept. There are some lesser issues such as how much data will be kept on the list (number of items, for instance).
3. A queue is a first-in-first-out structure and a stack is a last-in-first-out structure.
4. A lookup table or, for short, a table is a finite set of ordered pairs {(x, f(x))}, that is, it is a function on a finite domain (the first column) to some range (the second column).
5. How one implements a data structure is independent from the abstraction itself. The table could in some systems be implemented as an array, provided different array components could be of different types.
6. A tree is a structure in which all nodes may have more than one successor and all nodes but one (the root) have one predecessor.
7. In a binary tree, the maximum number of successors of a node is two.
8. A root has no predecessor.
9. leaves have no successors.
10. Interior nodes have a predecessor and one or more successors. To put it another way, they are the root of a subtree, but not a root of the entire tree.
11. A node in a binary tree has degree zero, one, or two.
12. A full binary tree with eight levels has 255 occupied nodes.
13. The mathematical sense of "full" simply means that all nodes on each used level are occupied. The memory sense is that there is no more place to put another node.
14. Searching a linked list requires examination of up to all n items, whereas, searching a binary tree requires at most nlog2 (n) comparisons.
15. Even with two pointers, a list is still linear, and searching is proportional to the number of items.
16. The letters ISAM mean Indexed Sequential Access Method.
17. Hashing refers to mapping data items into an index space. The function is not one-to-one (or there would be no point) so several items in the data space could have the same index value.
18. Tree traversal can be pre-order (root-left-right); in-order (left-root-right); or post-order (left-right-root).
19. Assuming that one works left to right as with a binary tree, the root of the ternary node could be processed before any one of the three children, or after the last, a total of four possibilities.
20-21. Try it and see.
22-25. Left as an exercise.
Problems
Note: At this stage, students should not need any problem solutions.