IB DP Computer Science Topic 5: Networks -: 5.1 – Abstract data structures HL Paper 1

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

a.)State the distance between Kiko and Longlines.[1]

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]

▶️Answer/Explanation

Ans:

a.)
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());
b.)

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]);
}
c.)

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;

 

Question

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:
1 A node containing the number 30 is inserted at the beginning of the circular linked list.
2 The last node is deleted from the circular linked list.
3 The first node is deleted from the beginning of the circular linked list.
Arrays and linked lists are used to store linear data.
a. Sketch a diagram showing the resulting circular linked list.[3]

b. Outline how the last node of the circular linked list is identified.[2]

c. Describe the steps required to calculate the sum of all numbers held in this circular linked list.[4]

d. Compare the use of arrays and linked lists.[4]

e. A linked list can be used to implement a data structure queue.[2]
Identify two applications of a queue data structure.

▶️Answer/Explanation

Ans:

a. )

Award [1] for the node containing number 20 is pointed to by the pointer ‘head’;
Award [1] for the diagram showing only two nodes and all the correct links;
Award [1] for the last node containing number 5;

Award [1] for the last node containing number 5;

The last node is identified by its next/link pointer;
which contains the address of the node at the beginning of the list / is equal to the pointer “head “;

b.)

Initialize (a temporary pointer with the head and) a variable sum with 0 (zero);
Loop from the beginning to the end of the circular linked list / until all the nodes get traversed);
Add the value (of the data field) (of the current node) to the sum;
Change the temporary pointer so it points the next node of circular linked list;

Note: Answers written in pseudocode are acceptable.
For example,

sum = 0
curr = head
loop
sum = sum + curr.data
curr = curr.next
until curr == head
c.)

In an array, memory is assigned during compile time(predetermined) whilst in a linked list it is allocated during execution/runtime;
Arrays are of fixed size whilst linked lists are flexible and can expand and contract its size;
Array requires less memory (due to actual data being stored within the index in the array) whilst there is a need for more memory in linked list (due to storage of additional next and previous pointers/references);
Elements are stored consecutively in array whereas elements are stored randomly in linked lists;
Memory utilization is inefficient in the array whilst memory utilization is efficient in the linked list;
Accessing an element in an array is direct (fast) while accessing an element in linked list is sequential/linear (slower) /to get into the nth element only the array name with index within the square bracket should be written whilst a linked list (to get the nth element) should be traversed starting from the beginning of the list, and traversing through the list until found/ ;
Operations like insertion and deletion in arrays consume a lot of time whilst the performance of these operations in linked lists is fast;

d.)

Print queues (a number of print jobs on a queue instead of waiting for each one to finish before specifying the next one);
Queue is used for synchronization when data is transferred asynchronously between two processes (for example IO Buffers, file IO);
Queues are used in CPU scheduling algorithms;
Handling of interrupts in real-time systems (the interrupts are handled in the same order as they arrive, first come first served);
Computer modelling of physical queues (supermarket checkouts) (call centre phone systems use queues to hold people calling them in an order, until a service representative is free);

Question

a.)Identify one difference between a binary tree and a non-binary tree.[1]
b.)Given the following binary search tree (BST), draw the resulting BST after the deletion of the root node.[2]

▶️Answer/Explanation

Ans:

a.)
Binary tree (is a tree) in which every node has (no, one or) at most two children whilst
a non binary tree can have nodes with more than 2 children (non binary trees do not have an upper limit on number of children nodes);
Each node in a binary tree can have at most two subtrees (left and right subtree), a node in a non binary tree can have any number of subtrees;
b.)
Award [1] for the root (1)
Award [1] for the correct right subtree

Alternative answer

Award [1] for the root (4)
Award [1] for the correct right subtree

Scroll to Top