1
Name:_______________________
Covers Chapters 18-29
Final Exam
CSCI 3230 Data Structures
Georgia Southern 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 refined Prim’s algorithm in the book. Show the detailed steps in the cost and
parent arrays. Show the list T. T contains the vertices that are added to the spanning tree
in order. What is the total weight of the minimum spanning tree? Also draw the tree for
each step in the left column.
5
5
1
2
9
8
1
1
2
3
4
6
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
cost
1
4
7
5
3
T:
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
parent
T:
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
parent
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
parent
4
0 1 2 3 4 5 6
cost
5
4. (4 pts) Show the shortest path tree rooted at vertex 3 for the following graph using the
Dijkstra’s algorithm in the book. Show the detailed steps in the cost and parent arrays.
Show the list T. T contains the vertices that are added to the shortest path tree from the
source vertex 3 in order. Also draw the tree for each step in the left column.
5
5
1
9
1
1
3
T:
cost
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
parent
cost
T:
1
5
6
6
T:
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
parent
T:
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
parent
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
parent
7
0 1 2 3 4 5 6
cost
0 1 2 3 4 5 6
parent
8
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:
9
2. (10 pts) Write a program that reads words from a text file and displays all the words
(duplicates allowed) in ascending alphabetical order. The text file is passed as a
command-line argument. Assume that the words are separated by spaces in the text file.
10
3. (10 pts) Add the following new method in the BST class.
Requirements:
1. Don’t use return size;
11
4. (10 pts) Add the following new method in the UnweightedGraph class that returns the
number of edges.
int getNumberOfEdges();
12
4. (10 pts) Rewrite the insert method in the BST class using recursion.
6. For the following graph, answer the questions: (if the edge has no directions indicated,
the edge has both directions.)
5
5
1
1
2
9
4
4
7
8
8
5
1
2
3
4
5
6
0
1
2
7
b. (2 pt) Is the following graph strongly connected? Is the following graph weakly
connected?