Markscheme: Practice Paper 2, HL, set 1

Complete the trace table for this Python code. A school library keeps its book IDs in ids, sorted from smallest to largest. This code is a binary search for the book with ID 150. // divides and keeps only the whole number part, and found stays -1 until the book is found. Then answer the question below the table. [4]

How many positions of ids did the loop look at in all, including the one where it found 150?

A school library gives every book a whole-number ID. The IDs are kept in a list (an array in Java) called ids, sorted from smallest to largest, with no ID appearing twice.

Write a function that uses a binary search to return the position (the index) of target in ids, or -1 if no book has that ID. Positions start at 0.

1. Keep two positions, low and high, for the part of the list that could still hold target. They start at the first and the last position.
2. Look at the middle position, (low + high) divided by 2, rounded down. If the ID there is target, return that position. If it is smaller than target, search only the part after it; if it is larger, search only the part before it.
3. When low has passed high, nothing is left to search, so return -1.
4. ids can be empty, and holds at most 10000 IDs, each between 1 and 1000000.
5. Write the search yourself. The shortcuts listed with this question are not allowed.

The tests check only the number your function returns, so they cannot tell a binary search from a linear one. In the exam, a linear search would not earn the marks for this part.

A school library keeps the IDs of its 1000 books in a list (an array in Java), and a librarian looks up one ID at a time.

(a) Explain why a binary search only works if the IDs are sorted. [2]

(b) State the largest number of IDs a linear search would have to look at to find one ID, and the largest number a binary search would have to look at, for the 1000 books. [2]

[4]

A school library program has a Book class. Here it is in Python and in Java.

class Book:
    def __init__(self, title, copies):
        self.title = title
        self.__available = copies

    def get_available(self):
        return self.__available

    def borrow(self):
        if self.__available > 0:
            self.__available -= 1
            return True
        return False

public class Book {
    private String title;
    private int available;

    public Book(String title, int copies) {
        this.title = title;
        this.available = copies;
    }

    public int getAvailable() {
        return available;
    }

    public boolean borrow() {
        if (available > 0) {
            available--;
            return true;
        }
        return false;
    }
}

(a) Identify the method in Book that is an accessor. [1]

(b) The number of available copies is private (in Python, its name starts with two underscores). Explain why it is private, and why code outside the class changes it only by calling borrow. [3]

(c) Another part of the program runs Book("Dune", 2) (in Java, new Book("Dune", 2)) and Book("Emma", 1). Distinguish between the class Book and the objects these lines create. [2]

[6]

The school library's Book class now also counts how many books have been created. Here it is in Python and in Java, with code that uses it. In Java the last part runs inside a main method.

class Book:
    count = 0

    def __init__(self, title, copies):
        self.title = title
        self.__available = copies
        Book.count += 1

    def get_available(self):
        return self.__available

    def borrow(self):
        if self.__available > 0:
            self.__available -= 1
            return True
        return False

b1 = Book("Dune", 1)
b2 = Book("Emma", 2)
print(b1.borrow())
print(b1.borrow())
print(b2.borrow())
print(b2.get_available())
print(Book.count)

public class Book {
    private static int count = 0;
    private String title;
    private int available;

    public Book(String title, int copies) {
        this.title = title;
        this.available = copies;
        count++;
    }

    public int getAvailable() {
        return available;
    }

    public boolean borrow() {
        if (available > 0) {
            available--;
            return true;
        }
        return false;
    }

    public static int getCount() {
        return count;
    }
}

// in main
Book b1 = new Book("Dune", 1);
Book b2 = new Book("Emma", 2);
System.out.println(b1.borrow());
System.out.println(b1.borrow());
System.out.println(b2.borrow());
System.out.println(b2.getAvailable());
System.out.println(Book.getCount());

(a) State the five lines of output, in order. [3]

(b) Explain why the last line of output is 2 and not 1. [2]

[5]

The school library's Book class has a constructor, an accessor get_available (in Java, getAvailable) and a method borrow that takes one copy if one is available and returns whether it did. Reference books, such as atlases, must stay in the library, so a programmer adds this subclass. Here it is in Python and in Java.

class ReferenceBook(Book):
    def __init__(self, title, copies, room):
        super().__init__(title, copies)
        self.room = room

    def borrow(self):
        return False

shelf = [Book("Dune", 1),
         ReferenceBook("Atlas", 3, "R2")]
for b in shelf:
    print(b.borrow())

public class ReferenceBook extends Book {
    private String room;

    public ReferenceBook(String title,
            int copies, String room) {
        super(title, copies);
        this.room = room;
    }

    @Override
    public boolean borrow() {
        return false;
    }
}

// in main
ArrayList<Book> shelf = new ArrayList<>();
shelf.add(new Book("Dune", 1));
shelf.add(new ReferenceBook("Atlas", 3, "R2"));
for (Book b : shelf) {
    System.out.println(b.borrow());
}

(a) Outline what ReferenceBook inherits from Book, and what it adds. [2]

(b) The loop prints True then False (in Java, true then false). Explain how polymorphism produces this output, although the loop makes the same call each time. [3]

[5]

A school library keeps a Book object for each title. Its mutator methods refuse a change that would make the number of copies on the shelf impossible. Write a function that works out the same thing from simple data: it is given how many copies of a book the library owns, all on the shelf at the start, and a list (an array in Java) of actions, carried out in order. It returns how many copies are on the shelf after the last action.

1. "borrow" takes one copy off the shelf, but only if at least one copy is there. Otherwise it is refused and changes nothing.
2. "return" puts one copy back, but only if fewer than total copies are on the shelf. Otherwise it is refused and changes nothing.
3. Any other text, such as "renew", changes nothing. Capital letters matter: "Borrow" is not "borrow".
4. total is a whole number from 0 to 50. There are at most 50 actions, and the list can be empty.

Only the number your function returns is checked.

A school's online code editor sends students' programs to one shared printer in the computer room, and it has an undo button that takes back the student's most recent edits, one at a time.

(a) Identify whether a stack or a queue should hold the print jobs waiting for the printer. [1]

(b) Explain why that ADT suits the print jobs. [2]

(c) Identify and explain which ADT suits the undo button. [2]

[5]

Complete the trace table for this Python code. A school code editor checks brackets using stack as a stack: append pushes onto the top (the right-hand end) and pop() removes the top item and gives it back. The stack column holds the whole stack in square brackets, like ["("], after each change. Then answer the question below the table. [4]

The same code is run with text = "(a))". What happens when the loop reaches the last character, and why?

A school's online code editor warns students when the brackets in a line of code do not match up. Write a function that returns whether the brackets in a piece of text are balanced. Use a list (an ArrayList in Java) as a stack.

1. The brackets are ( with ), [ with ], and { with }. Every other character is ignored.
2. The brackets are balanced when every closing bracket closes the most recent bracket still open, and that bracket is of the same kind. So ([]) is balanced, and ([)] is not.
3. A closing bracket with no bracket open makes the text unbalanced.
4. A bracket still open at the end makes the text unbalanced.
5. Text with no brackets at all, including empty text, is balanced.
6. The text has at most 100 characters, all of them printable ASCII. Write the stack yourself: the shortcuts listed with this question are not allowed.

Only the True or False (in Java, true or false) your function returns is checked.

The school code editor's bracket checker keeps its stack in a Python list (in Java, an ArrayList). The checker only ever uses the stack through three operations: push, pop, and a test for whether the stack is empty. A developer wants to change the stack so that it is stored as a singly linked list instead, with the head of the list as the top of the stack.

(a) Describe how push and pop would work on this singly linked list. [3]

(b) Explain why the bracket-checking code would not need to change, as long as push, pop and the empty test still do the same job. [2]

[5]

An online puzzle game keeps its players' scores in a list (an array in Java) called scores. This recursive function adds up the first n scores.

def total(scores, n):
    if n == 0:
        return 0
    return scores[n - 1] + total(scores, n - 1)

static int total(int[] scores, int n) {
    if (n == 0) {
        return 0;
    }
    return scores[n - 1]
        + total(scores, n - 1);
}

(a) Identify the base case of the function. [1]

(b) The function is called as total with scores [40, 25, 10, 5] and n = 3. State the value it returns. [1]

(c) State how many times total is called in (b), counting the first call. [1]

[3]

An online puzzle game keeps the scores of its players in a list (an array in Java) called scores. The leaderboard shows them from highest to lowest.

Write a function that uses a selection sort to put the scores in order from highest to lowest, and returns the sorted list.

1. On each pass, find the position of the highest score in the part of the list not yet sorted, then swap it with the first score of that part.
2. Equal scores stay in the list as many times as they appeared.
3. scores can be empty. Scores are whole numbers between -1000 and 100000 (a score can be below 0 after penalties).
4. You may change scores and return it, or return a new list.
5. Write the sort yourself. The shortcuts listed with this question are not allowed.

The tests check only the list your function returns, so they cannot tell a selection sort from another sort. In the exam, a different sort would not earn the marks for this part.

The puzzle game keeps the scores of its players in a list (an array in Java) called scores, in the order the games were played.

Write a recursive function that returns the highest score among the first n scores, that is scores[0] to scores[n - 1].

1. Base case: when n is 1, the highest of the first score is scores[0].
2. Recursive case: find the highest of the first n - 1 scores by calling the function itself, then compare that with scores[n - 1] and return the larger.
3. n is always between 1 and the length of scores, and scores holds at most 500 scores. Scores after position n - 1 are not looked at.
4. Scores are whole numbers between -1000 and 100000, so a score can be below 0.
5. Write the comparison yourself. The shortcuts listed with this question are not allowed.

The tests check only the number your function returns, so they cannot tell a recursive answer from one that uses a loop. In the exam, a loop would not earn the marks for this part.

The puzzle game finds the highest score among the first n scores with a recursive function, best_score(scores, n), which calls itself with n - 1 until n is 1. A programmer suggests replacing it with a loop that walks through the scores once and remembers the highest seen so far.

Compare the recursive best_score with the loop version, referring to time, memory and clarity. [4]