Back to Quizzes

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

Assignments referenced:

  • lab_quacks
  • lab_huffman
  • lab_trees
  • mp_stickers
  • mp_list
  • mp_mosaics

Points:100

Registration: Thursday, March 18

Start: Friday, April 02

End: Saturday, April 03