This content can't be printed from the browser. Use Export PDF with Pro for an offline copy.
Question 1
Neri Parcel Rooms tracks locker availability and the distinct locker numbers scanned during each inspection round. The program compares two rounds; its printed results describe lockers scanned only in the earlier round and whether every later-round locker was scanned earlier.
1 import java.util.HashSet;
2 import java.util.Set;
3 public class Inspection {
4 public static void main(String[] args) {
5 Set<Integer> earlier = new HashSet<>(Set.of(1, 3, 5, 7));
6 Set<Integer> later = new HashSet<>(Set.of(3, 7));
7 later.add(3);
8 Set<Integer> missed = new HashSet<>(earlier);
9 missed.removeAll(later);
10 System.out.println(missed.size());
11 System.out.println(earlier.containsAll(later) ? 1 : 0);
12 }
13 }
Each locker number must lead to its current status, either "free" or "occupied". Describe how a HashMap would support this requirement, from initial storage to retrieving the status after a parcel has been collected.
[3]
A scanner may report the same locker several times during a round. Outline why storing the reports in a set makes the set's size a suitable count of distinct lockers.
[2]
Consider the two results printed by the program.
I.
State the first printed result.
[1]
II.
State the second printed result.
[1]
Question 2
Oru Sensorworks tests a small hash table for storing positive sensor identifiers. There are seven locations, numbered from zero; −1 denotes an unused location. The hash function takes the remainder after division by seven, and collisions use linear probing.
1 public class SensorTable {
2 public static void main(String[] args) {
3 int[] table = {-1, -1, -1, -1, -1, -1, -1};
4 int[] keys = {6, 13, 8};
5 for (int key : keys) {
6 int index = key % 7;
7 while (table[index] != -1) {
8 index = (index + 1) % 7;
9 }
10 table[index] = key;
11 System.out.println(index);
12 }
13 }
14 }
Describe how the program chooses a storage location for an identifier when its initial hash location is already occupied. Include what happens at the end of the array.
[3]
The table is later used with six occupied locations and the same capacity. Outline how this higher load factor is likely to affect insertion performance.
[2]
Use the original program, starting with all seven locations unused.
I.
State the index printed when identifier 13 is inserted.
[1]
II.
State the index printed when identifier 8 is inserted.
[1]
Question 3
Vela Toolbank represents equipment awaiting collection using a doubly linked list. Each node stores the number of days an item has been waiting; head and tail identify the ends, and both are null for an empty list.
The following demonstration creates a two-node list.
1 public class CollectionList {
2 static class Node {
3 int days;
4 Node next, previous;
5 Node(int days) { this.days = days; }
6 }
7 static Node head, tail;
8 public static void main(String[] args) {
9 head = new Node(3);
10 tail = new Node(8);
11 head.next = tail;
12 tail.previous = head;
13 System.out.println(tail.previous.days);
14 }
15 }
Construct a static method named countWaiting for the printed class. It receives an integer parameter named limit and returns an integer: the number of nodes whose days value exceeds limit. Begin at tail and follow the backward links. An empty list must give a result of zero.
[5]
A collected item is removed from the front of this list. Describe, without code, a deletion procedure that maintains both end references and the backward links. Include the empty-list and single-node cases.
[5]
Question 4
Aster Seedstore indexes seed batches by unique positive batch numbers in a binary search tree. The program builds an example tree and obtains its smallest batch number using an iterative method. Each subtree obeys the same ordering rule as the complete tree.
1 public class BatchIndex {
2 static class Node {
3 int key;
4 Node left, right;
5 Node(int key) { this.key = key; }
6 }
7 static int smallest(Node root) {
8 if (root == null) { return -1; }
9 Node current = root;
10 while (current.left != null) {
11 current = current.left;
12 }
13 return current.key;
14 }
15 public static void main(String[] args) {
16 Node root = new Node(45);
17 root.left = new Node(27);
18 root.right = new Node(62);
19 root.left.left = new Node(19);
20 root.left.right = new Node(34);
21 root.right.left = new Node(56);
22 System.out.println(smallest(root));
23 }
24 }
Sketch the tree obtained by inserting batch numbers 45, 27, 62, 19, 34 and 56, in that order, into an empty BST. Label the root and distinguish left-child links from right-child links.
[2]
Explain why finding the smallest key in a non-empty BST can be expressed as a recursive process. Refer to the ordering rule and the stopping condition.
[3]
Consider the printed iterative method smallest and a recursive replacement.
I.
State the value printed by the program.
[1]
II.
Construct a static method named smallestRecursive that receives a Node parameter named root and returns an integer. It must match the printed method's behaviour, including returning for an empty tree, but use recursion rather than iteration.
[4]
III.
A much larger BST is formed by inserting batch numbers in strictly decreasing order. Explain a run-time risk of using the recursive replacement rather than the printed iterative method to find the minimum.
[3]
Build a Practice Exam — Computer Science HL
Test your knowledge with a custom paper containing questions from selected topics.
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.