IB Questionbank

User interface language: English | Español

Date	May 2019	Marks available	5	Reference code	19M.1.HL.TZ0.17
Level	HL	Paper	1	Time zone	no time zone
Command term	Construct	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]

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

[5]

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

[5]

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

[2]

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]

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]

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);

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;

Examiners report

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

[N/A]

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.

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).

Syllabus sections

Topic 5: Abstract data structures » 5.1 Abstract data structures

Show 80 related questions

17N.1.HL.TZ0.13c:

Show the output produced by the following algorithm.

loop while (NOT FRUITS.isEmpty()) AND (NOT FLOWERS.isEmpty())
  X = FRUITS.pop()
  Y = FLOWERS.pop()
  if X < Y then
    output X
  else
    output Y
  end if
end loop

Hide related questions

Topic 5: Abstract data structures

Question

Markscheme

Examiners report

Syllabus sections

View options