Consider 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.
Sketch a double linked list that holds the following sequence of names: Anne, Lana, Mary.
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 “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.
Outline why combinatorial optimization is used in the travelling salesman problem.
Outline one potential problem with hill climbing when applied to the travelling salesman problem.
Sketch a balanced binary tree that would allow the following output when traversed using in order traversal:
Zebra, Tango, Hotel, Foxtrot, Delta, Bravo, Alpha.
The following method, swap(A, B) is written to exchange the values of variables A and swap(A,B) TEMP = A B = TEMP A = B end swap
Assume A = 3 and B = 5. State the values of A and B after execution of swap(A, B).
Suggest how the algorithm used in method swap() would need to be modified to successfully exchange the values of variables A and B.
Use pseudocode to construct an algorithm for the method swapRows().
State Paul's total score.
State where Hugh's score in the fourth round can be found.
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 and part (b).
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.
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 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 arrayROUTE_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 [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.
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
Define the term recursion.