Back to Exams

Exam 2

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.

Instead of a practice programming question, you should prepare on your own to answer one of the following coding questions. In other words, the exam question will loosely require you to do one of the following:

  • Make a Stack or Queue out of a std::list or std:vector
  • Implement a tree function similar to those seen in lab_bst (but not the full code implementation of ‘remove’)
  • Navigate a tree to find a specific node of interest (if it exists)

The free response question will be on either a binary tree or a binary search tree.

The content on the exam will cover all lecture material up through (and including) September 23. This will include some overlap with the previous two exams and will primarily focus on lists, arrays, and trees. It will not cover balanced binary search trees.

There is a practice exam covering the ideas on prairieLearn

Covered Material

  • Pointers and References in C++
  • Pass by value, by reference, and by pointer
  • Lists
    • ADT
    • Linked
    • Array
  • Stacks and Queues
  • 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)

Assignments referenced:

  • lab_debug
  • lab_memory
  • lab_quacks
  • lab_bst
  • mp_lists

Points:60

Registration: Thursday, September 19

Start: Wednesday, October 02

End: Friday, October 04