1
FINAL EXAM AND COURSE OUTCOMES MATCHING
COURSE OUTCOMES
Upon successful completion of this course, students should be able to
1. design recursive solutions.
2. analyze algorithm complexities.
3. describe and analyze sorting algorithms.
4. use Java Collections Framework to develop applications.
5. implement classic data structures: array lists, linked lists, stacks, queues, heaps,
binary trees, hash tables.
6. represent and solve problems using graph algorithms.
Here is a mapping of the final comprehensive exam against the course outcomes:
Question
Matches outcomes
Part I(1)
5
Part I(2)
5
Part I(3)
3
Part I(4)
6
2
Name:_______________________
Covers Chapters 20-28
Final Exam
CSCI 2410 Data Structures and Algorithms
Armstrong Atlantic State University
Instructor: 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.
Part I:
1. (2 pts) Given the following heap, show the resulting heap
after removing 62 from the heap.
62
A:
59
3. (2 pts) For the quick sort, show the partition of the
following list using the first element as the pivot.
{45, 34, 342, 102, 3, 5, 35, 29, 244, 34}
3
4. (4 pts) Show the minimum spanning tree rooted at vertex 3
for the following graph. Mark the order of the edges in
which they are added into the minimum spanning tree. What
is the total weight?
5
5
1
9
8
1
3
1
2
7
5
5
1
1
2
9
4
4
7
8
8
5
1
2
3
4
5
6
0
1
2
7
3 –> 1
3 –> 7
Total weight: 15
5. (4 pts) Show the shortest path tree rooted at vertex 3
for the following graph. Mark the order of the edges in
which they are added into the shortest path tree.
7
8
4
5
4
5
5
1
9
8
1
3
1
2
7
A:
5
5
1
1
2
9
4
4
7
8
8
5
1
2
3
4
5
6
0
1
2
7
3 –> 1
3 –> 7
6 (3 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.
7
8
4
5
5
.
0
N-1
1
2
3
4
5
6
key: 28
key: 14
key: 27
.
0
N-1
1
2
3
4
5
6
X
key: 1
key: 28
key: 14
key: 27
8
8
9
6
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:
public static int countUppercaseLetter(String s)
For example, countUppercaseLetter(“ABc”) returns 2.
7
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.
import java.util.*;
import java.io.*;
}
catch (Exception ex) {
System.err.println(ex);
}
// Get an iterator for the list
Collections.sort(list);
8
3. (10 pts) Add the following new method in the BST class.
public int height() {
return height(root);
}
4. a (5 pts) Add the following new method in the
UnweightedGraph class that returns the number of the edges.
int getNumberOfEdges();
Implement it.
9
}
4. b
public PriorityQueue<WeightedEdge> getEdges() {
10
11
5. (10 pts) For the 24–point game, introduced in Programming
Exercise 25.7, write a program to find out the success
ratio for the 24–point game, i.e., number of picks with
solutions / number of all possible picks.
Hints:
1. Assume the following method is given:
2. Create 52 cards as
3. Write the code that produces all combinations of picking
four numbers from the deck.
4. Count the ones that have no solutions.
6. (10 pts) Write a method to multiply two matrices and
analyze its complexity. The header of the method is as
follows:
public static double[][] multiplyMatrix(double[][] a, double[][] b)
To multiply matrix a by matrix b, the number of
131211
131211
131211
ccc
bbb
aaa
12
return result;
}
The time complexity is O(n^3)