Test 3 Study Guide

Any questions over the following will be closed book.

Sorting, Searching, Generic classes

Any questions over the following will be open book.

Stacks & Queues

         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.

Trees

         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.

Graphs

         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.

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.

Arrays

         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

Classes

Recursion

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.

Generic Classes

         Be able to use a generic class in a program.

         Be able to create your own generic class.