CSE326: Data Structures

Midterm Review List

1.

General: Be able to write, trace, or perform a complexity analysis of:

(a)

recursive functions

(b)

functions that work with any kind of linked list (singly linked, doubly linked, circular, or whatever a problem defines)

(c)

functions that work with binary trees, general trees implemented via binary trees, binary search trees (with or without splaying), B+trees (NOT AVL trees)

(d)

functions that implement hashing

(e)

functions that work with binary heaps

2.

Complexity Analysis: Be able to determine time complexity in Big Oh notation, in terms of the smallest common function f such that T(N) = O(f(N))

(a)

using counting arguments

(b)

using results of other analyses if applicable

Be able to answer questions about the meaning of O(N).

3.

Trees: Be able to construct and search (by hand)

(a)

binary search trees

(b)

splay trees

(c)

B+trees

Be able to delete from binary search trees.

4.

Hashing: Be able to construct hash tables in several different ways. (My terminology and the book's are different, so I will try to be very explicit here.)

(a)

hash to buckets that point to either linked lists or contiguous lists

(b)

direct organization (book says ``open addressing'') with linear or quadratic probing or with double hashing (book's terminology for a second hash function)

Know what to do when the hash table becomes too full. Be able to discuss complexity.

5.

Heaps: Be able to construct, add to, or delete Min from a binary heap (or delete Max from a max heap).