Arrays (Cambridge (CIE) A Level Computer Science): Exam Questions

An exam paper has a maximum of 75 marks. One of five pass grades (A to E) is assigned, depending on the mark obtained. The lowest mark for a given grade is known as the grade boundary. For example, if the grade boundary for an A grade is 65 marks, then any candidate who achieves a mark of 65 or above will be awarded an A. A grade of U is awarded for marks below the E grade boundary.

The five grade boundaries are stored in a global 1D array GradeBoundary of type integer.

For example:

A global 2D array Result of type integer contains candidate marks for the exam. Each row relates to one candidate. Column 1 contains the candidate mark and column 2 contains the unique candidate ID.

For example, for the fourth and fifth candidates:

There are more rows in the array than candidates who sit the exam. Any unused rows will be at the end of the array.

Candidate papers that are given a mark within two marks of any grade boundary must be checked.

For example, given the values in the example grade boundaries above, any paper that was awarded between 41 and 45 marks (inclusive) would need to be checked.

A program is being written to identify papers that need to be checked.

The programmer has defined the first program module as follows:

Write pseudocode for module CheckMark().

A second module is defined:

Write pseudocode for module CheckAll().

CheckMark() must be used to check each individual mark.

The requirements have been changed. Conceal() will now be written as a procedure which will process 100 card numbers each time it is called.

The card numbers will be stored in a 2D array CardNumber. The original string will be stored in column one and the modified string in column two.

Write pseudocode to declare the array.

The implementation of a linked list uses an integer variable and a 1D array List of type Node.

Record type Node is declared in pseudocode as follows:

TYPE Node
DECLARE Data : STRING
DECLARE Pointer : INTEGER
ENDTYPE

The array List is declared in pseudocode as follows:

DECLARE List : ARRAY[1:200] OF Node

The linked list will operate as follows:

• Integer variable HeadPointer will store the array index for the first node in the linked list.

• The Pointer field of a node contains the index value of the next array element (the next node) in the linked list.

• The value 0 is used as a null pointer.

Give the range of valid values that could be assigned to variable HeadPointer.

An alternative algorithm to determine if a paper needs to be checked uses a global 1D array Check, containing 76 elements of type BOOLEAN. The indices of the array are from 0 to 75 (inclusive), corresponding to the range of possible marks.

An element value in Check is TRUE if the index is within 2 marks of a grade boundary. For example, in the case where the C grade boundary is 43 the corresponding part of the Check array would be as follows:

The mark for a given paper is stored in variable Mark.

Describe how an algorithm would use the Check array to determine whether this paper should be checked.

The diagram shows an Abstract Data Type (ADT) representation of a linked list after data items have been added.

• PS is the start pointer.

• PF is the free list pointer.

• Labels Df, Dc, Db and Dy represent the data items of nodes in the list.

• Labels Fg, Fh, Fm and Fw represent the data items of nodes in the free list.

• The symbol Ø represents a null pointer.

A program will be written to include a linked list to store alphanumeric user IDs.

The design uses two variables and two 1D arrays to implement the linked list.
Each array element contains data of a single data type and not a record.

The statements below describe the design.

Complete the statements.

The two variables will be of type ........................................................................... .

The two variables will be used as ....................................................................... to the arrays.

The values stored in the two variables will indicate .............................................. .

The first 1D array will be of type ............................................................................. .

The first 1D array will be used to ............................................................................ .

The second 1D array will be of type ....................................................................... .

The second 1D array will be used to ...................................................................................... .

A factory needs a program to help manage its production of items.

Data will be stored about each item.

The data for each item will be held in a record structure of type Component.

The programmer has started to define the fields that will be needed as shown in the table.

A 1D array Item of 2000 elements will store the data for all items.

Write pseudocode to declare the Item array.

The value zero denotes the split between the two parts of the sequence.

The requirement changes and now there may be up to 20 parts.

(i) Identify a suitable data structure that could be used to store the different total values.

[2]

(ii) Describe three benefits of using the data structure given in part (b)(i).

[3]

A global array is declared in pseudocode as follows:

DECLARE Data : ARRAY[1:150] OF STRING

A function TooMany() will:

1. take two parameters:

• a string (the search string)

• an integer (the maximum value)

2. count the number of strings in the array that exactly match the search string

3. return TRUE if the count is greater than the maximum value, otherwise will return FALSE

The global array is changed to a 2D array, organised as 150 rows by 2 columns. It is declared in pseudocode as follows:

DECLARE Data : ARRAY[1:150, 1:2] OF STRING

The algorithm for the function in part (a) is changed. Strings will only be counted if both of the following conditions are true:

• The current row is an even number.

• The search string exactly matches the value in either column.

Write pseudocode to check these conditions.

Assume that the row index is contained in variable Row and the search string in variable Search.

A global 1D array of integers contains four elements, which are assigned values as shown:

Mix[1] 1
Mix[2] 3
Mix[3] 4
Mix[4] 2

A procedure Process() manipulates the values in the array.

The procedure is written in pseudocode:

PROCEDURE Process(Start : INTEGER)
DECLARE Value, Index, Count : INTEGER

Index Start
Count 0

REPEAT
Value Mix[Index]
Mix[Index] Mix[Index] - 1
Index Value
Count Count + 1
UNTIL Count = 5

Mix[4] Count * Index

ENDPROCEDURE

Complete the trace table on the opposite page by dry running the procedure when it is called as follows:

CALL Process(3)

A class of students are developing a program to send data between computers. Many computers are connected together to form a wired network. Serial ports are used to connect one computer to another.

Each computer:

• is assigned a unique three-digit ID

• has three ports, each identified by an integer value

• is connected to between one and three other computers.

Data is sent as individual message strings.
Each string contains the destination ID (the ID of the computer that is to receive the message) followed by the data:

<DestinationID ><Data>

Messages may pass through several computers on the way to their destination.
When a message arrives at a computer, that is not the destination, the program needs to forward it on to another computer using one of its serial ports.

The port to use is obtained from information that is stored in an array RouteTable.

RouteTable is a global 2D array of integers. It is declared in pseudocode as follows:

DECLARE RouteTable : ARRAY[1:6,1:3] OF INTEGER

The values in the first two columns of RouteTable define a range of ID values.
Column 3 gives the corresponding port number to use when forwarding the message to a computer with an ID within this range.

For example, the contents of RouteTable could be:

In this example, a message that arrives with a DestinationID of "283" will be forwarded using port 2.

Row 3 in the example shows an unused row. These may occur anywhere. Unused rows have the column 1 element set to −1. The value of unused elements in the other two columns is undefined.

The programmer has defined the first program module as follows:

Write pseudocode for module GetPort().

Assume DestinationID contains a valid three-digit string.

Data is a 1D array of integers, containing 30 elements. All element values are unique.

The 30 data values could have been stored in separate variables rather than in an array.

Explain the benefits of using an array when designing a solution to part (a).

The requirement changes. Array Data needs to hold 120 elements and each value may include a decimal place.

Write a pseudocode statement to declare the modified array.

Procedure RandList() is modified so that the random numbers are also written into a 1D array Result.

A new module is written to confirm that the numbers in the array are in ascending order.

This module contains an IF statement that performs a comparison between elements:

IF (Result[x + 1] = Result[x]) OR (Result[x] > Result[x + 1]) THEN
Sequence FALSE
ENDIF

Write a simplified version of the conditional clause.