Question 1[6 Marks]

Given 2D array called ARRAY[row index][column index] of size 4x3 (rows x columns) in row order, construct an algorithm that outputs a new 1D array called BIGGEST containing the biggest number in each row. The algorithm must also work for a 2D array containing only negative numbers.

Question 2[13 Marks]

At the moment marathon runners cross the finishing line of a race, their names are added to a stack called RUNNERS. Here we can see “Ellie” has finished first and “Jessie” last. “Jessie” is at the top of the stack.

(a).

Using pseudocode, construct a procedure that will search the stack RUNNERS for a name given via standard input. Once found, output the finishing place of the specified runner as a number. For example, given an input string of "Joel" the procedure will output the number 2 to indicate Joel finished in 2nd place. If a runner's name is not found then the procedure should output the message "Runner not found". Assume all names are unique. You may empty the stack in the process and the number of elements in the stack are unknown.

[6](b).

Outline why the use of a queue would make this algorithm simpler and more efficient than using a stack.

[2]Another stack called TIMES saves runners finishing times as they cross the finish line.

(c).

Stacks RUNNERS and TIMES are formed as previously described and contain the results of a particular competition where 101 runners successfully finish a race. Given RUNNERS and TIMES, wrote pseudocode to populate a 2D array called RESULTS such that the first column contains the names of all those runners who finished the race and the second column contains their respective times in ascending rank order. For example, RESULTS[7][1] should contain the time of the runner who finished in 94th place, that is, having only ran faster than seven people (eighth last).

[3](d).

Using RESULTS, state the single line of pseudocode that represents the name of the runner with the median finishing time.

[2]Question 3[4 Marks]

Construct an algorithm using an empty stack called STACK to reverse an array containing 7 elements called ARRAY.

Question 4[5 Marks]

Consider the following algorithm.

function fun(N)
if N = 0 then
return 1
else if (N % 2 == 0)
return N - fun(N-1)
else
return N + 2 × fun(N-1)
end if
end function

(a).

State what would occur if the first "if statement" were removed.

[1](b).

Trace the algorithm when N=4 by completing the following trace table.

[3]N | fun(N) returns
-------------------
4 |
3 |
2 |
1 |
0 |

(c).

State the final output of the algorithm when N=4.

[1]Question 5[15 Marks]

A movie cinema uses a collection, TICKETS to store their ticket information. In every first item an integer is stored and every second item stores a string that has the customer’s name. The first number of the integer represents the aisle and the second number the row at which their seat is. For example, Rufus has a ticket for a seat in aisle 2 and row 3.

(a).

Identify a problem with storing tickets in a collection and why a 2D array would be more appropriate

[2](b).

Create an algorithm that will read through TICKETS and output out each ticket holder’s name without printing their seat number

[4](c).

Using the collection, TICKETS, populate a 2D array called SEATS that has dimensions 12x10 representing 12 rows and 10 aisles with the names of the ticket holders who are assigned to those respective seats. For example TICKETS[0][0] should hold “Sally” and TICKETS[1][2] should hold “Rufus”. Empty seats also are populated with the string ‘E’ to indicate that they are unassigned.

[9]Question 6[3 Marks]

Contrast the use of a linked list with an array for capturing streaming measurements from a weather station hygrometer (a device which measures humidity).

Question 7[6 Marks]

(a).

State what is meant by the term ‘dynamic data structure’

[1]Consider the following circularly linked list

(b).

Given the node prior (called PREV_NODE) to the correct insert location for a new node containing the integer 32, describe how the new node should be added to the linked list in such a way that the list remains sorted.

[3](c).

Outline why it would be more difficult to add 32 to the front of a static array containing [16, 8, 4] than the process described in part b).

[2]Question 8[12 Marks]

(a).

With respect to the binary search tree above, list all the nodes values according to the order in which they are visited by the following tree traversals.

(i).

In-order

[1](ii).

Pre-order

[1](iii).

Post-order

[1](b).

Describe how the post-order tree traversal algorithm works.

[3](c).

In contrast to arrays, outline two benefits of using binary search trees.

[4](d).

Outline one situation where using a binary search trees would not be useful.

[2]Question 9[7 Marks]

In consideration of the binary tree above

(a).

State the value contained in each of the following nodes

(i).

Root

[1](ii).

Right-child and sibling respectively of the node containing 65

[2](iii).

Leaves of the largest possible left subtree

[2](b).

Draw a resulting tree if the node containing the value 65 were removed

[2]9 Questions71 MarksPremium

9 Uses65 Views1 Like

Login or Create an Account to view question mark schemes and download a PDF of this test