Explain why a stack is used in the process of evaluating the expression in the algorithm.

Outline the steps involved in traversing the given tree using postorder tree traversal.

State the output from the given tree using inorder tree traversal.

State the result of inorder traversal of this binary tree.

Explain how “Primrose” could be inserted into this doubly linked list. You should draw a labelled diagram in your answer.

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.

State the value of MAT[3][4].

State the purpose of the following queue method:

dequeue()

State the result of preorder traversal of this binary tree.

State the dynamic data structure suitable for maintaining this list of vegetables which will allow faster searching for a given vegetable name.

The vegetable names are input in the following order

potato, asparagus, lettuce, radish.

Sketch the data structure suggested in part (d) containing the vegetable names sorted in alphabetical order.

Describe the characteristics of a queue.

State the distance between Kiko and Longlines.

Identify one application of a queue.

Define the term child in relation to a binary tree.

State the output from the binary tree using postorder traversal.

Explain the steps to insert “Jones” into this singly linked list. You may draw a labelled diagram in your answer.

Outline one example of where a circular linked list would be used in preference to a linear linked list.

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.

Sketch a balanced binary tree that would allow the following output when traversed using in order traversal:

Zebra, Tango, Hotel, Foxtrot, Delta, Bravo, Alpha. 

Sketch a single linked list holding these vegetables.

Show the output produced by the following algorithm.

loop while (NOT FRUITS.isEmpty()) AND (NOT FLOWERS.isEmpty())
  X = FRUITS.pop()
  Y = FLOWERS.pop()
  if X < Y then
    output X
  else
    output Y
  end if
end loop

State the index in $\mathrm{VALUES}$ of the first non-zero element in row $5$ of $\mathrm{BIGMAT}.$

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).

Draw the binary tree after deleting the root node.

Compare the use of static and dynamic data structures.

Construct an algorithm in pseudocode for the method invert(N,A).

Identify one disadvantage of using a two-dimensional array for this purpose.

State the purpose of the following queue method:

enqueue()

Consider the following recursive method:

mystery(N)
    if N>0 then
        return 3 + mystery(N-3)
    else
        return 3
    end if
end mystery

where N is an integer.

Determine the value of mystery(7). Show all your working.

Describe one difference between stack and queue data structures.

State the purpose of the following queue method:

isEmpty()

State the number of degrees by which the image will be rotated if the input value of K is 3.

Outline why it is more efficient that the loop in the given algorithm fragment executes (K mod 4) times instead of K times. You may give an appropriate example in your answer.

Sketch a double linked list that holds the following sequence of names: Anne, Lana, Mary.

Identify two characteristics of a dynamic data structure.

Outline why a binary tree would be a good choice of data structure for maintaining an address book.

List the steps required to insert cabbage into the linked list.

Explain the importance of the method isEmpty() when constructing an algorithm which performs operations on a stack data structure.

State Paul’s total score. 

Compare the use of a dynamic linked list for holding these names of vegetables with a static one-dimensional array.

State two applications of stacks.

State where Hugh’s score in the fourth round can be found. 

Identify one difference between a binary tree and a non-binary tree.

Given the following binary search tree (BST), draw the resulting BST after the deletion of the root node.

Outline how the last node of the circular linked list is identified.

Sketch a diagram showing the resulting circular linked list.

Determine the value of variable X after execution of the following method call:

X = mystery(MAT,5)

where MAT is the two-dimensional array given. You must show your working.

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.

Describe the features of a dynamic data structure.

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.

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”.

Determine the output produced by the method call mystery(4).

Construct an efficient algorithm for the method isValidMatrix().

Construct the algorithm in pseudocode for the method rotate(N,A) described above.

Explain why deleting the first node in this list is different to deleting other nodes.

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.

Identify one advantage of using a two-dimensional array for this purpose.

Assume that the queue Q holds the following data:

The reversed queue Q would be:

Construct an algorithm in pseudocode for reversing the queue using a stack data structure.

You may assume that the data in the queue is input and a new empty stack is created.
Only the standard queue and stack operations are allowed.

Outline one disadvantage of solving problems recursively.

Deduce the purpose of the method mystery(A,R).

To avoid inefficient use of memory, a new algorithm for the method rotate(N,A) is constructed.

The N × N two-dimensional array A should be rotated clockwise by 90°, without the use of any additional arrays.

One way of rotating the two-dimensional array A clockwise by 90° is to transpose A, and then reverse each row of A.

The transpose of A is formed by turning all the rows of A into columns. For example, the value in the first row and third column (A[1][3]) is swapped with the value in the third row and first column (A[3][1]).

Construct the new algorithm in pseudocode for the method rotate(N,A) described above.

Explain the benefits of using a binary search tree, compared to a stack, when searching for a specific item.

Construct pseudocode that will read PASSENGERS into the two-dimensional array, 2D_ARRAY.

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().

Construct the pseudocode that will find how many customers live in the city of Cardiff and display the results.

Construct an algorithm that will enable the company to print the mailing labels for all customers called Jones who live in Cardiff.

A third stack, FLOFRU, is needed. It should contain all the data from FLOWERS  and FRUITS and will store it as shown below

Describe how the FLOFRU stack could be created.

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 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.

Describe the steps required to calculate the sum of all numbers held in this circular linked list.