Study Guide
CSE 326: Data Structures
Winter 1999

Midterm Exam, Friday, February 5, 1999

• Exam policies
  • The midterm is closed book.
  • An 8 1/2 X 11 inch blue (or green) book is required.
  • You may put your own hand written notes in your blue book to aid you during the exam.
  • The exam begins promptly at 1:30 and ends at 2:20.
• 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.
• Study suggestions
  • Do concrete problems from the book. Suggestions from chapter 2. 2.1, 2.7. Suggestions from chapter 3. 3.2, 3.9, 3.10, 3.17. Suggestions from chapter 4. 4.1, 4.2, 4.9, 4.11, 4.23, 4.24, 4.36.
  • Do last years midterm exam.
  • Practice all the operations in binary search trees, AVL trees, and splay trees. You need to know how to implement pointers with arrays. You need to be able to convert a recursive algorithm into an iterative algorithm. Practice analysis of algorithms.