Back to Exams

Exam 3

There will be one programing question. The programing question will be in an enviroment identical to the PotDs (run by using make not cmake). 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 questions will be working on some recursive function on a binary tree.

There will also be several short answer or multiple choice questions on material up to and including Monday October 9th. For a rough list of topics worth studying (not guaranteed to be exhaustive!):

New Topics 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, October 05

Start: Monday, October 16

End: Wednesday, October 18