Study Guide
CSE 326: Data Structures
Spring 1998
Midterm Exam, May 1, 1998
- 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.
- Multidimensional trees. Quad trees, k-d trees, range queries, insert,
delete.
-
Study suggestions
-
Do concrete problems from the book. Here are some suggestions from
chapter 4. 4.1, 4.2, 4.9, 4.16, 4.23, 4.24, 4.36.
-
Do last years midterm exam.
-
Practice all the operations in binary search trees, AVL trees,
splay trees, B-trees, quad trees and k-d trees.
You should understand these well.