Exam 2

Exam 2 is focused primarly on the material since Exam 1 but will also review the material from the pervious exam.

Exam 2 contains only multiple choice or short answer problems. You will have 50 minutes to complete this exam.

There is a practice exam availibe on PrairieLearn.

Topics Covered

Main Topics from lecture:

• 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
  • Strategy for a 2-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

Assignments referenced:

• lab_quacks
• lab_huffman
• lab_trees
• mp_stickers
• mp_list

Points:100

Registration: Wednesday, March 10

Start: Monday, March 22

End: Wednesday, March 24