Review Sheet for Final Exam
The emphasis of the final exam will be on the material presented since Exam 2. However, you are responsible for ALL concepts and syntax presented since the beginning of the semester.
It is suggested that you review your previous exams and projets. In addition, use the topics below as a GUIDE in studying for the exam.
- Sorting:
- How each sort (bubble, selection, merge, quicksort) works conceptually
- The Big-Oh for each of the four sorts
- How to code the bubble and selection sorts
- How to code the recursive functions for the merge and quick sorts
- Why one might select one sort over another
- Asymptotic Analysis
- The concept of Big-Oh
- The most common functions encountered in Big-Oh analysis, from slowest to most rapid growth
- The effect of constants and factors in Big-Oh functions
- How to choose which algorithm to use based on its Big-Oh
- Trees
- General concept of a tree and tree terminology
- Concept of a binary tree and a binary search tree
- The concepts and code for preorder, inorder, and postorder tree traversals
- How to write the code for searching for a node, inserting a node, and deleting a node from a binary search tree
- Stacks and Queues
- The concepts of stacks, queues, and lists
- Ways in which stacks, queues, and lists can be implemented
- How to write class definitions for stacks and queues
- How to write the code for methods that would commonly be included in stack and queue classes (e.g., clear, push, pop, check for empty, enqueue, dequeue)
Terminology:
- node, path/edge, root, internal node, leaf, subtree, parent, child, sibling, ancester, descendant, depth of a node, depth of a tree, LIFO, FIFO, push, pop, head, tail, enqueue, dequeue