EECS 281 FINAL EXAM QUESTIONS ANSWERED CORRECTLY LATEST UPDATE 2026

EECS 281 FINAL EXAM QUESTIONS ANSWERED CORRECTLY LATEST UPDATE 2026 Hashing Basic Functionality Complexity - Answers Efficient: Insert O(1), Search O(1), Remove O(1) Inefficient: Sort, Kth largest, Joint/Merge Hashing Load Factor - Answers Alpha = α = N/M N is number of keys in table M is size of table Need to keep below 0.5 so functions are efficient. Hashing Load Factor - Separate Chaining - Answers Load factor, α, is average number of items per table entry Hashing Load Factor - Open Addressing - Answers Load factor, α, is percent of table filled Hashing Insert Complexity - Answers O(1) if duplicates are allowed O(α) if no duplicates allowed. Reasoning: Need to search for item to see if it already exists. Search is expensive. Hashing Search Complexity - Answers O(α) Need to hash for the key but then need to linear search table if rehashing or chain if separate chaining Hashing Remove Complexity - Answers O(α). Need to search for item before removing it. Could be even worse depending on separate chaining container. Hashing Complexity - Normal Vector - Answers Insert and Search both O(α) Hashing Complexity - Sorted Vector - Answers Insert is O(α) and Search is O(log α) Hashing Complexity - Binary Tree - Answers Insert and search O(log a). Large memory over head to maintain tree. Hashing Linear vs Quadratic Probing Complexity - Answers Number of probes for hit and for miss grow exponentially with α for both. Quadratic has slightly slower growth for both hit and miss. Number of probes for hit number of probes for miss Dynamic Hashing Summary - Answers When α ≥ 0.5, grow table size (M) and rehash. Keeps load factor α low, but occasional expensive regrow operation Dynamic Hashing Amortized Complexity - Answers O(M) - Linear 1) Initial inserts have cost until α ≥ 0.5 = Max 2.5 probes for insertion hit/miss if α ≤ 0.5 = Insert M/α -1 keys before α exceeds 0.5 = 2.5 * (M/α -1) = O(M) 2) Grow and rebuild table = Max 1.5 probes for insertion hit/miss if α ≤ 0.25 = 1.5 * M/2 = O(M) Thus 2O(M) = O(M) = Linear amortized cost.... O(1)! Simple Tree - Answers Acyclic, connected graph. Undirected. Rooted Tree - Answers Simple Tree w/ selected vertex as root. Edges directed AWAY from root. Internal Node - Answers A node with children ordered tree - Answers A rooted tree in which all children of each vertex are ordered left to right. Binary Tree - Answers a tree in which each node has at most 2 children. Complete Binary Tree - Answers A binary tree with depth d where: 1) Depths 1,...,d-1 are all full (each level of the tree except the last is full) 2) All internal nodes are to the left of external nodes at depth d-1 (All leaves are at the second to last level or left most at the last level) Complete Binary Tree Implementation - Answers Root: Index 1 Left Child of node i = 2*i Right child of node i = 2*i+1 Inefficient use of space for sparse trees Binary Tree Insert Complexity - Answers Best: O(1) Worst: O(n) Binary Tree Remove Complexity - Answers Worst: O(n) Binary Tree Find Empty Space Complexity - Answers Best: O(n) Worst: O(2^n) preorder traversal - Answers root, left subtree, right subtree DEPTH FIRST inorder traversal - Answers left, root, right DEPTH FIRST postorder traversal - Answers left, right, root DEPTH FIRST level order traversal - Answers This depth left to right - Next depth left to right - ... BREADTH FIRST Symbol Table ADT - Answers Insert, Remove, Join, Search, Sort, Select (kth Largest) BST Property - Answers - Keys satisfy BST property: left subtree ≤ node right subtree Insert and search have similar implementations BST Search/Insert Complexity - Answers Average: O(log n) - For a balanced tree Worst: O(n) - For a single branch stick tree Also O(h/d) where h and d are max height/depth 1) While node is not null and not the desired key, X 2) If X this node key, search this node left child 3) If X this node key, search this node right child BST Remove - Answers 4 Cases: 1) Z has no children (trivial) 2) Z has no left child OR no right child (trivial) - Replace with child 3) Z has two children - Take smallest in RHS as new root - make old LHS new root LHS. AVL Tree Property - Answers 1) Is a BST 2) For every node V of T, the child heights differ by no more than 1 - Use ROTATION to fix balance AVL Insert + Complexity (adn search - Answers Worst: O(log n) (same for search) 1) Insert like BST 2) Rotate to keep balance at parent and update heights Balance = height of left - height of right 3) Recursively check balance and rotate and update heights along path to node AVL Remove + Complexity - Answers Worst: O(log n) 1) Remove like BST (RHS Inorder Successor) 2) Re-balance at removal, update height and recursively back up path to node AVL Sort Complexity - Answers 1) O(nlogn) to insert + 2) O(n) to traverse Right Rotation Steps - Answers 1) Left child becomes parent 2) Parent becomes right child (of old left child). 3) Old left child right pointer becomes left pointer of parent Graph - Answers G = (V, E) Set of vertices together with a set of edges that connect pairs of vertices Simple Graph - Answers Graph with 1) No parallel edges 2) No self-loops Simple Path - Answers Sequence of edges connecting one node to another with no vertex appearing twice Connected Graph - Answers A graph here a simple path exists between all vertices Cycle - Answers Simple path but first and final nodes are the same Directed vs Undirected - Answers Directed if edges have specified direction - Ordered pairs Undirected - use unordered tuples Complete Graph - Answers Contains all possible edges |E| = |V| * | V-1 | / 2 Dense Graph - Answers Contains many edges |E| ~ |V|^2 Adjacency Matrix Sparse Graph - Answers Contains few edges |E| |V|^2 |E| ~ |V| Adjacency List Adjacency Matrix - Answers |V| x |V| matrix representing edges Optimal for DENSE Directed has to from, undirected only needs |V|^2/2 space Unweighted vs weighted dictates value in matrix (Boolean vs weight number) Adjacency List Complexity - Answers O(1) Access O(|E|/|V|) find Optimal for SPARSE Avg Single Find: O(1+ E/V) Cost for all vertices: O(V) * O(1+ E/V) = O(V+E) Adj List DFS/BFS Complexity - Answers Each vertex called at most once - O(V) Adjlist for each vertex called at most once - O(1+ E/V) = O(V)*O(1+E/V) = O(V + E) LINEAR with Edges and Vertices