IB

Computer Science
HL

Question Bank
Chapter 5
Abstract data structures

Book No: 9005

Homework:

Name: ____________________ Remark: ___________________

Date: ____________________ In-charge Sign: ___________________

1
2
Questions
Part - I
1. Define the term recursion. [1]

2. Describe the characteristics of a queue. [2]

3. Compare the use of a linked list with an array to store and process the daily sales
in a business. [3]

4. Consider the following recursive method, where N is a positive integer

mystery(N)
if (N > 0) AND (N mod 2 = 0) then
mystery(N−2)
end if
output N
end mystery

(a) Determine the output produced by the method call mystery(5). [1]

(b) Determine the output produced by the method call mystery(4). [3]

(c) Construct an iterative algorithm for the method mystery(), which uses a
single while loop instead of recursion. [4]

5. Identify the components of a node in a doubly linked list. [3]

6. Outline the reason why recursive solutions can be memory intensive. [2]

7. Consider the following binary tree.

(a) Identify all leaf nodes in this binary tree. [1]

(b) For this binary tree, state the result of:

(i) in-order tree traversal, [1]

(ii) postorder tree traversal. [1]

3
8. A car park has two barriers. One barrier is at the entrance, where tickets are issued,
and one barrier is at the exit, where paid tickets are checked when cars leave. A
display at the entrance, showing the current availability of spaces in the car park, is
updated as tickets are issued and checked.

The actions of issuing, paying and checking a ticket operate on the collection of
objects, TICKETS, that is organized as a linked list. Each object holds the following
information:

Nr: ticket number (a progressive unique identifier) Date: date of issue

Arrival: time of issue (in 24-hour format) PaidOn: date of payment
PaidAt: time of payment (in 24-hour format).
Describe how a linked list is a suitable data structure for the given scenario. [2]

9. LookUpLunch is an app for a Smartphone that can be used to search for restaurants
located in zones of increasing distance from the user’s current position. The diagram
shows the user and zones as they would appear on a map of the area.

A search in Norway produced the following table, RESULTS, which shows the number
of restaurants in each zone. RESULTS also displays the average price for a meal,
expressed in the local currency (Norwegian Krone, NOK).

Another Smartphone app that is linked to LookUpLunch collects customers’ reviews for
restaurants.

4
A review consists of whether a customer likes the restaurant, and a rating of cheap (C),
medium (M) or expensive (E). The app combines all of the reviews to produce a single
letter rating (C, M or E) and a total number of likes for the restaurant.

As part of the internal representation of the app, the collection LIKES is used. Some
of the data items contained in LIKES are shown below. Each individual data item is
separated by a comma.

0,26,TomHus,M,1,14,GladLaks,E,2,1,MerPoteter,C,1,15,Linie,E,0,2,
Mezze,M...

The restaurant GladLaks, underlined as an example, is located within zone [1]. Based
on the reviews, this restaurant has 14 likes and is expensive.

By making use of binary trees and the collection LIKES, explain how a list could be
produced that shows the restaurants in order of zone and then, within each zone, in
order of popularity. [3]

10. Consider the following binary tree.

(a) State the order that the nodes will be listed using the postorder tree
traversal. [1]

(b) The node H is deleted so that the postorder traversal of the remaining
nodes is preserved from part (a). Sketch the updated binary tree following this
deletion. [2]

11. (a) Draw an annotated diagram showing how an array can be used to store a
stack. [2]

(b) Explain how elements in the stack may be reversed using a queue. [4]

12. (a) Describe the characteristics of a stack. [2]

(b) Identify two applications of a stack in computing. [2]

5
Part - II
1. The names of students attending a science fair were recorded in a stack data
structure as each one arrived.

The first item stored in the stack was “Sophie”.

Note that “Troy” is currently in position 0 in the stack.

(a) Construct the pseudocode that will search the stack for a specific name,
and output its position in the stack. You may assume that all names in the
stack are unique. [5]

(b) Explain the benefits of using a binary search tree, compared to a stack,
when searching for a specific item. [3]

If the tree is populated with the data from the stack, the first item popped off will
become the root. For each subsequent item popped from the stack, a recursive
procedure is followed until the item is correctly placed in the tree.

(c) Without writing code, describe this recursive procedure. [4]

(d) By considering only the data visible in the stack shown above, sketch the
binary search tree that has been created from the items removed from the
stack. [3]

6
2. A transport authority is investigating how many people use a certain direct train
route.

At the end of each day, the total number of passengers who travelled on this route is
stored in a collection, PASSENGERS.

The first item was written to the collection on Monday 1st May 2017.

The next items, collected on Tuesday and Wednesday, were added like this:

Data for 30 complete weeks was added to the collection.

(a) Construct pseudocode that will read PASSENGERS into the two-dimensional
array, 2D_ARRAY. [4]

(b) Construct the pseudocode for the procedure total, that takes as input a
column number of this two-dimensional array and returns the sum of the
elements in that column. [4]

The transport authority wish to know how many passengers, on average, travel on
each day of the week.

(c) Using the procedure total construct the pseudocode to output the day of
the week with the highest average number of passengers, and the value of this
average.

You should make use of the sub procedure convert() which converts the
numbers 0 to 6 into days of the week, for example convert(1) will return
“Tuesday”. [3]

7
The transport authority stores details about the ticket prices in a one-dimensional
array, FEES, where FEES[0] contains the price of a ticket for Monday to Friday, while
FEES[1] contains the price of a ticket for Saturday and Sunday.

The procedure salesCalculate() takes as input the column and row indices that
define two specific days during the 30 weeks, and outputs the total amount of money
generated from ticket sales between those two days (inclusive).

(d) Construct, in pseudocode, the procedure salesCalculate(). [7]

3. (a) Describe the features of a dynamic data structure. [2]

Consider the following doubly linked list which holds the names of flowers in
alphabetical order.

(b) Explain how “Primrose” could be inserted into this doubly linked list. You
should draw a labelled diagram in your answer. [6]

Consider the two stacks: FLOWERS and FRUITS.

(c) Show the output produced by the following algorithm based on above
stacks. [4]

8
A third stack, FLOFRU, is needed. It should contain all the data from FLOWERS and
FRUITS and will store it as shown below

(d) Describe how the FLOFRU stack could be created. [3]

4. Consider the following two-dimensional array, MAT, with dimensions 6 × 6.

The value −1 is stored in MAT at position [4][2]. The position [4][2] means row
4 and column 2.

(a) State the total number of elements stored in MAT. [1]

(b) State the number of non-zero elements in MAT. [1]

A two-dimensional array in which most of the elements are zero is called a sparse
matrix. A sparse matrix can be compressed by storing only non-zero elements using
three one-dimensional arrays.

The first array, VALUES, stores all non-zero elements taken from the sparse matrix in
row-major order (left-to-right then top-to-bottom order).

The length of the array VALUES is equal to the number of non-zero elements in the
sparse matrix.

9
For the sparse matrix above, MAT, the array VALUES is:

The second array is ROWC. ROWC[i] stores the number of non-zero elements, from
row 0 to row i of the sparse matrix, inclusive.
The length of ROWC is equal to the number of rows in the sparse matrix.

For MAT the array ROWC is:

For example, ROWC[2] stores 3 because in MAT there are three non-zero elements
from row 0 to row 2, inclusive.

The third array, COL, stores the column index for each non-zero element in the sparse
matrix. COL[i] stores the sparse matrix column index for the non-zero element stored
in VALUES[i].

For MAT the array COL is:

(c) Construct an algorithm that compresses a 6 × 6 two-dimensional array, such

as MAT, into the three one-dimensional arrays described on page 8. You may
assume that the 6×6 array is inputted and all three one-dimensional arrays are
initialized. [6]

10
Consider the three arrays below. They hold the compressed contents of a 7 × 7 sparse
matrix, BIGMAT.

(d) For a given column, C, in BIGMAT, outline how it could be determined that
this column contains no non-zero elements. [2]

(e) State how many rows in BIGMAT contain only zeros. [1]

(f) (i) State the index in VALUES of the first non-zero element in row 5 of
BIGMAT. [1]

(ii) For a given row, R, in BIGMAT, determine the range of indexes in VALUES
where non-zero elements in row R of BIGMAT are placed. You may
assume that there is at least one non-zero element in row R. [3]

5. The diagram shows a list of names held in a circular linked list. The end of the list is
pointed to by an external pointer, X.

(a) State the first name in this circular list. [1]

Two operations are performed on the list in the following order:

* A node containing the name Sarah is inserted at the beginning of the list.
* A node containing the name Ken is inserted at the end of the list.
(b) Sketch a diagram showing the resulting circular linked list. [3]

11
(c) Describe how the number of names held in this list could be determined.
[4]

(d) Explain how a stack could be used to output, in reverse order, all names
held in the linked list. [4]

(e) Compare the use of static and dynamic data structures. [3]

6. A two-dimensional array, A, has N rows and N columns, where N is a positive

integer.
2
The following algorithm is written to fill array A with the numbers 1, 2, 3..., N .

(a) Trace the algorithm, with an input of N=3, to show the contents of array A after the
algorithm has been executed. [3]

2
There are many different ways of placing the numbers 1 to N into an N × N two-
dimensional array. The following two-dimensional array, with dimensions 5 × 5 has
been filled in a circular (spiral) pattern with numbers 1 to 25.

12
The general process of filling an N × N two-dimensional array, in a circular (spiral)
pattern, with numbers from 1 to N2 could be described as follows:

• initialize Z=1,

• initialize TOP, BOTTOM, LEFT and RIGHT,

• iterate until the whole array is filled,

• each time Z is placed correctly increase the value of Z by 1,

• fill the elements of the TOP row starting from LEFT to RIGHT,

• increase TOP by 1 before filling the elements of the RIGHT column,

• fill the elements of the RIGHT column starting from TOP to BOTTOM,

• decrease RIGHT by 1 before filling the elements of the BOTTOM row,

• and continue filling the BOTTOM row and LEFT column in a similar way, adjusting
TOP, RIGHT, BOTTOM and LEFT accordingly.

(b) (i) State the initial values for TOP, BOTTOM, LEFT and RIGHT. [1]

(ii) State the consequence of not increasing TOP by 1 before starting to

fill the elements of the RIGHT column. [1]

(iii) In the algorithm described above, state the indices (subscripts) of

the first and the last element to be filled in the BOTTOM row. [1]

(c) Construct, in pseudocode, an algorithm to fill an N × N two-dimensional

array, in a circular (spiral) pattern, with numbers from 1 to N2 as described
above. [9]

7. Theo entered a maze (labyrinth) and tries to get to the centre. As soon as he arrived
at the first possibility to turn right or left, he started recording each move on his phone
so that he could find his way back to the start. He entered the moves as the direction
he turned followed by the number of steps taken before the next turn. For example:

R3 , L5 , L10 , R6 , ... , L4
which indicates "TURN right, STEP 3", and then "TURN left, STEP 5" etc.

An app on his phone stored the moves in a stack named STK, using 0 for “right” and 1
for “left”. The above moves were therefore stored as

0 , 3 , 1 , 5 , 1 , 10 , 0 , 6 , ... , 1 , 4.

(a) Explain why a stack is a suitable structure to hold the data. [2]
13
Theo was successful in reaching the centre of the maze and now has to get back to
the start.

(b) Construct an algorithm, using appropriate stack access methods, to output

the moves needed to return from the centre to the first point where Theo
started recording his moves. You can assume that he is facing the correct exit
when he starts his return journey. [5]

8. The table below holds student names and scores, from a class test.

(a) Draw a diagram to show how the data given in the table could be stored in a
binary tree in the order of scores. Data should be inserted into the binary tree in
the order given in the table (i.e., data about Ann Taylor is to be inserted first).
[3]

(b) The same data could be inserted into a singly linked list in descending
order of scores. Draw a diagram of this singly linked list. [3]

(c) Compare the data structures in part (a) and part (b) in terms of:

(i) searching [2]

(ii) storage requirements. [2]

(d) Consider the following recursive algorithm, in which X and Y are

parameters in the method F. The return statement gives the value that
the method generates. Determine the value of F(5,11). [2]

14
9. A magic square is a two-dimensional array with n rows and n columns in which each
2
of the integers 1, 2, 3, ..., n appears exactly once and all column sums, row sums and
diagonal sums are equal.

The array A is a 7 × 7 magic square in which all rows, columns and the two main
diagonals add up to 175.

(a) Construct an algorithm to calculate the sum of all elements on the main diagonal,
from A[0, 0] to A[6, 6]. [2]
2
(b) An array with n rows and n columns holds every number from 1 to n . Construct an
algorithm that checks whether the n × n array is a magic square. [8]
The following is the algorithm for constructing a magic square with n rows and n
columns for any odd integer n.

15
(c) By applying this algorithm, copy and complete the 5×5 magic square, which
has been started below. Do not write solutions on this page. [5]

10.

(a) (i) Describe, with the aid of a suitable diagram, a dynamic singly linked list. [3]

(ii) Explain how an item could be found in this list. [3]

(b) Consider the following binary tree.

(i) State the order in which data will be listed using postorder tree traversal.
[1]

(ii) Identify the traversal which will return a list of names sorted in
alphabetical order. [1]

(c) Describe how a name which is stored in a node with two children could be
deleted from the binary tree without changing the order of the remaining names. [4]

(d) Compare the efficiency of finding a name in the binary tree with finding the
same name in a linked list. [3]

16
11. Let E be the arithmetic expression 9+2∗3.

(a) State the postfix representation of E. [1]

The following tree is a possible representation of E.

(b) Identify the traversal on the tree that would produce the expression E. [1]

(c) State the expression obtained by performing a post-order traversal of the

tree. [1]

(d) Suggest an algorithm and a data structure to be used on the tree in order
to produce the postfix representation of E. [3]

(e) Explain why binary tree traversal fits the requirements of the recursive
method. [4]

17
Mark Scheme
Part - I
1. Process/method/procedure/subroutine/function/algorithm that calls itself [1]

2. Award [2]. FIFO data structure;

Items can be added only to one end (rear/tail) and removed from the other end
(front/head); [2]

3. Award [3]. Award [1] for size comparison. Award [1] for access comparison. Award
[1] for relation to the given scenario.

Example:
Size/length of a static array is predetermined/fixed / size of a linked list
can be changed / size of a linked list depends only on memory available; Linked
list can be expanded to suit the daily sales;
Each item in a static array can be directly accessed whilst access to the items in
a linked list is sequential;
And searching for the given item in the linked list is slower /an item in the linked
list cannot be searched for using binary
search; [3]

4. (a) 5; [1]

4. (b)
Award up to [3] as follows:
[3] for fully correct response (sequence of output) “0;2;4”;
[2] for response (sequence) “4;2;0” (all elements are correct, but they are in inverse
order);
[1] for response ”0” (only base case is correct);
OR
“0;2” (incomplete output, but initially correct, and with correct order);
OR
“–2;0;2;4”,“0;2;4;6” (correct sequence immersed in some unnecessary and incorrect
context);

[0] in all other cases (e.g. responses “2”, “4”, “2;0”, “2;4”, “4;2”);

0
2
4 [3]

18
4. (c)
Example answer 1

Award marks as follows up to [4 max]. (There are 5 marking points);

Award [1] for determining whether N is odd/even;
Award [1] for correctly initializing and changing the value of the loop controlling variable
(K);
Award [1] for the correct condition in the while loop;
Award [1] for output within the loop for an even N;
Award [1] for output after the loop for an odd N;

mystery(N)
if N mod 2 = 0 then
K=0
loop while K <= N
output K
K=K+2
end loop
else
output N
end if
end mystery

Example answer 2

Award marks as follows up to [4 max]. (There are 5 marking points);

Award [1] for determining whether N is odd/even;
Award [1] for correctly initializing and changing the value of the loop controlling variable
(K);
Award [1] for the correct condition in while loop (note K < N);
Award [1] for output within the loop for an even N;
Award [1] for outputting N after the loop;

mystery(N)
K=0
loop while (K < N) AND (N mod 2 = 0)
output K
K=K+2
end loop
output N
end mystery

Note: No marks for any attempt of program that contains recursive calls.
Reminder: in the Spanish version mystery() is called incognita().
Remark: A correct program produces in output numbers in an ascending order, only.
[4]

19
5. Data;
A pointer/reference to the previous node;
A pointer/reference to the next node; [3]

6. Award up to [2].
A recursive call involves the use of stacks;
For storing/pushing on/popping out data/ return addresses/return values etc.;
If many recursive calls are made, the memory usage can be very large; [2]

7. (a) D and C; [1]

(b) (i) BDAC; (ii) DBCA; [2]

8. Award [1] for a feature of a linked list.

Award [1] for relating it to the given scenario.

Size of a linked list is not fixed/predetermined (efficient use of memory); Suitable

because the number of objects/cars in the car park may vary greatly;

Efficient addition of elements to the linked list;

Suitable because cars arrive at the car park in any order; [2]

9. Award marks as follows up to [3 max].

Award [1] for associating trees to zones.
Award [1] for explaining how to use the collection’s elements to build the trees. Award
[1] for inserting nodes under some criterion.
Award [1] for visiting the trees in such a way as to produce the ordered list.

For example:

Create three binary trees (one for each zone), by taking 4 elements at a time from
LIKES;
The element “zone” identifies the tree and the other three elements make a new node
in that tree;

Nodes are added depending on “likes” so that left child =< (accept “<”) the
(subtree) root, less than right child;
Do an in-order traversal on the three trees to get three lists, then join them together;
[3]

20
10. (a) CDLHTPM [1]

10. (b)

11. (a) Award up to [2] max.

Award [1] for the array elements shown,
[1] for either two additional variables or for labelling.

Example answer:

Variable Top is used to hold the subscript of the current top of the stack ; [2]

11. (b) Award up to [4] max.

Create an empty queue;
While stack is not empty:
Pop an element from the stack;
Enqueue the popped element;
While queue is not empty:
Dequeue;
Push dequeued element back on the stack;

Note: Award a maximum [2] for answers that describe how a stack and a queue work
[4]

12. (a) A data structure;

Which can only be accessed at one end / the last (first) element in is the first (last) one
out;
nd
Note: accept “LIFO” for the 2 marking point. [2]
21
12. (b) Award up to [2 marks max].
Used in calculations, evaluation of expressions;
Translations from one programming language to another;
Transferring control from one part of a program to another (such as storing return
addresses, running recursive processes);
Etc. [2]

Part - II
1. (a) Example answer 1:

searchName(NAME, STACK)
DEPTH = 0
NAMEDEPTH = -1
while not STACK.isEmpty() do
X = STACK.pop()
if X == NAME
then NAMEDEPTH=DEPTH
DEPTH = DEPTH + 1
end while
if NAMEDEPTH == -1
then output(NAME + ’not found’)
else output(NAMEDEPTH)
endif
end searchName
Award [5] as follows:

Award [1] for initialization.

Award [1] for a correct while/until loop.
Award [1] for correct comparison and assignment.
Award [1] for updating and outputting correct position of NAME on the
stack(NAMEDEPTH)
Award [1] for use of stack methods (pop() and isEmpty()) [5]

Example answer 2:

NAME=input()
CSTK = STACK.copy() // must make a real copy,
//any attempt to make a copy of stack is acceptable DEPTH = 0
SEARCHING = true
while SEARCHING and not CSTK.isEmpty() do
if NAME == CSTK.pop()then

22
SEARCHING = false
else
DEPTH = DEPTH + 1
end if
endwhile
if not SEARCHING then
output(DEPTH)
else
output NAME + " not found"
end if
Award [1] for initialization.
Award [1] for a correct while/until loop (even if flag is missing).
Award [1] for correct comparison and assignment.
Award [1] for incrementing and outputting correct position of NAME (DEPTH).
Award [1] for use of stack methods (pop() and isEmpty()). [5]

1. (b) Award [3].

Example answer 1 (time efficiency):

The data in the binary search tree(BST) is ordered;

Such that as each node is checked for the item, half of the remaining nodes are
ignored;
But each element in the stack has to be checked;
Which, for large data sets, may be inefficient compared to the BST;

Example answer 2 (memory efficiency):

Each element on the stack has to be popped off/removed from the stack to
be checked for the searched item;
When the item is found the stack will be empty/stack contents will be changed; When
an element in the BST is checked for the item it is not removed from the BST;
So there is no need to create an additional copy of the BST (but a real copy of the
stack must be created which for large data sets may be inefficient); [3]

1. (c) Award [4].

Example answer:
The (next) stack item is (placed into a new node and) compared (alphabetically) to the
root;
If the root is empty it would be placed here (and this recursive procedure terminates);
Else, depending upon the comparison, it would look to the node to the left or right and
the (recursive) procedure calls itself again (with the new root);
If it is lower than the root, then the left child of the root becomes the new root;
If it is higher than the root, then the right child of the root becomes the new root;

Note: Marks should also be awarded for an algorithm constructed in pseudocode [4]

23
1. (d)

Award [3] marks

Award marks as follows:

Clearly a binary tree; Correct root; All values correct; [3]

2. (a) Award [4] as follows.

Example answer 1:

Assumes that an array of sufficient size is declared (2D_ARRAY[][]) and

PASSENGERS contains valid data for all 7 days in each of 30 weeks.

PASSENGERS.resetNext()
N=0
loop while PASSENGERS.hasNext()

//accept not PASSENGERS.isEMPTY()

//accept N<PASSENGERS.length()
WEEK = N div 7
DAY = N mod 7
2D_ARRAY[WEEK][DAY] = PASSENGERS.getData() //
PASSENGERS.getNext() N=N+1

end loop

Award [1] for while loop.

Award [1] for correct calculation of row index(WEEK) Award [1] for correct calculation
of column index(DAY) Award [1] for correct array subscripts
Award [1] for correct use of collection methods

24
Example answer 2:

Assumes that an array of a sufficient size is declared (2D_ARRAY[][]) and

PASSENGERS contain valid data for all 7 days in each of 30 weeks)

PASSENGERS.resetNext()
loop for WEEK from 0 to 29
loop for DAY from 0 to 6
2D_ARRAY[WEEK][DAY] = PASSENGERS.getNext()//PASSENGERS.getData()

end loop
end loop

Award [1] for nested loops.

Award [1] for loops that generate the right output (correctly read PASSENGERS into
2D_ARRAY).
Award [1] for assignment into correct array location.
Award [1] for correct use of collection methods. [4]

2. (b)
total (N)
// if N (column number) is not passed as an input parameter then
// assignment must appear in pseudocode, for example, N =
input()

SUM = 0
loop for WEEK from 0 to 29
SUM = SUM + 2D_ARRAY[WEEK][N]
end loop
return SUM
end total
Award [1] for assigning the input to a variable / passing the value of N
Award [1] for initializing and returning/outputting SUM
Award [1] for correct loop
Award [1] for correct addition of each term to SUM (Note: the array position must
be completely correct with the input column and the varied row). [4]

25
2. (c) Example Answer

MAXAV = 0
MAXDAY = ""
loop for DAY from 0 to 6
if total(DAY)/30 > MAXAV
MAXAV = total(DAY)/30
MAXDAY = convert(DAY)
end if
end loop
output MAXAV,MAXDAY
Award [1] for correct loop.
Award [1] for use of method total() when calculating the average number of
passengers.
Award [1] for initializing, updating and outputting/returning MAXAV and MAXDAY. [3]

2. (d)
salesCalculate(2D_ARRAY, A, B, X, Y) // A,B are row & column of first day,
// X,Y are row & column of last day.
TOTAL = 0
loop for COL= B to 6
if COL < 5 then
TOTAL = TOTAL + 2D_ARRAY[A][COL] * FEES[0]
else
TOTAL = TOTAL + 2D_ARRAY[A][COL] * FEES[1]
end if
end loop
//calculates total for week A,
//days are in the range from B to 6
//weekdays are days 0-4, and weekend 5,6
loop for ROW = A + 1 to X - 1
loop for COL= 0 to 6
if COL < 5 then
TOTAL = TOTAL + 2D_ARRAY[ROW][COL]*FEES[0]
else
TOTAL = TOTAL + 2D_ARRAY[ROW][COL]*FEES[1]
end if
end loop
end loop
//calculates total for all weeks from A+1 to X-1,
//days are in the range from 0 to 6
loop for COL= 0 to Y
if COL < 5 then
TOTAL = TOTAL + 2D_ARRAY[X][COL]*FEES[0]
else
TOTAL = TOTAL + 2D_ARRAY[X][COL]*FEES[1]
end if
end loop

26
//calculates total for week X,
//days are in the range from 0 to Y
output TOTAL
end salesCalculate
Award [7].
Award [1] for initializing, updating and outputting TOTAL.
Award [1] for nested loops.
Award [1] for correct calculation of TOTAL in row/week A (column subscripts/days/ in
2D_ARRAY must be in range B to 6).
Award [1] for correct calculation of TOTAL in row/week X (column subscripts/days/ in
2D_ARRAY must be in range 0 to Y).
Award [1] for correct calculation of TOTAL in rows/weeks from A + 1 to X – 1 (column
subscripts/days/ in 2D_ARRAY must be in range 0 to 6).
Award [1] if evident that the number of days to be included in calculating total amount
is different for weeks A + 1 to X – 1, week A and X (three different cases).
Award [2], [1] for checking for weekdays / weekend and [1] for using correct subscript
in FEE (0 for weekdays, 1 for weekend). [7]

3. (a) Award up to [2].

Each node contains data and also a link to other nodes;
Links between nodes are implemented by pointers (a pointer references a
location in memory or holds a memory address);
List size is not fixed / predetermined; [2]

3. (b)Award up to [6] as follows. (There are 7 marking points)

[1] create new node;
[1] instantiation of values and pointers in new node;
[1] state where the search starts from;
[1] how to detect position for insertion;
[1] update pointers in new node;
[1] update pointers from the node at the insertion point, to the new node;
[1] update external pointers;

Remark: Some answers may just use illustrations alone, or very minimal explanations:
see note below;

Create a new node (with pointer NEWNODE) with data field Primrose and two pointer
fields (next and previous), to be inserted;

Perform a linear search, either from the beginning or end of the list (using pointers
FIRST and LAST, on the alphabetically order list;

The location/position of insertion, is found by comparing nodes (Primrose to be

inserted after Lavender, LOCATION points to Lavender) (Accept any description to that
effect);

(At the end of this phase, the situation looks as in Figure 1)

27
Then, continue by setting the “next” field/pointer in the newly created node to NULL;

Set the “previous” pointer in the newly created node to the current LAST / to point to
Lavender/ to point to the node detected by LOCATION;

Change/Set/Update the Lavender’s “next” pointer to point to the new node / to link with
the NEWNODE pointer (delete NULL in the field and link to the existing NEWNODE
pointer);

Update the LAST pointer to point to the newly created node; Eventually the final
doubly linked list looks like this (Figure 2);

Note: Award [4] for responses that return one or more drawings without any
explanation at all, for evidence of these features:
[1] Evidence of creation of an initial new node for Primrose out of the list;
[1] The order of nodes Aster/Camellia/Lavender/Primrose is eventually correct;
[1] The two unidirectional links between Lavender and Primrose are (eventually)
correctly displayed, from-to the appropriate fields;
[1] LAST points correctly to the appropriate field in the new node Primrose, and NULL
fills the last field of the new node; [6]

3. (c) Award [1] for each one in the correct order.

Apple; Broom; Camellia; Day Lily;
Note: Solution for the Spanish version (in this order):
Aster; Camelia; Lavanda; Lirio; [4]

28
3. (d) Award marks as follows up to [3].
Example answer 1

Create an empty stack (FLOFRU);

pop all elements from FRUITS and push them onto FLOFRU;
Then pop all elements from FLOWERS and push them onto FLOFRU;

Example answer 2

Create an empty stack (FLOFRU);

While FRUITS is not empty
pop an element from FRUITS and push it onto FLOFRU;
While FLOWERS is not empty
pop an element from FLOWERS and push it onto FLOFRU;
Note: Award [2] for generic descriptions that do not use appropriate
terminology on data structures and their operations. [3]

4. (a) 36 [1]

4. (b) 7 [1]

4. (c) Award marks as follows up to [6]. (There are 7 marking points)

Award [1] for initialization and correct changes of K (index/position in arrays VALUES
and COL);
Award [1] for initialization and correct changes of COUNT (counts non-zero elements);
Award [1] for correct conditions in “row” loop;
Award [1] for correct conditions in “column” loop;
Award [1] for placing non-zero element at correct position in array VALUES;
Award [1] for placing the “column” index of the non-zero element at correct position in
array COL;
Award [1] for placing COUNT at correct position in array ROWC;

29
4. (d) Award up to [2 max].

Example answer 1

Array COL should be searched for (value) C;

If (value) C is not found in array COL then this column (the column whose index in
BIGMAT is C) holds only zeros;

Example answer 2

If the number of occurrences of (value) C in array COL; Equals zero then this column
holds only zeros;

Example answer 3:
Award [1 only].
(wrong, so award [1] mark only)
If COL[C] = COL[C–1], then the column with index C in BIGMAT contains no non-
zero-elements;
(Accept words to that effect: “if the difference between COL[C] and COL[C-1] is
zero, then...”); [2]

4. (e) 1 [1]

4. (f)
(i) 5; [1]

(ii) Award marks as follows up to [3].

Award [1] for realizing that the range should be determined differently for the first row
(when row index R is 0) OR correct range when row index is 0;
Award [1] for correct first index in range (when row index R is not 0);
Award [1] for correct last index in range;
If row index R is equal to 0 then the range is from 0 to ROWC[0]-1 ; If row index R
is not equal to 0 then the range is from ROWC[R-1]; To ROWC[R]-1;

Note: Award [2 max] for a correct calculation of the indexes, but no unifying expression
showing how they have been calculated is given). [3]

30
5. (a) Boris; [1]

5. (b) Award up to [3].

For the diagram showing all nodes and links;
Ken inserted after Anna AND Sarah placed after Ken;
Node containing Ken is pointed to by X/Ken is currently at the end of the list;

[3]
5. (c) Use a variable (counter) to keep track of/increment the number of nodes;
Use a temporary pointer;
Follow the pointers from the beginning of the list/from the node pointed to by pointer
X.next;
Until the pointer to the end of the list (pointer X) is encountered;
Note: Accept methods that start from the end of the list (X). [4]

5. (d) Initialize an empty stack;

Traverse the list from beginning to end;
Pushing each data value from the list onto the stack;
While stack is not empty;
Popping an element from the stack and output the stack element; [4]

5. (e) Static data structure has a predetermined number of elements but number of
elements in dynamic data structure does not have to be defined in advance;
Static data structure has limited size, the amount of memory available is the only limit
in size of dynamic data structure, size varies;
In static data structure elements can be directly accessed, in a dynamic data structure
access is sequential (which is slower); [3]

6. (a) Award [1] for each correct row, up to [3].

Accept answers that transpose the table. [3]

31
6.
(b) (i)
Award [1] only for all correct values.

TOP=0
BOTTOM=N-1
LEFT=0
RIGHT=N-1 [1]

(b) (ii)

The array element at position [TOP][RIGHT] in which value of Z is already placed,

will be overwritten by the value of Z + 1;

Not all of the numbers 1 to N2 will be placed in the array because some will be
overwritten;
The array will be filled with more than N2 numbers/with numbers greater than N2;

Accept answers from the sample 5×5 table, e.g., the value of MATRIX[0][4]
which is already filled by 5, will be changed to 6. [1]

(b) (iii)

The first element to be filled in BOTTOM row has indices (subscripts)

[BOTTOM][RIGHT] and the last to be filled has indices (subscripts)
[BOTTOM][LEFT];

Accept answers from the sample 5 × 5 table. The first element to be filled in
BOTTOM row has indices (subscripts) [4][3] and the last to be filled has indices
(subscripts) [4][0]. [1]

6. (c) Award up to [9] as follows.

Award [1] for initializing Z.
Award [1] for initialization of the top and bottom rows, and left and right columns.
Award [1] for the outer loop (must be while).
Award [1] for the idea that four inner loops are needed
(could be for or while loops).
Award [1] for each correct inner loop up to [4].
Award [1] for assignment (current value of Z placed in A).
Award [1] for changing the value of Z after each assignment.
Award [1] for changing values of TOP, BOTTOM, LEFT, RIGHT.

32
Example answer 1:

Z=1
TOP=0
BOTTOM=N-1
RIGHT=N-1
LEFT=0
loop while Z<=N*N
COUNT1 = LEFT
loop while COUNT1 <= RIGHT
A[TOP][ COUNT1] = Z
Z = Z+1
COUNT1 = COUNT1+1
end loop
TOP = TOP+1
COUNT2 = TOP
loop while COUNT2 <= BOTTOM
A[COUNT2][ RIGHT] = Z
Z = Z+1
COUNT2 = COUNT2+1
end loop
RIGHT = RIGHT-1
COUNT3 = RIGHT
loop while COUNT3 >= LEFT
A[BOTTOM][ COUNT3] = Z
Z = Z+1
COUNT3 = COUNT3-1
end loop
BOTTOM = BOTTOM-1
COUNT4 = BOTTOM
loop while COUNT4 >= TOP
A[COUNT4][ LEFT] = Z
Z = Z+1
COUNT4 = COUNT4-1
end loop
LEFT = LEFT+1
end loop WHILE

33
Example answer 2:

Z=1
TOP=0
BOTTOM=N-1
RIGHT=N-1
LEFT=0
loop while Z<=N*N
loop for i from LEFT to RIGHT
A[TOP][i]=Z
Z=Z+1
end loop
TOP=TOP+1
loop for i from TOP to BOTTOM
A[i][RIGHT]=Z
Z=Z+1
end loop
RIGHT=RIGHT-1
loop for i from RIGHT downto LEFT
A[BOTTOM][i]=Z
Z=Z+1
end loop
BOTTOM=BOTTOM-1
loop for i from BOTTOM downto TOP
A[i][LEFT]=Z
Z=Z+1
end loop
LEFT=LEFT+1
end loop WHILE

Note: For both examples, assume that integer N is inputted and the space for the array
A with dimensions N × N is allocated. [9]

7. (a) Because items/moves are needed in reverse order;

To the order input;
OR
Because it is a LIFO (Last In First Out) data structure;
The items/moves pushed/placed onto the stack;
Will be popped off/taken from it in reverse order (to the order input); [2]

34
7. (b)
Award marks as follows, up to [5 marks max].
Award [1 mark] for checking for empty.
Award [1 mark] for popping STEP and TURN from stack.
Award [1 mark] for an output (STEP).
Award [1 mark] for correct if statement (checking popped TURN).
Award [1 mark] for an output (TURN).

For example:

8. (a)
Award marks as follows up to [3 max].
Award [1] for correct nodes (2 data fields and two pointers).
Award [1] for correct root.
Award [1] for correct left subtree.
Award [1] for correct right subtree.
Award [1] for trees that display either only names or only numbers, provided that they
are structurally correct.

35
8. (b)
Award marks as follows up to [3 max].
Award [1] for correct nodes (2 data fields and one pointer field).
Award [1] for correct order (links shown).
Award [1] for the external pointer to list and showing the end of the list (nil).

8.
(c)(i)
Award [2] for a valid comparison of binary trees and linked lists.
Award [1] for identifying a characteristic of either binary trees or linked lists, but without
an explicit comparison.

(ii)
Award [2] for a valid comparison of binary trees and linked lists.
Award [1] for identifying a characteristic of either binary trees or linked lists, but without
an explicit comparison.

8. (d)

Award [1] for each correct line.

36
9. (a)
Award [1 mark] for the correct loop.

Award [1 mark] for increasing the sum for the correct value. [2]
9. (b)
Award [8 max]
[2 marks] for correctly calculating sum of the second diagonal:
[1 mark] for the correct loop and [1 mark] for increasing the sum for the correct value.
[1 mark] for a correct use of the Boolean variable, MAGIC.
[1 mark] for correct outer loop.
[1 mark] for correct inner loop.
[1 mark] for correct calculation of the row sum.
[1 mark] for correct calculation of column sum.
[1 mark] for comparing row sum and column sum with diagonal sum. [8]

Example

MAGIC = TRUE
SD1 = 0
SD2 = 0
loop for K = 0 to (N-1)
SD1 = SD1 + A[K,K]
SD2 = SD2 + A[K,N-1-K]
end loop
if SD1 != SD2
MAGIC = FALSE
end if
K = 0
loop while (K<=(N-1)) AND MAGIC
SR = 0
SC = 0
loop for Z = 0 to (N-1)
SR = SR + A[K,Z]
SC = SC + A[Z,K]
end for
if ( SR ! = SD1) OR (SC! = SD1)
MAGIC = FALSE
end if
K = K + 1
end while
if MAGIC = TRUE
output “ The array is a magic square”
else
output “ The array is not a magic square”
end if

37
9. (c)
Award [1 mark] if the “off the edge” rule seen.
Award [1 mark] if the “off the top” rule seen.
Award [1 mark] if the “cell already filled” rule seen.
Award [2 marks] for whole square complete. [5]

10.
(a) (i)
Award marks as follows, up to [3 marks max].
Award [1 mark] for the external pointer to the list and no further nodes at the end.
Award [1 mark] for showing internal pointers.
Award [1 mark] for showing that each node contains data and pointer fields. [3]
Example diagram

(ii)Award up to [3 marks max].

Temporary pointer should be set to point to the beginning of the list;
Follow the internal pointers;
And compare the data in the node pointed to by the temporary pointer with the
searched data;
If found stop searching;
If the end of the list is reached then the searched data is not on the list; [3]

10.
(b)(i) BORIS, JANE, IVY, ANNIE, ROBERT, MARK; [1]

(ii) In-order traversal; [1]

10. (c) Award up to [4 marks max].
If the name to be deleted is placed in a node which has two children then find the
replacement node (the largest value in its left sub-tree / the smallest value in its right
sub-tree) and its parent node;
If the replacement node is either the leaf node or has one child;
Set the data fields in the node to be deleted to the data value in the replacement node;
Delete the replacement node;
If the replacement node to be deleted is a leaf node then just set the pointer in its
parent node to null;
If the replacement node to be deleted has one child then set the pointer in its parent
node to point to its child; [4]

38
10. (d) Award up to [3 marks max].
A linked list takes n comparisons to find a name, average search time is proportional to
number of elements;
When the binary tree is well balanced, it takes log2n comparisons to find a name (no
more than n comparisons);
So, a binary tree is usually more efficient, however in extreme cases will only take as
long as a linked list; [3]

11. (a) 923*+ OR 23*9+ [1]

11. (b) Preorder [1]

11. (c) +*329 [1]

11. (d) Perform post-order traversal on the tree;

Use a stack to put +*329;
Pop from stack (to reverse it) and get the postfix representation; [3]

11. (e) A binary tree is structurally self-referential (by definition of binary tree);
Because each node in the tree is a root to a binary tree of smaller size, or a node
without descendants (leaf);
The traversal algorithm exploits the structural definition of binary trees and can easily
be implemented recursively;
Because a recursive method operates by calling a function from within the function
itself (left/right subtrees) and needs a termination condition (leaf node); [4]

39