Programming Languages Chapter 18 Homework The Text File Passed Command line Argument Assume

1

Sample Final Exam for CSCI 2410

FINAL EXAM AND COURSE OUTCOMES MATCHING

COURSE OUTCOMES

Upon successful completion of this course, students should be able to

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

3

3. (4 pts) Show the minimum spanning tree rooted at vertex 3

for the following graph using the algorithm in the book.

Show the detailed steps in the cost and parent array.

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?

4

4. (4 pts) Show the shortest path tree rooted at vertex 3

for the following graph using the algorithm in the book.

5

1

3

1

7

5

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:

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. Assume that the words are separated

by spaces in the text file.

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()

Requirements:

1. Don’t use return size;

8

4. (10 pts) Rewrite the insert method in the BST

class using recursion.

9

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

UnweightedGraph class that returns the number of edges.

10

(Optional) 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:

/* Returns true if the four cards have a solution */

public static boolean findSolution(int a, int b, int c, int d)

2. Create 52 cards as

11

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

where

bababac jijijiij 332211 ++=

.

}













=



























333231

232221

131211

333231

232221

131211

333231

232221

131211

ccc

bbb

aaa