Test 3 Study Guide

Sorting, Searching, Generic classes

Stacks & Queues

         Know the basic operations on a stack.

         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.

         Know how to implement a graph.

Java Collections

         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.

File Input and Output



Memory Allocation and Linked Data Structures

         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.

Generic Classes

         Be able to use a generic class in a program.

         Be able to create your own generic class.