IB Computer Science 5.1 Abstract Data Structures Questionbank

Consider the following circular linked list:

where head is an external pointer that points to the first node in the circular linked list.

Three operations are performed on this circular linked list in the following order:

Arrays and linked lists are used to store linear data.

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

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

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

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

Determinism and non-invertibility are key characteristics of hashing.