# Shared Flashcard Set

## Details

CPE103 Midterm2
n/a
24
Computer Science
03/01/2009

Term
 Preorder
Definition
 root, left subtree, right subtree
Term
 Inorder
Definition
 left subtree, root, right subtree
Term
 Postorder
Definition
 left subtree, right subtree, root
Term
 Levelorder
Definition
 Sequential (each level is traversed before moving to the next level)
Term
 AVL Tree
Definition
 the height different between any given node and it's two subchildren is at max 1
Term
 AVL - Single Rotation
Definition
 * Left subtree, left child* Right subtree, right child
Term
 AVL - Double Rotation
Definition
 * Left subtree, right child* Right subtree, left child
Term
 AVL - Running Time Analysis
Definition
 Avg: O(logN)Worst: O(N)
Term
 Hash Tables - Seperate Chaining
Definition
 Collisions dealt by creating a seperate array (Linked List)
Term
 Hash Tables - Seperate Chaining Methods
Definition
 isEmptyinsertremovefind
Term
 Hash Tables - Seperate Chaining Requirements
Definition
 Tablesize PrimeNo more than half full
Term
 Hash Tables - Seperate Chaining Runtime Analysis
Definition
Term
Definition
 Resolves collisions by sending them to a different place in the array
Term
 Hash Tables - Open Addressing Problems
Definition
 Tablesize PrimeNo more than half fullLinear Probing has primary clusteringNo DuplicatesElements not deleted, set to inactive
Term
Definition
 position(x) = (hash(x) + i^2) % tablesize
Term
 Hash Tables - Open Addressing Linear Probing
Definition
 position(x) = (hash(x) + i) % tablesize
Term
 Hash Tables - Open Addressing Runtime Analysis
Definition
Term
 Bubble Sort
Definition
 Compares two elements to see if they are in correct order. if not, swaps them. Runs N-1 times (through entire list)*Smaller elements 'bubble' to the top
Term
 Bubble Sort Runtime Analysis
Definition
 Best: O(N) [sorted]Avg: O(N^2)Worst O(N^2)
Term
 Insertion Sort
Definition
 Starts at front, tries to add element and then creates a new list and continues to add elements to list in correct order
Term
 Insertion Sort Runtime Analysis
Definition
 Best: O(N) [sorted]AVG: O(N^2)Worst: O(N^2)
Term
 Selection Sort
Definition
 Go through list finding the smallest element, and put it at the front. Continue through entire list.
Term
 Selection Sort Runtime Analysis
Definition
 Always: O(N^2)
Term
 Inversion
Definition
 A pair of elements in the incorrect spotAvg # of inversions given by: N(N-1)/4
Supporting users have an ad free experience!