Exam 3 Topic List for Fall 2000, Sections 020x

Trees

• Terminology: node, path, root, internal node, leaf, subtree, parent, child, sibling, depth of a node, depth of a tree, height of a node, height of a tree, branch factor
• Understand the difference between a general tree, a binary tree, and a binary search tree. Why would one choose to use one over the other?
• Be able to write the pseudocode to:
  • find an item in a BST,
  • insert an item into a BST,
  • delete an item from a BST,
  • and perform a preorder, inorder, or postorder traversal of a general binary tree.
• Know the operations for the BST ADT. Know what the inputs to and outputs from each operation would be.
• Be able to write class definitions for a binary tree, a BST, and a tree node given a specification in English.

Hash Tables and Hashing

• Understand why one would use a hash table for the storage and retrievel of data.
• Understand what the following are: hash function, key, division method, multi-part hash function, collision, probing, separate chaining, open addressing.
• Know why collisions occur and what can be done to solve this problem.
• Given the description of a set of data (e.g., student records), be able to pick an appropriate key and an appropriate hash function based on this key. You should be able to produce a hash function for an arbitrary key type (some creativity required).