Date | November 2017 | Marks available | 2 | Reference code | 17N.2.HL.TZ0.18 |
Level | HL | Paper | 2 | Time zone | no time zone |
Command term | Outline | Question number | 18 | Adapted from | N/A |
Question
The programming team have decided to replace the array of Item
objects (pl)
and the array of Payment
objects (tables)
with either a linked list or an ArrayList.
The array of Item
objects (pl)
is replaced by priceLL
, an object of the LinkedList library class. The Item
objects can be created, deleted or amended.
The method changePrice()
allows an item, identified by its item code, to have its price changed. All data required by this method are passed as parameters. If the item is not found then an appropriate message is displayed.
Outline one benefit that the use of either of these choices will have over the original array structures.
Construct the method changePrice()
.
Explain how a binary tree structure would allow a more efficient search for the Item
object.
Markscheme
Memory space for the exact number of objects can be assigned;
Whereas the array will (inevitably) waste space/allot more memory than is needed/may run out of allotted memory/there is no need to determine array size;
Award marks as follows, up to [6 max].
Award [1] for correct signature.
Award [1] for correct initialization of the length of the loop/size of the linked list/ Boolean/Iterator object as appropriate to the solution and appropriate message displayed at end;
Award [1] for correct loop.
Award [1] for correct comparison, with or without get
methods.
Award [1] for correct updating, with or without get
methods.
Award [1] for early exit if found.
Award [1] for answer completely correct.
Example 1
public void changePrice(LinkedList<Item> pll, String c,
double newPrice)
{
int i = 0;
boolean found = false;
int size = pll.size();
while (i < size && !found)
{
if (pll.get(i).getCode().equals(c)) // allow “=”
{
pll.get(i).setPrice(newPrice);
found = true;
}
i = i + 1;
}
}
Example 2
public void changePrice(LinkedList<Item> pll, String c,
double newPrice)
{
Iterator<Item> iter = pll.iterator();
boolean found = false;
while (iter.hasNext() && !found)
{
Item current = iter.next();
if (current.getCode().equals(c)) // allow “=”
{
current.setPrice(newPrice);
found = true;
}
}
}
The pl
array/Item
objects could be read into a binary tree;
And placed in order of the Item
code;
(Successive) comparisons between the search item and tree item will reduce the search space by a half (each time);
Which results in a faster search than a linear search/Olog(n)
is better than O(n)
;
As a linear search might have to loop through the whole list;