Study Guide
CSE 326: Data Structures
Spring 1997

Midterm Exam, May 2, 1997

• Topics covered
  • Linked lists. Simple linked lists, doubly linked lists, multi-lists, 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.
  • B-trees. 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 B-trees. You should understand these well.