Data is stored in the array NameList[1:10]. This data is to be sorted.
Complete this pseudocode algorithm for an insertion sort. [7]
FOR ThisPointer ← 2 TO _______
// use a temporary variable to store item which is to
// be inserted into its correct location
Temp ← NameList[ThisPointer]
Pointer ← ThisPointer – 1
WHILE (NameList[Pointer] > Temp) AND _______
// move list item to next location
NameList[_______] ← NameList[_______]
Pointer ← _______
ENDWHILE
// insert value of Temp in correct location
NameList[_______] ← _______
ENDFOR
5 points
5
Question 2
2.
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()
5 points
5
Question 3
3.
A 1D array, Parts, is used to implement the stack in Q2 Parts is declared as:
DECLARE Parts : ARRAY[0 : 19] OF STRING
The procedure POP outputs the last element that has been pushed onto the stack and replaces it with a '*'. Complete the pseudocode for the procedure POP.
PROCEDURE POP
IF _______ = _______
THEN
OUTPUT "The stack is empty"
ELSE
StackPointer ← _______
OUTPUT _______
Parts[StackPointer] ←_______
ENDIF
ENDPROCEDURE
4 points
4
Question 4
4.
In the above question, the procedure PUSH() puts the parameter onto the stack.
Complete the pseudocode for the procedure PUSH().
PROCEDURE PUSH(BYVALUE Value : String)
IF StackPointer > _______
THEN
OUTPUT "Stack full"
ELSE
_______ ← _______
StackPointer ←_______
ENDIF
ENDPROCEDURE
2 points
2
Question 5
5.
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]
6 points
6
Question 6
6.
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]
7 points
7
Question 7
7.
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]
5 points
5
Question 8
8.
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]
5 points
5
Question 9
9.
The program in Q8 stores the position of the last node in the linked list in LastNode. The last node always has a Pointer value of -1. The position of the node at the head of the list is stored in ListHead.
After some processing, the array and variables are in the following state.
A recursive algorithm searches the list for a value, deletes that value, and updates the required pointers. When a node value is deleted, it is set to empty "" and the node is added
to the end of the list.
A node value is deleted using the pseudocode statement
CALL DeleteNode("England", 1, 0)
Complete the following pseudocode to implement the DeleteNode procedure.