Test 3 Study Guide

Any questions over the following will be **closed book**.

*Know the linear search algorithm, when it is appropriate to use, and its relative efficiency (big-Oh notation).**Know the binary search algorithm, when it is appropriate to use, and its relative efficiency.**Know algorithms (not the code, just how they work) for selection sort, bubble sort, heap sort, quick sort.**Know the time efficiency of each sorting algorithm (big-Oh notation).**Know logs of numbers in base 2.**Be able to explain the advantages of generic classes.*

Any questions over the following
will be **open book.**

·
Know the basic operations on a stack.

·
Know how to convert an arithmetic expression from infix to
post-fix.

·
Know the basic operations on a queue.

·
Know how to use a stack and a queue to evaluate a post-fix
expression.

·
Be able to hand-execute binary tree traversals: pre-order,
in-order, and post-order.

·
Understand how a binary search tree is organized.

·
Understand how trees are used to represent arithmetic
expressions.

·
Know the definition of a graph.

·
Know how to do a depth-first traversal of a graph.

·
Know how to do a breadth-first traversal of a graph.

·
Know how to do a topological sort of a directed graph.

·
Be familiar enough with the Java collections
that are in the textbook that you can __write your own code__ using them.
Note that all of these are *generic*
classes.

·
Use both 1-dimensional arrays and 2-dimensional arrays of
either primitives or objects in a program.

·
Pass arrays as parameters.

·
Return arrays from functions.

- Know how to read data from a file using a
*Scanner*object; know how to use the*Scanner*methods.

- Create classes, write
accessor and mutator methods, override methods.

- Definition of recursion.
- Understand how activation records go on the stack.
- Hand-execute a recursive subprogram.
- Know advantages and disadvantages of recursion vs.
iteration.

·
Understand how an array is implemented in memory.

·
Understand the difference between a direct access data
structure and a sequential access data structure.

·
Know when a linked data structure is appropriate and when
another type of list structure is appropriate.

· Know what hashing is used for.

· Know in general how hashing works.

· Know advantages and disadvantages of hashing.

·
Be able to use a generic class in a program.

·
Be able to create your own generic class.