| 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;
Examiners report
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.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. -
20N.2.HL.TZ0.17a:
Construct the
staffRemoveCarmethod. -
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
