This site uses cookie tracking technologies. Learn more in our Cookie Policy.
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, this recursive procedure.
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.
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, 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.
Three operations are performed on this circular linked list in the following order:
Arrays and linked lists are used to store linear data.
a diagram showing the resulting circular linked .
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
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
how this data could be used to 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
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.
The transport authority wishes to know how many passengers, on average, travel on each day of the week.
Using the procedure total 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).
, in pseudocode, the procedure salesCalculate().
Sign up for a free account to keep practicing.
Practice IB Computer Science (CS) Topic 5.1 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.1 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.
