Exam 3 Topic List for Fall 2000, Sections 0101-0102

Pointers

As stated in class, you will be tested again on this topic. Study the pointer questions from Exam 2 and review the following.

• For a given code segment, you should be able to draw a picture that corresponds to it.
• For a given picture, you should be able to write a segment of code that would "generate" that picture.
• You should understand how to allocate and deallocate memory in C++ using new, new [], delete, and delete [].

Trees

• Terminology: node, path, root, internal node, leaf, subtree, parent, child, sibling, depth of a node, depth of a tree
• 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 common to a general binary tree 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. This includes constructors, copy constructors, destructors, and overloaded = operators. Syntax counts!

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 hash function, collision, linear probing, clustering, double hashing, chained hashing.
• Know why collisions occur and what can be done to solve this problem.
• Know why clustering can occur and what can be done to minimize 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.

Advanced Topic - Finite State Machines

As stated in class, there will be one question (maximum of 10 points) dealing with finite state machines. In particular, review the following.

• Know what the following are: symbol, input alphabet, output alphabet, input string, state, arc, transition, null transition, set of possible states (Q), initial state, set of final states (F), acceptance, rejection, jamming (a cause of rejection).
• Given an FSM, FSR, or FSG and an input string (FSM and FSR only), be able to write down the notation for its input alphabet, output alphabet, set of possible states, initial state, set of possible final states, and the output string generated (FSM and FSG only). Also be able to describe its behavior (what it does).
• Given an English description of the behavior of an FSR or FSG, be able to draw the corresponding FSR or FSG.