Exam 2

Theory Exam 2 contains only multiple choice or short answer problems. You will have 50 minutes to complete this exam.

Topics Covered

A list of topics will be announced closer to the exam.

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

Points:70

Registration: Thursday, February 14

Start: Thursday, February 28

End: Sunday, March 03