Unit 5: Abstract Data Structures [45 marks]
1. [Maximum mark: 15]
The two-dimensional array MAT is used to store randomly generated integers in
the range from 0 to 9.
In the MAT array, some numbers can be repeated multiple times and other
numbers may not appear at all (see Figure 1).
Figure 1: Example data stored in the MAT array
The one-dimensional COUNT array will show how many times each of the
randomly generated numbers is found in the MAT array (see Figure 2).
Figure 2: The content of the COUNT array
Figure 2 shows that number 4 occurs 5 times (COUNT[4]=5) in the MAT array.
(a) Construct an algorithm in pseudocode to create the COUNT
array as described. You may assume that the MAT array is
created and the COUNT array is initialized with zero values. [4]
In Figure 2, COUNT[8]=0 because the number 8 does not appear in the MAT
array.
(b) Construct an algorithm in pseudocode that uses the COUNT
array to output the numbers that do not appear in the MAT
array. If all of the numbers from 0 to 9 are present, then it will
output an appropriate message. [5]
The mode is the number that appears most often in the MAT array. There can be
more than one mode.
0, 3 and 9 are the modes of the numbers stored in the MAT array (see Figure 2).
(c) Construct an algorithm in pseudocode that uses the COUNT
array to output the mode(s) of the numbers stored in the MAT
array. [6]
2. [Maximum mark: 15]
A bus company provides services within a city. Passengers can look up the
distance between any two bus stations on any of its routes.
For each route, a one-dimensional string array is used to store the names of all
bus stations on the route and a two-dimensional array is used to store the
distances between the bus stations (in kilometres). Only the lower triangle of the
two-dimensional array is used to store the distances.
Figure 1 shows data about Route X, a bus route between Oppox and Dovely.
Figure 1: One-dimensional string array, ROUTE_X_NAMES, and
two-dimensional array, ROUTE_X_DISTANCES, for Route X
For example, the distance between Kingsley and Kronos (2.0 kilometres) can be
found in ROUTE_X_DISTANCES [7][5].
(a) State the distance between Kiko and Longlines. [1]
The two-dimensional array ROUTE_X_DISTANCES is valid if all the entries on
and above the main diagonal are zero and all the entries below the main
diagonal are greater than zero.
Figure 2 shows an invalid form of ROUTE_X_DISTANCES.
Figure 2: Invalid form of two-dimensional array ROUTE_X_DISTANCES
(b) Construct an algorithm in pseudocode that checks the elements
of the array ROUTE_X_DISTANCES and outputs whether the
array is valid or not. [5]
(c) Construct an algorithm in pseudocode that inputs the names of
two bus stations and outputs the distance between them. If any
of the inputted names are not found, the method should
output an appropriate message. [6]
(d) The array ROUTE_X_TIMES (Figure 3) stores the approximate
number of minutes it takes for a bus to travel to a bus station
from the previous one. For example, ROUTE_X_TIMES [6] stores
the number of minutes it takes for a bus to travel from Kingsley
to Allapay: 7 minutes.
Figure 3: The array ROUTE_X_TIMES
Explain how this data could be used to determine the number
of minutes it takes for a bus to travel between any two bus
stations. [3]
3. [Maximum mark: 15]
Images in computers are stored as two-dimensional arrays.
A black-and-white image (Figure 1) is stored as a 10 × 10 two-dimensional array
named MAT (Figure 2).
Each element of MAT holds a number for a colour; 1 represents the colour black
and 0 represents the colour white.
In an application, the black-and-white image can be inverted (all white pixels are
changed to black, and all black pixels are changed to white).
Method invert(N,A) accepts a positive integer N and an N × N two-dimensional
array A that holds the data for a simple black-and-white image; it returns the
inverted N × N two-dimensional array A.
(a) Construct an algorithm in pseudocode for the method
invert(N,A). [3]
In the application, it is also possible to rotate an image clockwise by 90 degrees
(90°).
For example, when the simple black-and-white image is rotated, the
corresponding 10 × 10 two-dimensional array MAT is updated.
This would mean the first row of the original MAT is the last column in the
rotated MAT, the second row is the second-to-last last column, … and the last
row is the first column.
Consider the following algorithm fragment:
K=input()
loop for M=0 to K mod 4 - 1
A=rotate(N,A)
end loop
where:
N is an integer and A is the N × N two-dimensional array that holds data
about an image
K(K>=0) is an integer showing how many times the image should be
rotated
method rotate(N,A) accepts an integer N and an N × N two-dimensional
array A representing an image. It returns an N × N two-dimensional array
representing the image rotated clockwise by 90°.
(b.i) State the number of degrees by which the image will be rotated
if the input value of K is 3. [1]
(b.ii) Outline why it is more efficient that the loop in the given
algorithm fragment executes (K mod 4) times instead of
K times. You may give an appropriate example in your answer. [2]
The algorithm for method rotate(N,A) uses an additional N × N two-
dimensional array, named The N × N dimensional array B is initialized and
updated using the values from A to represent the image rotated clockwise by
90°.
(c) Construct the algorithm in pseudocode for the method
rotate(N,A) described above. [3]
(d) To avoid inefficient use of memory, a new algorithm for the
method rotate(N,A) is constructed.
The N × N two-dimensional array A should be rotated
clockwise by 90°, without the use of any additional arrays.
One way of rotating the two-dimensional array A clockwise by
90° is to transpose A, and then reverse each row of A.
The transpose of A is formed by turning all the rows of A into
columns. For example, the value in the first row and third
column (A[1][3]) is swapped with the value in the third row and
first column (A[3][1]).
Construct the new algorithm in pseudocode for the method
rotate(N,A) described above. [6]
© International Baccalaureate Organization, 2025
