Name:_______________________



Name:_______________________

Covers

50 min |CSCI 2410 Data Structures and Algorithms

Armstrong Atlantic State University

Instructor: Y. Daniel Liang | |

Part I:

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

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

[pic]

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

[pic]

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

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

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

}

}

6. (1 pt) Show the time complexity of the following program:

for (int k = 0; k < 10; k++) {

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

System.out.print('*');

}

}

}

7. (3 pt) Design an efficient O(logn) time algorithm for computing [pic]. (Describe it using a pseudo code)

8. (2 pts) Add the elements 40, 135, 9, 11, 3, 102, into a heap in this order. Draw the final heap.

9. (2 pts) Given the following heap, show the resulting heap after removing 62 from the heap.

[pic]

Part II: Complete the following program.

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

Part III: Multiple Choice Questions: (1 pts each)

(Take the multiple-choice questions online from LiveLab before midnight today. Log in and click Take Instructor Assigned Quiz. You have to take it before it is due. You have to submit it within 30 minutes.)

Part I:

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

F(n) = 1; n = 1

F(n) = n + F(n-1); n > 1

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

[pic]

Sum is 15

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

[pic]

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

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: []

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

}

}

1) [[123, "Steve Yao"], [111, "George Smith"], [222, "Steve Yao"]]

2) [[111, "George Smith"], [123, "Steve Yao"], [222, "Steve Yao"]]

6. (1 pt) Show the time complexity of the following program:

for (int k = 0; k < 10; k++) {

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

System.out.print('*');

}

}

}

O(n2)

7. (3 pt) Design an efficient O(logn) time algorithm for computing [pic]. (Describe it using a pseudo code)

double result = a;

int i = 1;

while (i ................
................

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

Google Online Preview   Download