Back to Quizzes

Exam 3

Exam 3

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

Topics Covered

Topics from lecture (all BST concepts, no AVL trees):

  • 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
  • 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:

  • mp_stickers, mp_lists
  • lab_memory, lab_trees

Points:75

Registration: Thursday, October 08

Start: Friday, October 23

End: Saturday, October 24