Name:_______________________



Name:_______________________

Covers Chapters 20-22

50 min |CSCI 2410 Data Structures and Algorithms

Armstrong Atlantic State University

Instructor: Y. Daniel Liang | |

Part I: Multiple-Choice Questions: (1 pts each)

A question may have multiple correct answers.

1  How many times is the factorial method in Listing 20.1 invoked for factorial(5)?

A. 6

B. 3

C. 5

D. 4

2  Which of the following statements are true?

A. Recursive methods run faster than non-recursive methods.

B. In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve.

C. A recursive method can always be replaced by a non-recursive method.

D. Recursive methods usually take more memory space than non-recursive methods.

3  Fill in the code in Comparable______ c = new Date();

A.

B.

C.

D.

4  To declare an interface named A with two generic types, use

A. public interface A(E, F) { ... }

B. public interface A { ... }

C. public interface A { ... }

D. public interface A(E) { ... }

5  To create a list to store integers, use

A. ArrayList list = new ArrayList();

B. ArrayList list = new ArrayList();

C. ArrayList list = new ArrayList();

D. ArrayList list = new ArrayList();

6  Suppose List list = new ArrayList. Which of the following operations are correct?

A. list.add(new Integer(100));

B. list.add(new ArrayList());

C. list.add("Red");

D. list.add(new java.util.Date());

7  Which of the following is correct to sort the elements in a list lst?

A. new LinkedList(new String[]{"red", "green", "blue"})

B. lst.sort()

C. Arrays.sort(lst)

D. Collections.sort(lst)

8  To find a maximum object in an array of strings (e.g., String[] names = {"red", "green", "blue"}), use

A. Arrays.max(names)

B. Collections.max(Arrays.asList(names))

C. Arrays.sort(names)

D. Collections.max(names)

E. None of the above

9  Which method do you use to remove an element from a set or list named x?

A. x.remove(element)

B. x.removes(element)

C. x.delete(element)

D. None of the above

E. x.deletes(element)

10  To create a set that consists of string elements "red", "green", and "blue", use

A. new HashSet(new String[]{"red", "green", "blue"})

B. new LinkedHashSet(Arrays.asList(new String[]{"red", "green", "blue"}))

C. new Set(Arrays.asList(new String[]{"red", "green", "blue"}))

D. new HashSet(Arrays.asList(new String[]{"red", "green", "blue"}))

E. new HashSet({"red", "green", "blue"})

11  Which of the data types below could be used to store elements in their natural order based on the compareTo method.

A. TreeSet

B. Collection

C. HashSet

D. LinkedHashSet

E. Set

12  Which of the following statements are true?

A. The Collection interface is the root interface for manipulating a collection of objects.

B. All interfaces and classes in the Collections framework are declared using generic type in JDK 1.5.

C. The AbstractCollection class is a convenience class that provides partial implementation for the Collection interface.

D. Some of the methods in the Collection interface cannot be implemented in the concrete subclass. In this case, the method would throw java.lang.UnsupportedOperationException, a subclass of RuntimeException.

E. The Collection interface provides the basic operations for adding and removing elements in a collection.

Part II:

1. (2 pts) Write a recursive mathematical definition for computing [pic] for a positive integer n.

2. (2 pts) Write a recursive mathematical definition for computing [pic] for a positive integer.

3. (2 pts) Show the output of the following program:

[pic]

4. (2 pts) Are there any compile errors in (a) and (b)?

[pic]

5. (6 pts) Suppose that set1 is a collection that contains the strings "red", "yellow", "green", and that set2 is another collection that contains the strings "red", "yellow", "blue". Answer the following questions: (All the questions are independent)

• What are set1 and set2 after executing set1.addAll(set2)?

• What are set1 and set2 after executing set1.add(set2)?

• What are set1 and set2 after executing set1.removeAll(set2)?

• What are set1 and set2 after executing set1.remove(set2)?

• What are set1 and set2 after executing set1.retainAll(set2)?

• What is set1 after executing set1.clear()?

6. (2 pts) Show the printout of the following code:

public class Test {

public static void main(String[] args) {

Map map = new LinkedHashMap();

map.put("123", "John Smith");

map.put("111", "George Smith");

map.put("123", "Steve Yao");

map.put("222", "Steve Yao");

System.out.println("(1) " + map);

System.out.println("(2) " + new TreeMap(map));

}

}

Part III: Complete the following program.

1. (10 pts) (Summing the digits in an integer using recursion) Write a recursive method that computes the sum of the digits in an integer. Use the following method header:

public static int sumDigits(long n)

For example, sumDigits(234) returns 2 + 3 + 4 = 9. Hint: sumDigits(234) = sumDigits(23) + 4

2. (10 pts) (Displaying words) Write a program that reads words from a text file and displays words in ascending order. (If two words are the same, display only one). Pass the text filename from the command line.

Keys:

2. A

4. BCD

6. D

7. C

9. A

12. C

13. D

14. B

15. A

16. BD

17. A

20. ABCDE

How many times is the factorial method in Listing 20.1 invoked for factorial(5)?

A. 6

B. 3

C. 5

D. 4

Key:A

#

Which of the following statements are true?

A. Recursive methods run faster than non-recursive methods.

B. In some cases, however, using recursion enables you to give a natural, straightforward, simple solution to a program that would otherwise be difficult to solve.

C. A recursive method can always be replaced by a non-recursive method.

D. Recursive methods usually take more memory space than non-recursive methods.

Key:BCD

#

Fill in the code in Comparable______ c = new Date();

A.

B.

C.

D.

Key:D

#

To declare an interface named A with two generic types, use

A. public interface A(E, F) { ... }

B. public interface A { ... }

C. public interface A { ... }

D. public interface A(E) { ... }

Key:C

#

To create a list to store integers, use

A. ArrayList list = new ArrayList();

B. ArrayList list = new ArrayList();

C. ArrayList list = new ArrayList();

D. ArrayList list = new ArrayList();

Key:A

#

Suppose List list = new ArrayList. Which of the following operations are correct?

A. list.add(new Integer(100));

B. list.add(new ArrayList());

C. list.add("Red");

D. list.add(new java.util.Date());

Key:C

#

Which of the following is correct to sort the elements in a list lst?

A. new LinkedList(new String[]{"red", "green", "blue"})

B. lst.sort()

C. Arrays.sort(lst)

D. Collections.sort(lst)

Key:D

#

To find a maximum object in an array of strings (e.g., String[] names = {"red", "green", "blue"}), use

A. Arrays.max(names)

B. Collections.max(Arrays.asList(names))

C. Arrays.sort(names)

D. Collections.max(names)

E. None of the above

Key:B

#

Which method do you use to remove an element from a set or list named x?

A. x.remove(element)

B. x.removes(element)

C. x.delete(element)

D. None of the above

E. x.deletes(element)

Key:A

#

To create a set that consists of string elements "red", "green", and "blue", use

A. new HashSet(new String[]{"red", "green", "blue"})

B. new LinkedHashSet(Arrays.asList(new String[]{"red", "green", "blue"}))

C. new Set(Arrays.asList(new String[]{"red", "green", "blue"}))

D. new HashSet(Arrays.asList(new String[]{"red", "green", "blue"}))

E. new HashSet({"red", "green", "blue"})

Key:BD

#

Which of the data types below could be used to store elements in their natural order based on the compareTo method.

A. TreeSet

B. Collection

C. HashSet

D. LinkedHashSet

E. Set

Key:A

#

Which of the following statements are true?

A. The Collection interface is the root interface for manipulating a collection of objects.

B. All interfaces and classes in the Collections framework are declared using generic type in JDK 1.5.

C. The AbstractCollection class is a convenience class that provides partial implementation for the Collection interface.

D. Some of the methods in the Collection interface cannot be implemented in the concrete subclass. In this case, the method would throw java.lang.UnsupportedOperationException, a subclass of RuntimeException.

E. The Collection interface provides the basic operations for adding and removing elements in a collection.

Key:ABCDE

5. (6 pts) Suppose that set1 is a set that contains the strings "red", "yellow", "green", and that set2 is another set that contains the strings "red", "yellow", "blue". Answer the following questions: (All the questions are independent)

• What are set1 and set2 after executing set1.addAll(set2)?

set1: ["red", "yellow", "green", "blue"]

set2: ["red", "yellow", "blue"]

• What are set1 and set2 after executing set1.add(set2)?

set1: ["red", "yellow", "green", ["red", "yellow", "blue"]]

set2: ["red", "yellow", "blue"]

• What are set1 and set2 after executing set1.removeAll(set2)?

set1: ["green"]

set2: ["red", "yellow", "blue"]

• What are set1 and set2 after executing set1.remove(set2)?

set1: ["red", "yellow", "green"]

set2: ["red", "yellow", "blue"]

• What are set1 and set2 after executing set1.retainAll(set2)?

set1: ["red", "yellow"]

set2: ["red", "yellow", "blue"]

• What is set1 after executing set1.clear()?

set1: []

1. (10 pts) (Summing the digits in an integer using recursion) Write a recursive method that computes the sum of the digits in an integer. Use the following method header:

public static int sumDigits(long n)

For example, sumDigits(234) returns 2 + 3 + 4 = 9. Hint: sumDigits(234) = sumDigits(23) + 4

public static int sumDigits(long n) {

if (n = 0)

return 0;

else

return n % 10 + sumDigits(n / 10);

}

2. (10 pts) (Displaying words) Write a program that reads words from a text file and displays words in ascending order. (If two words are the same, display only one). Pass the text filename from the command line.

import java.io.*;

import java.util.*;

public class Test {

public static void main(String[] args) throws Exception {

// Boiler-plate code

File file = new File(args[0]);

Scanner input = new Scanner(file);

TreeSet set = new TreeSet();

while (input.hasNext()) {

set.add(input.next());

}

for (String word : set)

System.out.println(word);

}

}

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download