Exam 2

Exam 2 Covers lists both linked and array in detail and simple tree ideas through binary search trees. It does not have any coding component.

There is a practice exam on PrairieLearn.

Exam 2 is 50 minutes long and only has multiple choice and short answer questions.

Topics Covered

• Pointers and References in C++
• Pass by value, by reference, and by pointer
• Indirection in C++:
• 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
• 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:

• lab_memory
• lab_quacks
• lab_trees
• mp_stickers
• mp_list

Points:60

Start: Sunday, September 25

End: Tuesday, September 27