## Midterm Study Guide

CSE 326: Data Structures

Winter 2006

#### Midterm Exam, Friday, February 3, 2006

- Exam policies
- Closed book, closed
notes. Calculators allowed (not sure they will be useful for anything but
you may use one if desired)
- The exam begins
promptly at 12:30 (sec A) (2:30 sec B) and ends at 1:20 (sec A) (3:20 sec
B).

- Topics covered
- Linked lists. Simple
linked lists, doubly linked lists, circularly linked lists.
- Stacks and Queues,
array and list implementations.
- Recursion. Designing
algorithms recursively.
- Asymptotic analysis,
Big-O. Worst case, upper bound, lower bound, analyzing loops,
recurrences, amortized complexity.
- Trees –
definitions
- Binary Heaps, D-heaps
- Findmin, Deletemin, Insert. Additional
operations of increase, decrease, buildheap.
- Leftist Heaps and Skew
Heaps - Findmin, Deletemin, Insert. Additional operations of merge,
increase, decrease
- Binomial Queues -
Findmin, Deletemin, Insert. Additional operations of merge, increase,
decrease.
- Dictionary ADT
- Binary search trees
– Inorder, preorder, postorder traversals, insert, delete, find.
- AVL trees - Single and
double rotations, insert, find.
- Splay trees -
Splaying, insert, find.

- Study suggestions
- Do concrete problems
from the book and re-work problems from lecture, section, and HW #1.
Suggestions of more problems from the book:
Chapter 2: 2.6, 2.10. Chapter 3: 3.21, 3.22, 3.23 (a). Chapter 4: 4.1,
4.2, 4.8, 4.9, 4.22, 4.27, 4.28. Chapter 6: 6.2, 6.3, 6.26, 6.30.
- Practice all the
operations in binary heaps, leftist and skew heaps, binomial queues,
binary search trees, AVL trees, splay trees. Practice analysis of
algorithms.
- All material from
lecture up through Splay trees is fair game. This material corresponds to: Chapters:
1, 2, 3, 4 (not section 4.7 on B-trees), and 6.