Study Guide
CSE 326: Data Structures
Spring 1997
Midterm Exam, May 2, 1997
 Topics covered

Linked lists. Simple linked lists, doubly linked lists, multilists,
polynomials, sparse matrices, adjacency lists, text editing, stacks, queues.

Recursion. Designing algorithms recursively, using call by reference.

Analysis of algorithms. Worst case, average case, upper bound, lower
bound, analyzing loops, recurrences, amortized complexity.

Trees and traversals. Multiway trees, preorder, postorder.

Binary search trees. Inorder traversal, insert, delete, find.

AVL trees. Single and double rotations, insert, delete, find.

Splay trees. Splaying, split, join, insert, delete, find.

Btrees. Insert, delete, find.

Study suggestions

Do concrete problems from the book.

Do the last midterm exam.

Practice all the operations in binary search trees, AVL trees,
splay trees, and Btrees. You should understand these well.
cse326request@cs.washington.edu
(Last Update:
05/30/97
)