Archived Content

This website is an archive of the Spring 2019 semester of CS 225.
Click here to view the current semester.
Back to Exams

Exam 3

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

Topics Covered

Note: Topics covered on previous exams may be referenced (eg: you need to be able to compare anything vs. the running time of a sorted array/list, etc).

New topics from lecture for the exam:

  • AVL
    • Difference between a “Tree”, “BST”, and an “AVL”
    • 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
    • AVL Tree Rotations
    • Minimum/maximum nodes in an AVL tree
  • BTree
    • Difference between a key and a node in a BTree
    • The order of a BTree
    • Structural properties of a BTree
    • The min/max keys/children in each node in a BTree
    • The min/max total number of keys in a BTree
    • Advantages of a BTree
    • Running time of a BTree
  • Hash Table
    • Hash functions
    • Properties of a good hash function
    • SUHA
    • Hash Table Array
    • Load Factor
    • Hash Table Collisions
    • Open Hashing vs. Closed Hashing
    • Separate Chaining
    • Linear Probing
    • Double Hashing
    • Re-Hashing
    • Runtime of a hash table, in terms of n
    • Load factor’s impact on running times
    • Properties of a good hash table
  • Heaps
    • Construction of a Heap
    • Heap runtime
    • HeapifyUp
    • HeapifyDown
    • Priority queue ADT

Assignments referenced:

  • MP4, MP5
  • lab_huffman, lab_avl, lab_btree, lab_heaps


Registration: Thursday, March 21

Start: Thursday, April 04

End: Sunday, April 07