| Date | November 2020 | Marks available | 3 | Reference code | 20N.2.HL.TZ0.16 |
| Level | HL | Paper | 2 | Time zone | no time zone |
| Command term | Outline | Question number | 16 | Adapted from | N/A |
Question
A single parking space that holds one car can be used to hold two motorbikes. The programmer has decided to use a two-dimensional array to create a map of the parking area.
Vehicle parkingSpaces[][] = new Vehicle[2][200];
Note: m and c have been used to show where motorbikes and cars are parked.
Police have requested a way of searching the parking area for vehicles with a specified registration plate, and a binary tree has been suggested.
Identify one advantage of using a two-dimensional array for this purpose.
Identify one disadvantage of using a two-dimensional array for this purpose.
Outline why searching for the registration plate in a binary tree would be faster than looking for it in the two-dimensional array.
Identify the steps that would be involved in taking the data from this two-dimensional array and creating a binary search tree.
Markscheme
Award [1 max].
Faster to access (i.e. O1 instead of On);
Arrays take less memory than lists (as they do not store pointers);
Mirrors real life situation;
Award [1 max].
Static, therefore memory wasted when not being fully utilised;
Inability to grow, should further spaces be added, i.e. If Parking area grows;
Award [3 max].
The array would need to be searched using a linear search which is inefficient O(n) whereas a binary search is much more efficient O(log n);
A linear search for a car in this parking area could require a maximum of 200 comparisons (i.e. it would look at the first row of every column) whereas a binary search would only require 8 (i.e. log 200 base 2);
A linear search for a motorbike in this parking area would require a maximum of 400 comparisons (i.e. it would need to look at both rows of every column) whereas a binary search would only require 7 (log 100 base 2);
In a binary search, each comparison would eliminate half of the remaining possible matches, whereas in a linear search it only eliminates 1;
A binary search has the registration plate as its key and therefore it doesn’t require accessing the field of the vehicle object for each comparison, whereas in a linear search, each comparison would be slower because it would require getting the vehicle object’s registration field using an accessor method;
A binary search is always faster than a linear search on a large data set. As the police may be searching for many cars and in many parking areas, their searches will be on large set of data;
Award [5 max].
Create a binary tree to store vehicle objects;
Loop around all of the elements in the 2 dimensional array (e.g. using inner and outer loop);
Skip empty locations;
Take the first vehicle found and add as the head of the binary tree;
Take all subsequent vehicles found and do the following;
Get the node’s vehicle registration;
Find the appropriate insertion point in the binary tree by navigating from the root and comparing the registration to the key of the current node;
When a leaf node is reached compare the registration with the vehicle to be inserted and insert it as the left or right child node, using its registration as the key;
Continue until the end of the vehicle array has been reached;
Examiners report
Both parts were well-answered.
Both parts were well-answered.
Most students identified the tree property that effectively eliminates half of the tree when searching but answers were not always detailed enough to gain full marks.
A large number of students were unclear as to how a binary search tree is created. Full marks were only reached by those students who clearly identified the different stages of the process.
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). -
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
