Practice IB Computer Science (CS) Topic 5. Abstract Data Structures with authentic exam-style questions for both SL and HL students. This question bank focuses on the exact syllabus content for 5. Abstract Data Structures and mirrors Paper 1, 2, 3 style where relevant.
Get instant solutions, detailed explanations, and build confidence with questions aligned to IB examiner expectations.
The names of students attending a science fair were recorded in a stack data structure as each one arrived.
The first item stored in the stack was "Troy".
Note that "Troy" is currently in position 0 in the stack.
If the tree is populated with the data from the stack, the first item popped off will become the root. For each subsequent item popped from the stack, a recursive procedure is followed until the item is correctly placed in the tree.
Without writing code, describe this recursive procedure.
Construct the pseudocode that will search the stack for a specific name, and output its position in the stack. You may assume that all names in the stack are unique.
Explain the benefits of using a binary search tree, compared to a stack, when searching for a specific item.
By considering only the data visible in the stack shown above, sketch the binary search tree that has been created from the items removed from the stack.
Consider the following circular linked list:
where head is an external pointer that points to the first node in the circular linked list.
Arrays and linked lists are used to store linear data.
Sketch a diagram showing the resulting circular linked list.
Outline how the last node of the circular linked list is identified.
Describe the steps required to calculate the sum of all numbers held in this circular linked list.
Compare the use of arrays and linked lists.
A linked list can be used to implement a data structure queue.
Identify two applications of a queue data structure.
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
State the distance between Kiko and Longlines.
Construct an algorithm in pseudocode that checks the elements of the array ROUTE_X_DISTANCES and outputs whether the array is valid or not.
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.
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 [8] 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.
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
Determine the output produced by the method call mystery(4)
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.
Construct pseudocode that will read PASSENGERS into the two-dimensional array, 2D_ARRAY.
Construct the pseudocode for the procedure total, that takes as input a column number of this two-dimensional array and returns the sum of the elements in that column.
The transport authority wishes to know how many passengers, on average, travel on each day of the week.
Using the procedure total construct the pseudocode to output the day of the week with the highest average number of passengers, and the value of this average.
You should make use of the sub procedure convert() which converts the numbers 0 to 6 into days of the week, for example convert(1) will return “Tuesday”.
The transport authority stores details about the ticket prices in a one-dimensional array, FEES, where FEES[0] contains the price of a ticket for Monday to Friday, while FEES[1] contains the price of a ticket for Saturday and Sunday.
The procedure salesCalculate() takes as input four integers: the row and column indices of a start day and the row and column indices of an end day , and outputs the total amount of money generated from ticket sales between those two days (inclusive).
Construct, in pseudocode, the procedure salesCalculate().