IB Computer Science 5. Abstract Data Structures Questionbank

Determinism and non-invertibility are key characteristics of hashing.

Describe how these properties contribute to the functionality and security of blockchain technology.

(a) List two characteristics of a digital signature.

(b) List two stages in the proof-of-work process.

A local charity organizes a half-marathon to raise money. The rules to participate in the half-marathon are as follows:

• The organizers limit the total number of participants to 450
• Participants belong to a team and each team must have at least three and at most five participants
• Each participant registers for the event independently from the other members of their team, and they all declare their team name when registering
• For scoring, the team's final time is the sum of the times of its three fastest participants. Participants who do not cross the finishing line within 2 hours after the start, are assigned a default time of 1000 minutes. The winning team is the team with the smallest sum total.

During registration, an array, PARTICIPANTS, with 450 positions is used to hold the abbreviated team names that are declared by each participant. Simultaneously, a collection TNAMES is generated: any new team name that is declared is added to the collection.

Part of the array PARTICIPANTS is shown below, where, for example, the first participant declared that they are part of team TK. The initial part of the collection TNAMES is also shown, with arrows indicating the direction of growth.

PARTICIPANTS:

TNAMES [Image of TNAMES collection]

Both PARTICIPANTS and TNAMES are used to construct the array, TEAM, that groups all participants who belong to the same team. Part of the array TEAM is shown below.

TEAM:

In TEAM, each element is related to one other index in the array, shown by the arrows on the above diagram. This relation will eventually form a closed path (for this example 0, 3, 5, 8, 9 and back to 0). The relation reflects the information in PARTICIPANTS, by grouping people who declared the same team name during registration. Hence, participants 0, 3, 5, 8 and 9 are on the same team and, from PARTICIPANTS, that team is TK.

(a) Determine the minimum size of TNAMES to ensure the names of all potential teams can be stored.

(b) Identify the position in PARTICIPANTS of the second participant that registered for team QA.

5.1 Abstract data structures (HL)

Explain how the order in which items are inserted into a Binary Search Tree (BST) can impact the efficiency of its search operations.

(c) In order to complete this code, and return the correct TEAM array, construct pseudocode to find MINP, the first index in PARTICIPANTS of the CURRENT team, and use it to start the construction of TEAM.

(d) In order to complete this code, and return the correct TEAM array, construct pseudocode to find the other participants belonging to the CURRENT team, implementing the idea of the closed paths in the TEAM array.