CSUDH Computer Science Department

 

CSC311 Data Structures

(Spring 2006)

 

Midterm Examination 2

 

(11:30am -- 12:45pm, May 3, 2006)

 

  

1.      Priority Queues and Heaps (15 points):

a.       Describe a scenario where the priority queue should be the main data structure. Justify your answer.

 

b.      Briefly explain the Priority Queue Sort algorithm, and explain the relationship between the priority queue sort and the selection-sort as well as the insertion-sort.

 

c.       Illustrate the performance of the heap-sort algorithm on the following input sequence: 2, 5, 16, 4, 10, 23, 39, 18, 26, 15.

 

 2.      Hash table. (15 points)

a.       Argue why a hash table is not suited to implement an ordered dictionary.

  

b.      Given the following sequence of keys: 66, 47, 87, 90, 126, 140, 145, 153, 177, 285, 393, 395, 467, 566, 620, 735.

                           i.      Draw the 19-entry hash table that results from using using the hash function h(i) = (3i+7) mod 19, to hash the above keys, assuming collisions are resolved by chaining.

  

                         ii.      What is the result of above question when collisions are handled by double hashing using the secondary has function h’(k) = 11 – (k mod 11)?

 

3.      Search Trees (35 points): Given the following sequence of keys: 20, 12, 26, 10, 16, 23, 28, 14, 18, 30

a.       Binary search tree: (10 points)

                                       i.      Insert this sequence of keys into an empty binary search tree. Draw the tree after each insertion.

 

                                      ii.      Delete the keys 12 and 20 from above binary search tree. Draw the tree after each deletion.

  

b.      AVL Tree: (10 points)

                                       i.      Insert this sequence of keys into an empty AVL tree. Draw the tree after each insertion.

  

                                     ii.      Delete the keys 12 and 20 from above AVL tree. Draw the tree after each deletion.

 

c.       (2-4) Tree and Red-back Tree: (15 points)

                                       i.      Insert the given sequence of keys into an empty (2-4) search tree. Draw the tree after each insertion.

 

                                     ii.      Delete the keys 12 and 20 from above (2-4) search tree. Draw the tree after each deletion.

 

                                    iii.      Convert the above (2-4) tree to a red-black tree

  

 

  1. Graphs (25 points): Let G be a weighted graph whose vertices are numbered 1 through 7, and whose edges with weights are given by the table:

 

1)      Draw the graph

2)      Give the DFS result starting at vertex 1

3)      Give the BFS result starting at vertex 1

4)      Find the shortest paths from vertex 1 to all other vertices using Dijkstra’s algorithm

5)      Find a minimum spanning tree

 

 

Edge

Weight

(1,2)

7

(1,3)

6

(1,4)

5

(2,4)

3

(2,5)

4

(3,4)

5

(3,6)

9

(4,5)

5

(4,7)

3

(5,7)

6

(6,7)

8