Midterm #1 Study Guide
CSE 373: Data Structures & Algorithms
Midterm Exam #1, Friday, October 22, 2010
- Closed book, closed
notes. Calculators NOT allowed.
- The exam begins promptly
at 2:30 and ends at 3:20.
- Stacks and Queues,
array and list implementations.
- Recursion. Designing algorithms recursively.
- Asymptotic analysis,
Big-O. Worst case, upper bound,
lower bound, analyzing loops, recurrences.
- Trees –
- Dictionary ADT
- Binary search trees
– Inorder, preorder, postorder traversals, insert, delete, find.
- AVL trees - Single and
double rotations, insert, find.
- Binary Heaps -
Findmin, Deletemin, Insert.
Additional operations of increase,
Topics covered on these exams may not be the
exact same topics covered on our exam; please see the list of topics listed
above for topics covered on our exam.
These are provided to help you study and are
not meant to be interpreted as a guarantee of the format of our actual midterm
in terms of length or type of questions.
Midterm I samples:
Midterm II samples: (These are mostly not relevant except where noted.)
- Do concrete problems
from the book and re-work problems from lecture and HW. Suggestions of a few 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.19, 4.25, Chapter 6: 6.2, 6.3.
- Practice all the
operations on stacks and queues, binary search trees, AVL trees, and binary
- Practice analysis of
- All material from
lecture up through binary min heaps is fair game. This material corresponds to: Chapters:
1, 2, 3, 4 (Not Including: section 4.5 on Splay trees, 4.7
on B-trees, or 4.8), and 6 (Not including: sections