Back to Exams
# Exam 3

### New Topics Covered

The exam will consist of multiple choice questions, one free responce question, and one coding question. It will require programming complete and correct C++ programs. Partial credit will only be given for working, compilable code that passes some test cases. Code that doesnt compile will not receive any credit. Multiple (but not unlimited) submissions will be allowed.

The programing question will be on creating trees.

The free responce question will be on what is the best covered data structure to use for a particual real world problem.

Material on lectures through Feb. 28th will be covered.

- Trees
- Basic tree terminology (CS 173)
- Tree Property: Binary
- Tree Property: Height
- Tree Property: Full
- Tree Property: Perfect
- Tree Property: Complete (as defined in data structures)
- Tree Property:
`NULL`

pointers in a BST, including proof - Traversal: Pre-Order, In-Order, and Post-Order
- Traversal: Level-Order
- Search Strategy: BFS, DFS

- Binary Search Tree
- Difference between a “Tree” and a “BST”
- Operation
`find`

, including running times in terms of`h`

and`n`

- Operation
`insert`

, including running times in terms of`h`

and`n`

- Operation
`delete`

, including running times in terms of`h`

and`n`

- A clear understanding of delete (particularly two-child delete)
- BST Property: Min/max nodes in a tree of a given
`h`

, and properties - BST Property: Height balance factor,
`b`

- AVL
- Difference between a “Tree”, “BST”, and an “AVL”
- Operation
`find`

, including running times in terms of`h`

and`n`

- Operation
`insert`

, including running times in terms of`h`

and`n`

- Operation
`delete`

, including running times in terms of`h`

and`n`

- Strategy for a 2-child delete
- AVL Tree Rotations
- Minimum/maximum nodes in an AVL tree

- BTree
- Difference between a key and a node in a BTree
- The order of a BTree
- Structural properties of a BTree
- BTree insertion and find algorithms (NOT remove!)

Assignments referenced:

- mp_lists, mp_mosaics
- lab_trees, lab_bst, lab_avl

**Points:**60

**Registration:** Thursday, February 29

**Start:** Monday, March 18

**End:** Wednesday, March 20