Programming Languages Chapter 3 Homework Write Program That Reads Words From Text

1

Sample Final Exam for CSCI 3230 (Java) Covers Chapters 18-29

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.

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 18-29

Final Exam

CSCI 3230 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) Add the elements 4, 15, 29, 101, 13, 2, into a

heap in this order. Draw the final heap.

2. (2 pts) Given the following heap, show the resulting heap

after removing 62 from the heap.

3

3. (2 pts) For the quick sort, show the partition of the

following list using the first element as the pivot.

4. (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?

5. (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.

4

5

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.

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:

6

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.

7

3. (10 pts) Add the following new method in the BST class.

/** Returns the number of nodes in this binary tree */

public int getNumberOfNodes()

8

4. (10 pts) Add the following new method in the

UnweightedGraph class that returns the number of edges.

9

(Optional) 5. (10 pts) For the 24-point game, introduced in

Programming Exercise 20.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.

10

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

columns in a must be the same as the number of rows

}