CSC 332 - Data Structures - Spring 2014

There will be a midterm exam on Tuesday, March 22, 2014.

To prepare for the exam make sure that you know the following.

1.      (16 points) Given some input of integers and a hash function h(x) = x mod 10 in a hash table of size 10, show the result using the following paradigms.   Do not rehash the table.

a.       Separate chaining hash table

b.      Linear probing.

c.       Quadratic probing

d.      A second hash function h2(x) = 7 – (x mod 7)

2.      (8 points) Given some input of integers and a hash function h(x) = x mod 10 in a hash table originally of size 10, show the final result if the table must be rehashed (by doubling the table size) when the number of inserts is > (size of table / 2).  Collisions should be resolved by linear probing.

3.      (16 points) Illustrate how to quicksort a list of integers.   Illustrate each stage including the selection of a pivot using median-of-three.   Draw every swap.

4.      (15 points) From your reading and from what you saw in your sorting experiments, know the big-Oh execution time of each kind of sort (average case and worst case) and the relative performance in actual practice.

5.      (12 points) Be able to find a topological sort for a given graph.  You will have to fill in the table that is used in the algorithm.

6.      (12 points) Be able to use Dijkstra's algorithm to find the shortest weighted path from any starting node to all other nodes in a graph.  You will have to fill in the table that is used in the algorithm.

7.      (10 points) Give a minimum spanning tree for a given graph.  You can use either Prim's or Kruskal's algorithm.

8.      (10 points) Create Huffman Code for a given input (alphabet + frequencies).

Remember: The exam is not open notes and not open book.  However, you may bring in a single sheet of paper with some notes on it.