User interface language: English | Español

Date May 2019 Marks available 2 Reference code 19M.2.HL.TZ0.17
Level HL Paper 2 Time zone no time zone
Command term Outline Question number 17 Adapted from N/A

Question

The organizing school arranges for visiting students to stay with a host family. The information about each of the visiting students is stored in a file. The student records are sorted by name. Some of the other variables included are school, gender, age and host family name, as shown in the UML diagram below.

A program needs to be written to match visiting students with host families. The matching process requires data to be manipulated extensively (adding, editing, deleting). The file will be read into RAM.

This program will be used for different events with different numbers of visitors. Therefore, it will be implemented using a dynamic data structure.

It has been decided to use a single linked list named guests to store and manipulate the Visitor objects.

Consider the following diagram which represents the list guests.

The following recursive method has been written to act on the list guests.

public void recursive(int k, char a)
{
if (k == guests.size())
{
output ("no such record");
}
else
{
Visitor current = guests.get(k);
if ((current.getGender() == a) && (current.getAge() > 15))
{
output current.getName();
}
else
{
recursive(k + 1,a);
}
}
}

Define the term object reference.

[1]
a.

Outline one reason why a linked list may be more suitable than a binary tree in this particular situation.

[2]
b.

Construct the code needed to instantiate an object guests of the LinkedList class.

[1]
c.i.

Construct the code for the method penultimate() that returns the second to last element in the linked list guests. You may assume that guests is locally accessible.

[4]
c.ii.

Using the data provided in the diagram, trace the call recursive(0,'F'), clearly showing the levels of recursion.

[4]
d.

Outline one reason why the use of a recursive method may be inappropriate for linked lists.

[2]
e.

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 removeSchool that takes the name of a school as parameter and removes all students of that school from the list guests.

[6]
f.

Markscheme

Award [1 max].
A reference is a variable whose value points to the location of an object (in memory); 

a.

Award [2 max].
The ease of which pointers or references can be manipulated in a linked list;
Allows easier addition/deletion of objects (compared to a binary tree);
It can be difficult to manipulate pointers or references in a binary tree;
Which makes it more difficult to add or delete objects in a binary tree; 

b.

Award [1 max]Allow missing final parentheses.
LinkedList<Visitor> guests = new LinkedList<Visitor>();

c.i.

Award [4 max]
Award [1] for correct signature.
Award [1] for using size() or finding the correct size of the linked list *
Award [1] for correctly returning the penultimate element.
Award [1] for correctly returning null if there is no penultimate element in the list.

public Visitor penultimate(LinkedList guests) // parameter
is optional
{
Visitor result = null;
if(guests.size() > 1) {
result = guests(guests.size()-2);
}
return result;
}

*Note to examiners – allow a method that will iterate through the class as long as a valid LinkedList class methods are used.

c.ii.

Award [4 max].
Award [1] for showing the second call to the method
Award [1] for showing the third call to the method (and no subsequent calls)
Award [1] for including the correct test outcome
Award [1] for correct output

recursive(0,'F')
k = 0
current is Ana
test incorrect
recursive(1,'F')
k = 1
current is Ben
test incorrect
recursive(2,'F')
k = 2
current is Defne
test correct
output Defne Tasci
d.

Award [2 max].
For a large linked list, this would require a large number of recursive calls / become very memory intensive;
Which may cause stack overflow;

A linked list only allows for sequential access;
Therefore, using recursion would not lead to any gains in efficiency;

e.

Award [6 max].
Award [1] for the correct initialisation of index.
Award [1] for correct loop/iterator declaration and initialisation
Award [1] for the correct assignment to current.
Award [1] for the correct comparison of school (allow use of =)
Award [1] for the correct remove (allow correct use of next pointer)
Award [1] for the decrementing index after remove.
Award [1] for correct increment of index / use of iterator.next(). Within context.

Example answers:

public void removeSchool(String school) {
int index = 0;
Visitor current;
while(index < guests.size()) {
current = guests.get(index);
if(current.getSchool().equals(school)) {
guests.remove(index);
index--;
}
index++;
}
}

public void
removeSchool(String school) {

Visitor current;
for(int index = 0; index < guests.size();index++) {
current = guests.get(index);
if(current.getSchool().equals(school)) {
guests.remove(index);
index--;
}
}
}

public void
removeSchool(String school) {
Iterator<Visitor> itr = guests.iterator();
Visitor current;
while(itr.hasNext()){
Visitor current = itr.next();
if(current.getSchool().equals(school)) {
itr.remove();
}
}
}
f.

Examiners report

Not many candidates related this term to a location in the memory.

a.

A binary tree may be ideal when searching for items, but when extensive editing is required then the ability of a linked list to easily manipulate its pointers makes this structure the preferred option.

b.

Reasonably well answered.

c.i.

When answering questions regarding a library class then the use of the correct methods are expected. Not many candidates were familiar with the use of the size method.

c.ii.

This was a quite straightforward trace of a recursive algorithm which most candidates completed well.

d.

Some candidates alluded to the excessive use of memory if recursion was used.

e.

Many candidates made a reasonable attempt but too many tried to use generic methods instead of ones specifically pertaining to this class.

f.

Syllabus sections

Option D: Object-oriented programming » D.4 Advanced program development
Show 33 related questions
Option D: Object-oriented programming

View options