Exam 3 Review Topics

Exam 3 Review Topics

(Chapters in 5th Ed.: 14, 17, and 18)

Sorting and Big-O Analysis

-  selection sort

-  insertion sort

-  merge sort

-  number of comparisons/swaps

-  Big-O analysis

o  quadratic, n log(n)

-  measure runtime in Java

Tree Terminologies

-  nodes: root, leaf, internal node

-  parent, child, ancestor, descendant

-  level, height

-  full, complete, balanced, empty

-  path, branch

-  subtree

Binary Tree Traversal

-  left/right child/subtree

-  in-order traversal

-  preorder traversal

-  post-order traversal

-  representing a (complete) binary tree with an array

-  efficiency

Binary Search Tree

-  recursive definition

-  find

-  add

-  remove

o  a leaf node

o  a node with one child

o  a node with two children

-  code

Generic Programming

-  type variable, such as <E>

-  implementing generic classes

-  using generic types (interfaces, classes) in Java code

Quiz 3 Topics