User interface language: English | Español

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

Question

A two-dimensional array CUSTOMERS [ ] is used to store customer details for a mail order company such that each row of the array represents a customer record and each column represents a specific field. The fields currently in use are: LASTNAME, FIRSTNAME, ADDRESS1, ADDRESS2, ADDRESS3, CITY, POSTCODE.

The array currently holds 512 records.

The company wishes to print a number of mailing labels, such as the one shown below, that will go to all customers called Jones who live in Cardiff.

A singly linked list has been created including the following surnames; Bale, Cousens, Davies, Pugh, Williams.

Construct the pseudocode that will find how many customers live in the city of Cardiff and display the results.

[5]
a.

Construct an algorithm that will enable the company to print the mailing labels for all customers called Jones who live in Cardiff.

[5]
b.

Explain the steps to insert “Jones” into this singly linked list. You may draw a labelled diagram in your answer.

[5]
c.

Outline one example of where a circular linked list would be used in preference to a linear linked list.

[2]
d.

Markscheme

Award [5 max].
Initialization of TOTAL before loop and output of result after loop;
Use of any loop with correct limits;
Correct row and column subscripts of two-dimensional array;
Correct comparison in if statement;
Totalling within if statement, if statement inside loop;

Note to examiners: Do not accept flowcharts.

Example algorithm 1:

SEARCH = "Cardiff"
TOTAL = 0

loop COUNTER from 0 to 511
if SEARCH = CUSTOMERS[COUNTER][5] then
TOTAL = TOTAL + 1
end if
end loop

output "The number of customers is ", TOTAL

Example algorithm 2

TOTAL = 0
loop COUNTER from 0 to CUSTOMERS.length()-1
if CUSTOMERS[COUNTER][5].equals( "Cardiff")
//accept CUSTOMERS[COUNTER][5]== "Cardiff"
then TOTAL = TOTAL + 1
end if
end loop
output TOTAL

Note to examiners:
The array structure is not given in the question.

If array subscripts begin with 1, then award 1 mark for 
loop COUNTER from 1 to 512 
and 1 mark for 
CUSTOMERS[COUNTER][6]

a.

Award [5 max].
Use of any loop with correct limits;
Correct row and column subscripts of two-dimensional array;
Correct comparison in if statement
Output of all row elements(fields)
Output correctly formatted

Note to examiners: Accept flowcharts.

Example algorithm 1:

SEARCH1 = "Jones"
SEARCH2 = "Cardiff"
loop COUNTER from 0 to 511
if CUSTOMERS[COUNTER][0] = SEARCH1 then
if CUSTOMERS[COUNTER][5] = SEARCH2 then
output CUSTOMERS[COUNTER][1] " " CUSTOMERS[COUNTER][0]
output CUSTOMERS[COUNTER][2]
output CUSTOMERS[COUNTER][3]
output CUSTOMERS[COUNTER][4]
output CUSTOMERS[COUNTER][5]
output CUSTOMERS[COUNTER][6]
end if
end if
end loop

Example algorithm 2:

R=0
loop while R <= 511
   if CUSTOMERS[R][0]=="Jones" and CUSTOMERS[R][5]== "Cardiff"
      then
        output CUSTOMERS[R][1], CUSTOMERS[R][0]
        loop K from 2 to 6
          output CUSTOMERS[R][K]
        end loop
      end if
  R=R+1
end loop

Note to examiners:
Since “Jones” can be either a first or last name, accept
       CUSTOMERS[COUNT][1] == SEARCH1
and the first output line
     output CUSTOMERS[COUNT][0], CUSTOMERS[COUNT][1]

b.

Award [5 max].
Accept correct answers given as diagrams or written in text applying the following marking points:

Award [5 max] if candidate explained the steps to insert “Jones” into sorted list at correct place.
Award [1] for each of the following steps, up to [5]

Create a new node with data field Jones and pointer field;
Start searching from the beginning of the list;
Find the location/position where the new node is to be inserted (Jones to be inserted after Davies);
Set the pointer in the new node (containing Jones) to the pointer in the node containing Davies (to point to the node containing Pugh);
Set the pointer in the node containing Davies to point to the new node (Jones);

Award [3 max] if candidate explained only the steps to insert “Jones” at the end of the list.
Award [1] for each of the following steps

Create a new node with data field Jones and pointer field NIL;
Start searching from the beginning of the list to find the last node (Williams);
Set the pointer in the last node (containing Williams) to point to the new node (Jones);

Award [3 max] if candidate explained only the steps to insert “Jones” at the beginning of the list.
Award [1] for each of the following steps, up to [3]

Create a new node with data field Jones and pointer field;
Set the pointer in the new node (containing Jones) to the external pointer (which points to the beginning of the list/to the first node in the list (Bale));
Set the external pointer to point to the new node (Jones);

c.

Award [2 max].
Award marks for the use of circular lists (rather than linked lists) in an application (accept examples);
in which any node can be a starting point / which traverses the whole list by starting from any point;
to repeatedly go around the list;

Used to allow multiple applications to run in a PC;
The operating system cycles through each one in time giving each a slice of time to execute;

Used for the implementation of a (circular) queue;
The end of the queue points to the beginning, eliminating the need to maintain both front and rear pointers;

Used in multiplayer gaming environment;
The OS cycles through one player at a time using time slicing;

A media playlist that repeats (endlessly);
The last song (node) points to the first song;

d.

Examiners report

Those candidates who are proficient in programming easily got full marks. The others did not complete the exercise or completed it incorrectly.

a.
[N/A]
b.

Part (c) seems to have split the cohort; strong candidates often responded with full and correct answers, however there were many responses that were completely wrong.

c.

Not many candidates were able to outline a good example of the use of a circular list in preference to a linear linked list in Part(d).

d.

Syllabus sections

Topic 5: Abstract data structures » 5.1 Abstract data structures
Show 80 related questions
Topic 5: Abstract data structures

View options