I.  True/False

1.  _____  Text files are considered to be strings of characters that look like characters to your program

     and your editor.

2.  _____  A recursive solution is likely to be easy to find and implement if a problem cannot be

     reduced to any smaller instances of the same problem.

3.  _____  When writing a recursive method definition, always check to see that the method will not

     produce infinite recursion.

4.  _____  A linked list is a random-access structure.

5.  _____  A stack is not a random-access structure.

6.  _____  Queues cannot be implemented using a linked structure.

II.  Multiple Choice

1.  _____ What do we call data that flows from a file or input device to your program?

A.  output stream        B.  program stream      C.  input stream           D.  java stream

2.  _____  What do we call data that flows from your program to a file or output device?

A.  output stream        B.  program stream      C.  input stream           D.  java stream

3.  _____  What kind of exception might be thrown by the following?

Scanner fileScanBoys = new Scanner(new FileInputStream("boynames.txt"));

A.  OutOfBoundsException   B.  FileNotFoundException   C.  DivisonByZero      D.  JavaStreamError

4.  _____  What do we call a Method that contains an invocation or call to itself.

A.  looping                  B.  iterative                 C.  conditional            D.  recursive

III.  Short Answer

1.  Name one method that can be used to check for the end of an input file. 

2.  Write a statement that will create a stream named fileIn that is a member of the class Scanner.  It should connect the stream to a text file named "sally.txt" so that your program can read input from the text file sally. 

3.  What is the output of the following program?                         [output]

public class TestExercise

{

            public static void main(String[] args)

            {

                        cheers(3);

            }

           

            public static void cheers (int n)

            {

                        if(n = = 1)

                        {

                                    System.out.println("Hurray");

                        }

                        else

                        {

                                    System.out.println("Hip  ");

                                    cheers(n-1);

                        }

            }

}

4.  Assuming that a method named addToStart places a node at the beginning of a linked list, and a method named outputList prints out the contents of a linked list beginning with the node at the front, what output is produced by the following code?  

LinkedList1 list = new LinkedList1( );

list.addToStart("apple", 1);

list.addToStart("hot dogs", 12);

list.addToStart("mustard", 1);

list.outputList( );

 

The next eleven questions use the following diagram.  In the diagram a reference is indicated by an arrow.  The list nodes have an info variable containing an integer and a next variable containing a reference, and list, ref1, and ref2 are references to a list node.

                                          ref1                                                                                                         ref2

                                   

 Give the values of the following expressions:  

5.   ref1.info 

6.  ref2.next.info

7.  list.next.next.info

Are the following expressions true of false?  

8.  _____  list.next = = ref1                                                    

9.  _____  ref1.next.info = = 60

10.  _____  ref2.next =

11.  _____  list.info = = 25

Write one statement to do each of the following:  

12.  Make list point to the node containing 45.

13.  Make ref2 point to the last node in the list.

14.  Make list point to an empty list.

15.  Set the info variable of the node containing 45 to 60.

                                          

III.  Coding

Following the style of the figures in our textbook, draw the list that would result from each of the following code sequences:

1.  

     UnsortedLinkedList myList = new UnsortedLinkedList( );

     myList.insert(5);

     myList.insert(9);

     myList.insert(3);

2.  

     UnsortedLinkedList myList= new UnsortedLinkedList( );

     myList.insert(5);

     myList.insert(9);

     myList.insert(3);

     myList.delete(9);

The textfiles boynames.txt and girlnames.txt, which are included in the source code for this book, contain a list of the 1000 most popular boy and girl names in the United States for the year 2003 as compiled by the Social Security Administration.

            Those are blank-delimited files where the most popular name is listed first, the second most popular name is listed second, and so on, to the 1000th most popular name, which is listed last. Each line consists of the first name followed by a blank space and then the number of registered births using that name in the year. For example the girlnames.txt file begins with:         

                        Emily 25494

                        Emma 22532

                        Madison 19986

            this indicates that Emily was the most popular name with 25,494 registered namings, Emma was second most popular with 22,532, and Madison was the third most popular with 19,986.

            Write a program that reads both the girls and boy's files into memory using arrays. Then, allow the user to input a name. The program should search through both arrays. If there is a match, then it should output the popularity ranking and the number of namings. The program should also indicate if there is no match.

            For example, if the user enters the name "Justice," then the program should output:

            Justice is ranked 456 in popularity among girls with 655 namings.

            Justice is ranked 401 in popularity among boys with 653 namings.

            If the user enters "Walter," then the program should output:

            Walter is not ranked among the top 1000 girl names.

            Walter is ranked 356 in popularity among boys with 775 namings.

 

Write a program that will search a binary file of numbers of type int and write the largest and smallest numbers to the screen. The file contains nothing but numbers of type int written to the file with writeInt.

 

A savings account typically accrues savings using compound interest. If you deposit $1,000 with a 10% interest rate per year, then after one year you have a total of $1,100. If you leave this money in the account for another year at 10% interest, then after two years the total will be $1,210. After three years you would have $1,331, and so on.

            Write a program that inputs the amount of money to deposit, and interest rate per year, and the number of years the money will accrue compound interest. Write a recursive function that calculates the amount of money that will be in the savings account using the input information.

            To verify your function, the amount should be equal to P(1+i)n, where P is the amount initially saved, i is the interest rate per year, and n is the number of years.

 

In an ancient land, the beautiful princess Eve had many suitors. She decided on the following procedure to determine which suitor she would marry. First, all of the suitors would be lined up one after the other and assigned numbers. The first suitor would be number 1, the second number 2, and so on up to the last suitor, number n. Starting at the suitor in the first position, she would then count three suitors down the line (because of the three letters in her name), and the third suitor would be eliminated from winning her hand and removed from the line. Eve would then continue, counting three more suitors, and eliminate every third suitor. When she reached the end of the line, she would continue counting from the beginning.

            For example, if there were six suitors, the elimination process would proceed as follows:

            123456             Initial list of suitors: start counting from 1.

            12456              Suitor 3 eliminated:  continue counting from 4.

            1245                Suitor 6 eliminated:  continue counting from 1.

            125                  Suitor 4 eliminated:  continue counting from 5.

            15                    Suitor 2 eliminated:  continue counting from 5.

            1                      Suitor 5 eliminated:  1 is the lucky winner.

            Write a program that creates a circular linked list of nodes to determine which position you should stand in to marry the princess if there are n suitors. Your program should simulate the elimination process by deleting the node that corresponds to the suitor that is eliminated for each step in the process.