AP Computer Science A Quarterly Exam

Which sorting algorithm repeatedly finds the lowest item from a portion of a list and swaps it with the item at index?

• linear sort

• selection sort

• insertion sort

• sequential sort

Which sorting algorithm sequentially removes an item from a list and adds it back to the list in the appropriate position relative to the previous items in the list?

• sequential sort

• selection sort

• insertion sort

• mergesort

Which algorithm uses a temporary array during the sorting process?

• selection sort

• insertion sort

• mergesort

• binary search

Given the following code segment: public static int whatzOutput(int x) { if (x == 0) { return(x); } else { return(whatzOutput(x-1)); } } Which is displayed when whatzOutput(-1) is called?

• 0

• -1

• -2

• No value is returned because this call results in infinite recursion.

Which algorithms take a divide and conquer approach?

• I. Selection Sort

• II. Merge Sort

• III. Quick Sort

• IV. Bubble Sort

Which algorithms have a running time of n²?

• a. I and II only

• I. selection sort

• IV. binary search

• III. mergesort

• II. insertion sort

Which algorithms are implemented recursively?

• a. I and II only

• I. selection sort

• III. mergesort

• II. insertion sort

• IV. binary search

Which elements would be checked in a search for 99 in an array that stores 3, 12, 23, 56, 78, 99 using the binary search?

• a. 23, 78, and 99

• b. 99 only

• c. 56 and 99

• d. 3, 12, 23, 56, 78, and 99

What value is returned by the call something(4,6)? __________

Given the input line ABCD and 0, what does the following method print? public void processLine(String str, int pos) //precondition: str = "ABCD", pos=0 { if (pos < str.length) { int i; for (i=0; i<=pos; i++) { System.out.print(str.charAt(i)); } processLine(str, pos+1); } }

• a. ABBCCCDDDDDDDDDDDCCCCBBA

• b. ABBCCCDDDDD

• c. ABCDCBA

• d. AABABCABCDABCABCABCABA