Topic 5 - Abstract data structures(HL)
Question 1
HLPaper 1Consider the following binary tree.
An inorder traversal of this binary tree will produce a list of names sorted in ascending order.
State two applications of stacks.
Explain the use of a one-dimensional array as a static stack. Your answer should include brief outlines of the push and pop operations and the tests for empty and full stacks.
State the result of postorder traversal.
Draw the binary tree after deleting the root node.
Compare the use of static and dynamic data structures.
Question 2
HLPaper 1Sketch a double linked list that holds the following sequence of names: Anne, Lana, Mary.
Question 3
HLPaper 1The 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 “Sophie”.
Note that “Troy” is currently in position 0 in the stack.
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.
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.
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.
Question 4
HLPaper 1Sketch a balanced binary tree that would allow the following output when traversed using in order traversal:
Zebra, Tango, Hotel, Foxtrot, Delta, Bravo, Alpha.
Question 5
HLPaper 1The following method, swap(A,B)is written to exchange the values of variables A and B.
swap(A,B)
TEMP = A
B = TEMP
A = B
end swap
Method swapRows(MAT,K,L)swaps the elements of two rows (row Kand row L) in the two‑dimensional array MAT.
For example,
A game consists of four rounds. In each round a player can score up to 100 points.
The data about the game is sorted in alphabetical order of names and stored in the memory as follows
Where
PLAYERSis a one-dimensional array holding names of players (currently sorted in alphabetical order).
ROUNDSis a two-dimensional array holding players’ scores.
TOTALSis a one-dimensional array holding total scores.
For example,
PLAYER[1]is Boris. The total number of points he scored is 180 and this can be found in TOTALS[1].
Boris scored 40 points in the first round which can be found in ROUNDS[1][0].
The value stored in ROUNDS[1][2]is 50 which means that Boris scored 50 points in the third round.
State Paul’s total score.
State where Hugh’s score in the fourth round can be found.
All the data stored in memory should be sorted in ascending order of total score using selection sort.
For example, after sorting, the data given opposite will be held in memory as follows
Construct an algorithm that will sort all the data in ascending order.
In your solution you should call methods swap()and swapRows()given in part (a) and part (b).
Question 6
HLPaper 1Consider 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.
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.
Question 7
HLPaper 1A 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_DISTANCESis 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 arrayROUTE_X_DISTANCES
State the distance between Kiko and Longlines.
Construct an algorithm in pseudocode that checks the elements of the array ROUTE_X_DISTANCESand 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 [6]stores the number of minutes it takes for a bus to travel from Kingsley to Allapay: 7 minutes.
Figure 3: The arrayROUTE_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.
Question 8
HLPaper 1Consider the following recursive method, where Nis a positive integer
mystery(N)
if (N > 0) AND (N mod 2 = 0) then
mystery(N−2)
end if
output N
end mystery
Question 9
HLPaper 1Define the term recursion.
Question 10
HLPaper 1A 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 PASSENGERSinto 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 totalconstruct 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 numbers0 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 the column and row indices that define two specific days during the 30 weeks, and outputs the total amount of money generated from ticket sales between those two days (inclusive).
Construct, in pseudocode, the procedure salesCalculate().
