IB Questionbank

User interface language: English | Español

Date	November 2021	Marks available	5	Reference code	21N.1.HL.TZ0.13
Level	HL	Paper	1	Time zone	no time zone
Command term	Construct	Question number	13	Adapted from	N/A

Question

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

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

State the distance between Kiko and Longlines.

[1]

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]

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]

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]

Markscheme

Award [1 max].
5.9;

Award [5 max].
Award [1] for correct outer/row loop
Award [1] for correct inner/column loop
Award [1] for use of a flag
Award [1] for checking whether all elements on and above the main diagonal are zero
Award [1] for checking all elements below the main diagonal (they all should be positive numbers)
Award [1] for outputting the appropriate message

Example 1:

VALID=True
loop R from 0 to 9
   loop C from 0 to 9
        if R>C and ROUTE_X_DISTANCES[R][C]<=0
             then VALID=False
         end if
         if R<=C and ROUTE_X_DISTANCES[R][C]!=0
             then VALID=False
         end if
     end loop
end loop
if VALID
  then output('VALID')
  else output('INVALID')
end if

Example 2:

FLAG=1
loop R from 1 to 9
loop C from 0 to R-1
if ROUTE_X_DISTANCES[R][C]<=0
then FLAG=0
end if
end loop
end loop

loop R from 0 to 9
loop C= from R to 9
if ROUTE_X_DISTANCES[R][C]!=0
then FLAG=0
end if
end loop
end loop
if FLAG ==1
then output('IT IS VALID')
else output('IT IS NOT VALID')
end if

Example 3:

Note: Marks should also be awarded if a candidate wrote the algorithm in Java/Python/Javascript.

Award [1] for correct outer/row loop
Award [1] for correct inner/column loop
Award [1] for stopping as soon as an incorrect value is found
Award [1] for checking whether elements on and above the main diagonal are zero
Award [1] for checking elements below the main diagonal (they all should be positive numbers)
Award [1] for outputting the appropriate message

function check()

{ for (var i=0; i<10; i++)
  { for (var j=0; j<10; j++)
    { if (i>j)
      { if (ROUTE_X_DISTANCES[i][j] <= 0.0) return "invalid";
      }
      else if (ROUTE_X_DISTANCES[i][j] != 0.0 ) return "invalid";
    }
  }
  return "valid";
}

output("ROUTE_X_DISTANCES is "+check());

Award [6 max].
Award [1] for all variables correctly declared and initialized;
Award [1] for looping through the array ROUTE_X_NAMES;
Award [1] for determining positions of the first name in the array;
Award [1] for determining positions of the second name in the array;
Award [1] for outputting a message if one or other not present;
Award [1] for a comparison of positions to find largest;
Award [1] for the correct output of distance from ROUTE_X_DISTANCES;

Example 1:

NAME1=input()
NAME2=input()
POS1=-1
POS2=-1
K=0
loop while K<=9 and (POS1==-1 or POS2==-1)
      if ROUTE_X_NAMES [K].equals(NAME1) //accept '==' instead of equals()
        then POS1=K
      end if
      if ROUTE_X_NAMES [K].equals(NAME2)
         then POS2=K
      end if
      K=K+1
end while
if POS1==-1 OR POS2==-1
   then output('stations are not found')
   else
      if POS1 > POS2
         then output(ROUTE_X_DISTANCES [POS1][POS2])
         else output(ROUTE_X_DISTANCES [POS2][POS1])
      end if
end if

Example 2:

ST1=input()
ST2=input()
PS1=-1
PS2=-1
loop K from 0 to 9
      if ROUTE_X_NAMES [K]==ST1
        then PS1=K
      end if
      if ROUTE_X_NAMES [K]==ST2
         then PS2=K
      end if
end loop
if PS1!=-1 AND PS2!=-1
  then   if PS1 < PS2
         then T=PS1
              PS1=PS2
              PS2=T
         end if
         output(ROUTE_X_DISTANCES [PS1][PS2])
  else
         output('stations not found')
end if

Example 3:

Note: Award marks if algorithm is presented in a Java/Python/Javascript/any other program rather than IB pseudocode.
For example, please see the following Javascript program

function findStation(station)
{ var found = false;
  var i = 0;
  do
  { found = (ROUTE_X_NAMES[i] == station);
    if (!found) i = i + 1;
  } while (!found && i < 10);
  if (found) return i;
  else
  { output("No such bus station as "+station);
    return -1;
  }
}




var station1 = input();
var station2 = input();
output("Finding the distance between "+station1+" and "+station2);
var station1index = findStation(station1);
var station2index = findStation(station2);
if (station1index >=0 && station2index >= 0)
   { if (station1index >= station2index)
       output("Distance "+ROUTE_X_DISTANCES[station1index][station2index]);
   else
       output ("Distance = "+ROUTE_X_DISTANCES[station2index][station1index]);
}

Award [3 max].
Determine positions/indexes/subscripts of both bus stations in array ROUTE_X_NAMES;

Calculate the sum of the elements of array ROUTE_X_TIMES (calculate the number of minutes as the sum of the array elements);

Between (lower +1) index and higher index;

Examiners report

The majority of students attempted it, and many got it right.

Algorithms were required based on the question scenario. Some candidates did not attempt these questions. Some candidates achieved high marks by demonstrating good programming skills. Many candidates scored several marks for the construction of a partial solution or a solution that was partially correct.

Algorithms were required based on the question scenario. Some candidates did not attempt these questions. Some candidates achieved high marks by demonstrating good programming skills Many candidates scored several marks for the construction of a partial solution or a solution that was partially correct.

Varied from poor to excellent.

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