1
Name:_______________________
Covers Chapters 18-29
Final Exam
CSCI 2410 Data Structures and Algorithms
Armstrong Atlantic State University
Instructor: Dr. Y. Daniel Liang
Please note that the university policy prohibits giving the exam score by email. If you need to know your
final exam score, come to see me during my office hours next semester.
I pledge by honor that I will not discuss this exam with anyone until my instructor reviews the exam in the
class.
Signed by ___________________ Date ___________________
Part I:
1. (2 pts) Given the following heap, show the resulting heap
after removing 62 from the heap.
2. (2 pts) For the quick sort, show the partition of the
following list using the first element as the pivot.
2
3. (4 pts) Show the minimum spanning tree rooted at vertex 3
for the following graph using the algorithm in the book.
Mark the order of the edges in which they are added into
the minimum spanning tree. What is the total weight of the
minimum spanning tree?
5
5
1
9
8
1
3
1
7
4. (4 pts) Show the shortest path tree rooted at vertex 3
for the following graph using the algorithm in the book.
Mark the order of the edges in which they are added into
the shortest path tree. Please draw a new final tree.
5
5
1
7
8
9
4
8
1
3
4
5
0
1
2
7
7
8
4
5
3
5 (2 pts)
Assume the load factor threshold is 75%. Show the hash
table of size 13 after inserting entries with keys 14, 1,
27, 28, using linear probing. Show the hash table after
removing 1.
Part II: Complete the following programs.
1. (10 pts) Write a recursive method that returns the number
of the uppercase letters in a string using the following
method header:
4
2. (10 pts) Write a program that reads words from a text
file and displays all the words (duplicates allowed) in
5
3. (10 pts) Add the following new method in the BST class.
/** Returns the number of nodes in this binary tree */
public int getNumberOfNodes()
Requirements:
1. Don’t use return size;
6