This content can't be printed from the browser. Use Export PDF with Pro for an offline copy.
Question 1
Brindle Tool Hub keeps tool identification numbers in ascending order and searches them repeatedly. Its developers also test sorting algorithms on small arrays; the following program performs one pass of bubble sort.
1 public class SortTrial {
2 public static void main(String[] args) {
3 int[] durations = {6, 2, 5, 1};
4 for (int index = 0; index < durations.length - 1; index++) {
5 if (durations[index] > durations[index + 1]) {
6 int temporary = durations[index];
7 durations[index] = durations[index + 1];
8 durations[index + 1] = temporary;
9 }
10 }
11 System.out.println(durations[0]);
12 System.out.println(durations[3]);
13 }
14 }
Explain why binary search is a suitable choice, in terms of scalability, for searching the hub's sorted tool identification numbers rather than using linear search.
[3]
Describe the steps of an iterative binary search that receives an ascending array of distinct tool identification numbers and a target number. The method returns the target's index, or -1 if it is absent. Do not write code.
[4]
State the relationship between the two adjacent values that is tested in line 5.
[1]
State the output of the program.
[2]
Construct the static method comparisonBudget, which receives a non-negative integer n and returns the number of value comparisons made by standard selection sort on n elements. Its return type is int.
Model the comparisons using nested loops: for each position except the last, selection sort compares its current candidate with every later element. Do not sort any data or use a formula for the total. Assume the result fits in an int.
[5]
Question 2
Mavren Dispatch stores parcel-bay codes in a list called CODES. The flowchart in (Figure 1) searches for TARGET and outputs the index of its first occurrence, or -1 if it is absent. List indices start at 0. provides the trace table.
State one requirement concerning the order of CODES before binary search can be used.
[1]
Copy and complete the trace table in for the flowchart in , using CODES = [31, 18, 44, 27, 52, 16] and TARGET = 27. Each row records one evaluation of a test: write that test's result in its column, write a variable's value only when it changes, and record the output on the row where it is produced.
[3]
State the worst-case time complexity of the flowchart in , using Big O notation, where n is the number of codes.
[1]
The dispatch centre also maintains a non-empty list of distinct parcel-bay codes sorted in ascending order. Construct an algorithm, as numbered steps in structured English, that uses binary search to locate TARGET in this list. The algorithm must output its index if found, or -1 if absent. Do not write code.
[5]
An array initially contains [31, 18, 44, 27, 52, 16]. Selection sort is applied in ascending order, placing the smallest remaining value at the start of the unsorted region on each pass. Sketch the array immediately after the first complete pass.
[2]
The dispatch centre wants to use bubble sort on lists that may already be sorted. Describe the steps of an ascending bubble sort that stops as soon as a complete pass makes no swaps. Do not write code.
[3]
Question 3
Vela Grove Studio develops illuminated artworks. Its software generates branching patterns and calculates totals from recorded energy readings.
pattern-generation process draws a segment of length 8 units. Whenever a segment is longer than 2 units, the process applies the same drawing rule to two new segments, each half its length, attached to its endpoint. Segments of length 2 units have no further branches.
Sketch the complete branching structure produced. Label every segment with its length.
[2]
Explain why the pattern-generation process in part (a) is recursive.
[3]
The following program calculates a total from an array of non-negative energy readings. The parameter start is a valid array index or is equal to the array's length.
1 public class EnergyTotal {
2 static int totalFrom(int[] readings, int start) {
3 int total = 0;
4 for (int index = start; index < readings.length; index++) {
5 total = total + readings[index];
6 }
7 return total;
8 }
9 public static void main(String[] args) {
10 int[] readings = {3, 8, 0, 4};
11 System.out.println(totalFrom(readings, 1));
12 }
13 }
I.
State the output of the program.
[1]
II.
Construct a recursive replacement for totalFrom, with the same parameters and return type. It must return the sum of the readings from index start to the end of the array, or 0 when start equals the array's length. Assume that the total fits in an int.
Use no loops and make at most one recursive call in each invocation.
[4]
III.
The studio may process a very large array starting at index 0. Explain why the recursive replacement could fail at run time even when the iterative method completes successfully and the total fits in an int.
[3]
Question 4
Orin Parcel Hub orders parcels by their priority values using quicksort. Its software also determines how many decimal digits are needed to display a positive parcel reference number.
The priority values, in their initial order, are 8, 3, 7, 2, 6, 1, 5.
One partition uses the final value, 5, as its pivot. This partition places all values smaller than the pivot first, followed by the pivot, followed by all values greater than the pivot. Within each of the two groups, the original relative order is preserved.
Sketch the array immediately after this partition. Label the pivot. Do not sort either group.
[2]
Explain why quicksort is well suited to a recursive solution.
[3]
The following iterative method receives a positive integer reference and returns its number of decimal digits. Integer division discards any remainder.
1 public class ReferenceDisplay {
2 static int digitCount(int reference) {
3 int count = 0;
4 while (reference > 0) {
5 count = count + 1;
6 reference = reference / 10;
7 }
8 return count;
9 }
10 public static void main(String[] args) {
11 System.out.println(digitCount(4932));
12 }
13 }
I.
State the output of the program.
[1]
II.
Construct a recursive replacement for digitCount, receiving one positive integer reference and returning its number of decimal digits as an integer.
Use integer arithmetic, no loops and at most one recursive call in each invocation.
[4]
III.
The hub performs this digit-counting operation millions of times on short reference numbers. A programmer claims that replacing the loop with recursion will make it faster. Explain why this claim is not justified.
[3]
Build a Practice Exam — Computer Science HL
Test your knowledge with a custom paper containing questions from selected topics.
Question 5
Fenmere Seed Store receives a short, unsorted batch of packet codes each morning and makes one search before archiving the batch. A separate, ascending catalogue is used for repeated searches; the following program tests a search of that catalogue.
1 public class CatalogueTrial {
2 static int locate(int[] codes, int target) {
3 int low = 0;
4 int high = codes.length - 1;
5 int comparisons = 0;
6 while (low <= high) {
7 int middle = (low + high) / 2;
8 comparisons++;
9 if (codes[middle] == target) {
10 return middle;
11 } else if (codes[middle] < target) {
12 low = middle + 1;
13 } else {
14 high = middle - 1;
15 }
16 }
17 return -1;
18 }
19 public static void main(String[] args) {
20 int[] codes = {3, 7, 11, 16, 22, 29};
21 System.out.println(locate(codes, 22));
22 System.out.println(locate(codes, 12));
23 }
24 }
Explain why linear search is a suitable choice for the single search of each morning's batch, rather than sorting the batch to use binary search.
[3]
Describe the steps of a selection sort that rearranges a batch of packet codes into ascending order in its existing array. Do not write code.
[4]
State the quantity recorded by comparisons during one call of the printed method.
[1]
State the output of the program.
[2]
Construct the static method findLast, which receives an integer array batch and an integer target. Packet codes may be repeated. The method must use linear search and return the index of the last occurrence of the target, or -1 if it is absent. Its return type is int. The array may be empty.
[5]
Question 6
Orwick Repair Desk maintains short arrays of estimated repair times that are often already in ascending order. Before choosing its sorting and searching methods, it tests the number of target comparisons made by a linear search.
1 public class SearchTrial {
2 static int checks(int[] times, int target) {
3 int comparisons = 0;
4 for (int index = 0; index < times.length; index++) {
5 comparisons++;
6 if (times[index] == target) {
7 return comparisons;
8 }
9 }
10 return comparisons;
11 }
12 public static void main(String[] args) {
13 int[] times = {14, 8, 21, 5, 17};
14 System.out.println(checks(times, 21));
15 System.out.println(checks(times, 9));
16 }
17 }
Explain why bubble sort with an early-exit check can be preferable to standard selection sort for the desk's short arrays, which are often already sorted.
[3]
Describe the steps you would use to determine the worst-case time complexity and additional space complexity of checks for an input containing n repair times. Exclude storage for the input array. Do not write code.
[4]
State what the condition in line 6 tests.
[1]
State the output of the program.
[2]
Construct the static method sortTimes, which receives an integer array times and sorts it into ascending order using bubble sort. It must stop early if a complete pass makes no swaps. The array may be empty or contain one element. The method has return type void and must modify the existing array.
The Arrays.sort() method must not be used.
[5]
The Ultimate All-in-One
IB Platform
All content on this website has been developed independently from and is not endorsed by the International Baccalaureate Organization. International Baccalaureate and IB are registered trademarks owned by the International Baccalaureate Organization.