A2 - CS - End of Unit 19 test

Joseph is taking a toy apart. Each time he removes an item from the toy, he writes the name of the item at the bottom of a paper list. When he rebuilds the toy, he puts the items back together working from the bottom of the list.

Joseph writes a computer program to create the list using a stack, Parts.

(a) Describe a stack structure. [1]

(i) Describe the purpose of the variable StackPointer. [1]

Use the table below to show the contents of the stack, Parts, and its pointer after the following code is run. [3]

POP()

POP()

PUSH("Light 1")

PUSH("Light 2")

PUSH("Wheel 1")

POP()

POP()

The recursive algorithm for the Calculate() function is defined as follows:

(i) State what is meant by a recursive algorithm. [1]

(ii) State the line number in Calculate() where the recursive call takes place. [1]

The function in Q5 is called with Calculate(3).

Dry run the function and complete the trace table below. State the final value returned. Show your working. [6]

A recursive algorithm within a subroutine can be replaced with an iterative algorithm.

(i) Describe one problem that can occur when running a subroutine that has a recursive algorithm. [2]

(ii) Rewrite the Calculate() function (of above question) in pseudocode, using an iterative algorithm. [5]

A linked list abstract data type (ADT) is created. This is implemented as an array of records. The records are of type ListElement.

An example of a record of ListElement is shown in the following table.

(i) Use pseudocode to write a definition for the record type, ListElement. [3]

(ii) Use pseudocode to write an array declaration to reserve space for only 15 nodes of type ListElement in an array, CountryList. The lower bound element is 1. [2]