Overview

Theory Exam 2 is worth 70 points.

Exam 2 contains only multiple choice or short answer problems. You will not be required to write any standalone code outside of the PrairieLearn web interface. You will have 50 minutes to complete this exam.

TA Review Session

A TA review session will be held for this exam on Tuesday (Oct. 9) from 7:30pm - 9:00pm in 1404 SC.

Topics Covered

Topics from lecture (topics go through the first 10 minutes on Monday’s lecture; all BST concepts, no AVL trees):

• Object Lifecycle
  • Lifecycle in stack memory
  • Lifecycle in heap memory (new/delete)
• Inheritance
  • Base class
  • Derived class
  • Virtual functions
  • Pure virtual functions
• Templates in C++
• Array List
  • Operation insertAtFront, including running time, resize strategies, and proofs
  • Operation insertAtIndex, including running time, on both a sorted and unsorted list
  • Operation removeAtIndex, including running time, on both a sorted and unsorted list
  • Operation insertAfterElement, including running time, on both a sorted and unsorted list
  • Operation removeAfterElement, including running time, on both a sorted and unsorted list
  • Operation findIndex, including running time, on both a sorted and unsorted list
  • Operation findData, including running time, on both a sorted and unsorted list
• Linked List
  • Operation insertAtFront, including running time and insertion strategies
  • Operation insertAtIndex, including running time, on both a sorted and unsorted list
  • Operation removeAtIndex, including running time, on both a sorted and unsorted list
  • Operation insertAfterElement, including running time, on both a sorted and unsorted list
  • Operation removeAfterElement, including running time, on both a sorted and unsorted list
  • Operation findIndex, including running time, on both a sorted and unsorted list
  • Operation findData, including running time, on both a sorted and unsorted list
• Stack and Queues
  • Using a list to build a stack/queue
  • Operations pop, push, enqueue, and dequeue, including running times
  • Applications of stacks and queues (see lab_quack)
• Iterators
  • Operations *, !=, and ++.
  • Applications of iterators
  • Utility of iterators
• 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

Assignments referenced:

• MP2, MP3
• lab_memory, lab_quacks, lab_trees