CIS 22

Exam II Review


This is a list of topics and concepts intended to help you study for the exam.  It is intended to be reasonably complete, but there could be material covered on the exam that is not listed here.  The ultimate guide to what will be on the exam is your notes and the textbook.  Note that you will need to be implicitly familiar with some earlier topics (such as how to program with C++ classes) even though you will not be asked any explicit questions about them.
 

Linked Lists

implementation (nodes and pointer manipulations)
applications
    implement queue,stack, etc.
    alternative to array
when to use (versus array)
variants
    with header node
    circular 
    doubly-linked

Trees

basic definitions
implementation options (nodes, arrays)
recursive structure/algorithms
traversal (pre-, in-, post-order)
binary search trees
AVL trees
    balancing
    rotation

Searching and Sorting

Measuring efficiency (O(n2), O(n log n), etc.)

Review problems:  4.2.3, 4.2.5, 4.3.9, 4.5.12abdg, 5.1.4, 5.1.5, 5.1.9, 5.1.10, 5.1.13,
 
 

 

Sample Questions

    1. Construct a BST corresponding to the word NUMERICAL. Build the tree by inserting the letters one-by-one (in the order they appear in the word), maintaining a BST ordered by increasing alphabetic order.
    2. Now construct an AVL tree corresponding to NUMERICAL. If/when the tree becomes imbalanced, redraw the tree after the appropriate rotation. You don't have to show the steps within the rotation, but label the new tree, something like "after LR rotation at node X".
  2. A complete binary tree is a binary tree in which every node has either zero or two children (i.e. no node has only one child). Write a new BTree method, BTree::isComplete(), which returns 1 if the object is a complete binary tree, and 0 otherwise. (Hint: recursion really does make this easier.)
  3. True or False. The three traversal algorithms (pre, in, post) for binary trees will always visit the nodes in different orders (that is, pre-order will visit the nodes in a different order from in-order, which will be a different order from post-order). If you answer True, explain why; if you answer False, give an example.