| Date | November 2020 | Marks available | 6 | Reference code | 20N.2.HL.TZ0.17 |
| Level | HL | Paper | 2 | Time zone | no time zone |
| Command term | Construct | Question number | 17 | Adapted from | N/A |
Question
A new parking service has been introduced: staff will park the car for the driver and then return it later when the driver wants to leave. This service will use a narrow parking area surrounded on three sides by walls, where any cars behind the required car must be reversed out. For example, car X00000011 was the first vehicle to be parked, so to remove it from the parking area, the other five cars, starting with X00000123, will need to be removed. The cars are then returned starting with car X00000010.
Figure 5: Cars parked in the parking area
The class Stack, which contains the Vehicle objects, has the following methods:
The method staffRemoveCar will remove a vehicle with a specified registration plate from the parking area (you can assume the vehicle is in the parking area):
public static void staffRemoveCar(Stack stack, String reg){
Stack temp = new Stack();
//add code here
}
Construct the staffRemoveCar method.
A stack can be implemented using an array or a singly linked list.
Compare the use of these two data structures for creating a stack.
Markscheme
Award [6 max].
Award [1] for looping around the main stack using isEmpty() method;
Award [1] for using "while" loop in both loops (note: not a "do while"!);
Award [1] for breaking out of outer loop when car is removed and other cars are replaced;
Award [1] for correctly removing cars before target car is found;
Award [2] for replacing cars in same order by popping off temporary stack;
Example 1:
public void staffRemoveCar(Stack stack, String reg) {
Stack temp = new Stack();
while (!stack.isEmpty()) {
Vehicle v = (Vehicle) stack.pop();
if (v.getRegistration().equals(reg)) {
// correct car is now removed
// return others
while (!temp.isEmpty()) {
stack.push(temp.pop());
}
break; // don't keep repeating
}
temp.push(v);
}
}
Example 2:
public static void staffRemoveCar(Stack<Vehicle> stack, String reg)
{ Stack<Vehicle> temp = new Stack<Vehicle>();
boolean found = false;
while (!found && !stack.isEmpty())
{ Vehicle curr = stack.pop();
found = curr.getRegistration().equals(reg);
if (!found) temp.push(curr);
}
while (!temp.isEmpty()) stack.push(temp.pop());
}
Award [4 max].
Award [1] for an initial valid comparison and [1] for a valid expansion.
Memory
Linked lists can deal with memory issues more efficiently than arrays;
Arrays are static so will have a maximum size and cannot grow beyond that;
Memory will be allocated for maximum size at instantiation so while it is not full memory is wasted Links are dynamic and can add/remove memory as required- no memory is wasted;
Implementation
No particular advantage is gained by the use of either structure;
As additions and removals (push and pop) work on one end of the stack, navigation speed (i.e. O1) is not very helpful; Linked lists can adjust the pointer at the end of the list (can use a tail pointer) so slow navigation is not an issue;
Errors
The use of arrays is more likely to lead to run-time errors;
As arrays can reach their maximum limit whilst linked lists are only limited in size by the specifications of the CPU;
Examiners report
There were many full marks gained for this algorithm with students making correct use of the various stack methods.
Most alluded to the memory issues regarding the two data structures, but too many dealt incorrectly with issues dealing with traversing the structures, which were largely irrelevant as access was only needed for the top of the stack.
Syllabus sections
- 17N.2.HL.TZ0.19a: Explain why recursion is a suitable tool to use when performing this check.
- 18N.2.HL.TZ0.16d.i: Define the term recursion.
-
18N.2.HL.TZ0.16d.ii:
Trace the call
process(runway1,0)given the diagram ofrunway1as drawn above. Copy and complete the following table.
-
18M.2.HL.TZ0.19a:
Identify two essential features of a recursive algorithm.
-
19M.2.HL.TZ0.17a:
Define the term object reference.
-
19M.2.HL.TZ0.17d:
Using the data provided in the diagram, trace the call
recursive(0,'F'), clearly showing the levels of recursion. -
19M.2.HL.TZ0.17e:
Outline one reason why the use of a recursive method may be inappropriate for linked lists.
- 18M.2.HL.TZ0.18a: Outline why a linked list structure has been chosen for allCustomers.
-
18M.2.HL.TZ0.19b:
Copy and complete the following table to show the output when the method is called by:
recursionEx(3);
-
19M.2.HL.TZ0.17b:
Outline one reason why a linked list may be more suitable than a binary tree in this particular situation.
-
19M.2.HL.TZ0.17c.i:
Construct the code needed to instantiate an object
guestsof theLinkedListclass. -
17N.2.HL.TZ0.18a:
Outline one benefit that the use of either of these choices will have over the original array structures.
-
17N.2.HL.TZ0.18c:
Explain how a binary tree structure would allow a more efficient search for the
Itemobject. -
17N.2.HL.TZ0.19b:
The method
palindrome()is called byboolean t = palindrome(word);
wherewordis a String variable.Without writing code, describe the recursive method
palindrome()that returns whether or not a word is a palindrome. -
18N.2.HL.TZ0.16a:
Outline an advantage of using a library.
-
18N.2.HL.TZ0.16b:
Evaluate the use of dynamic linked lists to static arrays when managing arriving airplanes.
-
19N.2.HL.TZ0.17a:
Define the term object reference.
-
19N.2.HL.TZ0.17b:
Using object references, construct the method
public Cart removeFirst()that removes the firstCartNodeobject fromlist. The method must return theCartobject in that node ornulliflistis empty. -
20N.2.HL.TZ0.16c:
Identify the steps that would be involved in taking the data from this two-dimensional array and creating a binary search tree.
-
20N.2.HL.TZ0.17b:
A stack can be implemented using an array or a singly linked list.
Compare the use of these two data structures for creating a stack. -
19N.2.HL.TZ0.17c:
Sketch the linked list
listafter running the following code fragment wherecart1, cart2, cart3, cart4andcart5have been instantiated as objects of the classCart.POSlist queueList = new POSlist()
queueList.addLast(cart2);
queueList.addLast(cart1);
queueList.addLast(cart4);
queueList.removeFirst();
queueList.addLast(cart5);
queueList.addLast(cart3);
queueList.removeFirst(); -
18N.2.HL.TZ0.16c:
Sketch the resulting linked list when an airplane with ID RO225, STA 12:05 and delay 0 is added to this list.
-
19N.2.HL.TZ0.17f:
Explain the importance of using coding style and naming conventions when programming.
-
19M.2.HL.TZ0.17c.ii:
Construct the code for the method
penultimate()that returns the second to last element in the linked listguests. You may assume thatguestsis locally accessible. -
18M.2.HL.TZ0.19d:
Identify three features which should be included in either program code or UML diagrams to help programmers understand and modify programs in the future.
-
19N.2.HL.TZ0.17d:
Outline one feature of the abstract data structure queue that makes it unsuitable to implement customers waiting in line.
-
17N.2.HL.TZ0.18b:
Construct the method
changePrice(). -
18M.2.HL.TZ0.19c:
Explain what would happen if the method was called by
recursionEx(-3). -
20N.2.HL.TZ0.16b:
Outline why searching for the registration plate in a binary tree would be faster than looking for it in the two-dimensional array.
-
18M.2.HL.TZ0.18b:
Construct the method
goldMails()that will return anArrayListcontaining the email addresses of all current “Gold” members. You should make use of any previously defined methods. -
19M.2.HL.TZ0.17f:
Due to unforeseen circumstances, schools may cancel their participation in an event at the last minute. Therefore, a method is needed to remove all the visiting students of one school from the linked list
guests.Construct the method
removeSchoolthat takes the name of a school as parameter and removes all students of that school from the listguests. -
19N.2.HL.TZ0.17e:
Using object references, construct the method
public Cart leaveList(int n)that removes the nthCartNodeobject fromlist. The method must return theCartobject in that node.You may assume that the nth
CartNodeobject exists in the list.
You may use any method declared or developed. -
18N.2.HL.TZ0.16e:
In case of bad weather it is possible that one of the runways has to be closed and the two linked lists (
runway1andrunway2) need to be merged using a methodmergeLists()into one new linked listrunway.Construct the method
public LinkedList<Arrival> mergeLists()that merges the two sorted linked lists in to one sorted linked listresultwhich needs to be returned. You may assume thatrunway1andrunway2are accessible to the method and do not need to be passed. The original two lists are allowed to becomenullas a result of the merging.In answering this question, you may use the following methods from the JETS
LinkedListclass, in addition to any method provided or developed in this exam paper.addFirst(<object>) // adds the object at the head of the list
addLast(<object>) // adds the object at the tail of the list
getFirst() // returns the head object in the list
getLast() // returns the tail object in the list
removeFirst() // removes and returns the head object
removeLast() // removes and returns the tail object
size() // returns the number of objects in the list
isEmpty() // returns true if the list is empty
