$($ANS$)$

$1-8$ In the three minimum$-$cost spanning tree algorithms we discussed in class, which one keeps a single tree and expand it until the final tree is found? Which one select multiple edges at each pass? Are the spanning trees found by them exactly the same? What about the cost?

$($ANS$)$

$1-9$ The quicksort algorithm has the best average case complexity. Therefore, it is better to use it in all cases.

True$/$False$)$

$2.(20$ points$)$ The NDHU campus is large with many buildings, facilities and roads. New students tend to get lost, especially in the first semester. It would be nice to have a customized APP to help the students. Outline the design by answering the following questions. $($Don$\text{'}$t need to write the complete code. Just the key elements of the $C++$ classes. You may use existing $C++$ classes in the textbook w$/$o copying in here. Specify your selection clearly.$)$

$($a$)$ Choose an appropriate data structure for the problem and briefly explain it$.$

$($b$)$ Outline the skeleton of a NDHUCampus class to maintain the information about all relevant entities: buildings, facilities and roads.

$($c$)$ Write Add$/$Delete functions to add$/$delete entities on the campus.

$($d$)$ Write a Find function to search for a particular entity.

$($e$)$ Outline how would you test your classes$/$functions in the main program.