Back to Exams

Exam 2

The exam will consist of multiple choice questions, one free responce 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:

  • Make a Stack or Queue out of a std::list or std:vector
  • The simple functions to implement a tree such as those in lab_bst (not all of remove)

The free responce question will be on list, stacks, and/or queues. This will be similar to the ones from last exam but should be worded more clearly than some of the variants were last exam.

The content on the exam will cover all lecture material up through (and including) February 14th. 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

Example Free Response Question

Consider a class Things that is implemented using a singly linked list but stores the following and nothing else.

  • a pointer head that points to the first node in the linked list.
  • a pointer middle that always points to the node at the integer index $\lfloor length/2 \rfloor$.
  • a integer size that stores the number of elements in the list

Describe an algorithm for insert at head as well as the big-$O$ runtime for that algorithm. This should be the fastest algorithm given the above constraints.

The answer must be in the form of English sentences.

Example Full Credit Answer

The algorithm for insert will work as follows. Step one: create a new list node with the value being inserted and set the next pointer in the list node to the value of head. Step two: update head to point to the new node. Step three: update size to be one greater than the current size. Step four: walk through the list node by node until you reach the node at floor(size/2) and update the middle pointer to point at that node. This algorithm is clearly O(n) since you have to walk through half of the list when running it.

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, February 08

Start: Monday, February 19

End: Wednesday, February 21