Back to Exams

Exam 3

The exam will consist of multiple choice questions, one free response 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 programming question will be on tree-related content such as the construction or use of binary trees of different properties (full, complete, perfect, BST, AVL, etc…). Be sure to practice your recursion, as these may include constructing a tree of a precise unusual shape.

The free response question will require you to identify the best solution to a real world problem and describe in detail your method of choice (as well as its Big O). The methods can include any previously seen data structure in CS 225.

Here is a rough approximation of the grading rubric for exam 3:

Points Rubric Item Description
1 Optimal Data Structure The data structure chosen is an optimal solution to the problem
1 Optimal Big O The Big Os given are both correct for the data structure chosen and optimal for the problem.
2 Optimal Structure Justified Correctly There is a logically consistent and correct justification for why the chosen data structure is optimal.
1 Big O Variable(s) Defined The variable(s) used make sense in the context of the problem and are used appropriately to give Big Os
2 Data Structure Correct Interface The relevant functions of the interface are described correctly. No implementation details are needed, just a clear idea of what the functions are doing.
2 Correct Interface Usage It is clear how the interface is being used to solve the problem
1 Correct Interface Big O Every function described has the correct Big O for the data structure chosen (even if the data structure itself is not optimal).

The content on the exam may cover all lecture material up through (and including) Wednesday October 14. It will not include heaps but may contain overlap with previously seen material, with a focus on trees.

Core Material 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_bst, lab_avl, lab_tree, lab_btree

Points: 80

Registration: Thursday, October 08

Start: Wednesday, October 21

End: Friday, October 23