A2 - CS - End of Unit 19 test - Soheil Meskini | Biblioteka

Instrukcije

Answer all the questions.

7

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

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

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

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

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

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

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

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

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.

null

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.

PROCEDURE DeleteNode(NodeValue: STRING, ThisPointer : INTEGER, PreviousPointer : INTEGER)

IF CountryList[ThisPointer].Value = NodeValue

THEN

CountryList[ThisPointer].Value ← ""

IF ListHead =

THEN

ListHead ←

ELSE

CountryList[PreviousPointer].Pointer ← CountryList[ThisPointer].Pointer

ENDIF

CountryList[LastNode].Pointer ←

LastNode ← ThisPointer

ELSE

IF CountryList[ThisPointer].Pointer <> -1

THEN

CALL DeleteNode(NodeValue, , ThisPointer)

ELSE

OUTPUT "DOES NOT EXIST"

ENDIF

ENDPROCEDURE

A2 - CS - End of Unit 19 test

A2 - CS - End of Unit 19 test

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]

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]

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]

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]