Arrays — Paper 2 · A Level Computer Science 9618

6 The following diagram represents an Abstract Data Type (ADT) for a linked list. A C D E Ø The free list is as follows: Ø (a) Explain how a node containing data value B is added to the list in alphabetic sequence. … … … … … … … [4] (b) Describe how the linked list in part (a) may be implemented using variables and arrays. … … … … [2]

6 marks

Mark scheme: 6(a) One mark per point: 4 1 Check for a free node 2 Search for correct insertion point 3 Assign data value B to first node in free list / node pointed to by start pointer of free list 4 Pointer from A will be changed to point to node containing B (instead of C) 5 Pointer from B will be changed to point to node containing C 6 Start pointer in free list moved to point to next free node Note: max 4 marks 6(b) One mark per point: 2 • An array (1D) to store the data and a second array (1D) to store the pointers • An (integer) variable to hold the start pointer and an (integer) variable to store the next free pointer ALTERNATIVE: • Define a record type comprising a data element and a pointer and declare an array (1D) of this type • An integer variable to hold the start pointer and an integer variable to store the next free pointer

This question in 9618/21 May/June 2021

7 A program is needed to take a string containing a full name and produce a new string of initials. Some words in the full name will be ignored. For example, "the", "and", "of", "for" and "to" may all be ignored. Each letter of the abbreviated string must be upper case. For example: Full name Initials Integrated Development Environment IDE The American Standard Code for Information Interchange ASCII The programmer has decided to use a global variable FNString of type STRING to store the full name. It is assumed that: • words in the full name string are separated by a single space character • space characters will not occur at the beginning or the end of the full name string • the full name string contains at least one word. The programmer has started to define program modules as follows: Module Description • Called with an INTEGER as a parameter, representing the number of a word in FNString. • Returns the character start position of that word in FNString or GetStart() returns –1 if that word does not exist • For example: if FNString contains the string "hot and cold", GetStart(3) returns 9 • Called with a parameter representing the position of the first character of a word in FNString GetWord() • Returns the word from FNString • For example: if FNString contains the string "hot and cold", GetWord(9) returns "cold" (a) Write pseudocode for the module GetStart(). … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … [7] (b) The programmer has decided to use a global ten-element 1D array IgnoreList of type STRING to store the ignored words. Unused elements contain the empty string ("") and may occur anywhere in the array. A new module AddWord() is needed as follows: Module Description • Called with a parameter representing a word • Stores the word in an unused element of the IgnoreList array AddWord() and returns TRUE • Returns FALSE if the array was already full or if the word was already in the array Write a detailed description of the algorithm for AddWord(). Do not include pseudocode statements in your answer. … … … … … … … … … … … … [4]

11 marks

Mark scheme: 7(a) FUNCTION GetStart (WordNum : INTEGER) RETURNS INTEGER 7 DECLARE Index, ThisPos, NumFound : INTEGER DECLARE ThisChar : Char CONSTANT SPACECHAR = ' ' Index ← -1 Numfound ← 0 ThisPos ← 1 IF WordNum = 1 THEN // if looking for word 1... Index ← 1 // Word 1 always starts at index // position 1 ELSE // Otherwise start counting spaces... WHILE ThisPos <= LENGTH(FNString) AND Index = -1 ThisChar ← MID(FNString, ThisPos, 1) IF ThisChar = SPACECHAR THEN NumFound ← NumFound + 1 IF NumFound = WordNum - 1 THEN Index ← ThisPos + 1 // the start of the // required word ENDIF ENDIF ThisPos ← ThisPos + 1 ENDWHILE ENDIF RETURN Index ENDFUNCTION 1 mark for each of the following: 1 Function heading, including return type and function end 2 Loop counting spaces until word found or end of FNString 3 extract a character from FNString in a loop 4 compare with SPACECHAR and increment count if equal in a loop 5 compare count with WordNum - 1 (depending on initialisation value) in a loop 6 if equal then set flag or Index to ThisPos + 1 in a loop 7 Return Index (correctly in all cases / following a reasonable attempt) 8 Works for special case when looking for word 1 Note: Max 7 marks 7(b) Marks awarded for any reference to each of the following steps of the algorithm: 4 1 Mention of variable for use as array index 2 Use of a loop (to check through the array) 3 If word is the same as the current array element then return FALSE / set flag 4 If word not already in array, loop to find unused element (second loop) 5 Store word in unused element and return TRUE, otherwise return FALSE VARIATION: 1 Mention of variable for use as array index 2 Use of a loop (to check through the array) 3 Save index of (first) unused element found 4 If word is the same as the current array element then return FALSE / set flag 5 If word not already in array and unused element available, store word in unused element and return TRUE otherwise return FALSE Note: Max 4 marks 7(c) FUNCTION GetWord (Index : INTEGER) RETURNS STRING 5 DECLARE NextWord : STRING DECLARE Done : BOOLEAN DECLARE ThisChar : CHAR DECLARE Index : INTEGER CONSTANT SPACECHAR = ' ' NextWord ← "" Done ← FALSE REPEAT ThisChar ← MID(FNString, Index, 1) IF ThisChar <> SPACECHAR THEN NextWord ← NextWord & ThisChar // build up NextWord ENDIF IF ThisChar = SPACECHAR OR Index = LENGTH(FNString) THEN Done ← TRUE ENDIF Index ← Index + 1 UNTIL Done = TRUE RETURN NextWord ENDFUNCTION 1 mark for each of the following: 1 Conditional loop 2 Extract char from FNString and compare with SPACECHAR in a loop 3 Concatenate with NextWord if not SPACECHAR in a loop 4 Exit loop when SPACECHAR encountered or when end of FNString reached 5 Return NextWord (after reasonable attempt at forming, and must have been initialised) 7(c) The ‘length and substring’ solution: FUNCTION GetWord (Index : INTEGER) RETURNS STRING DECLARE Done : BOOLEAN DECLARE ThisChar : CHAR DECLARE Index, NextPos : INTEGER CONSTANT SPACECHAR = ' ' Done ← FALSE NextPos ← Index // must be at least one character in // the required word REPEAT ThisChar ← MID(FNString, NextPos, 1) IF ThisChar = SPACECHAR OR NextPos = LENGTH(FNString) THEN Done ← TRUE ELSE NextPos ← NextPos + 1 ENDIF UNTIL Done = TRUE IF NextPos = LENGTH(FNString) THEN NextPos ← NextPos - 1 // special case when last word ENDIF RETURN MID(FNString, Index, NextPos - Index) ENDFUNCTION 1 mark for each of the following: 1 Conditional loop 2 ...extract char from FNString and compare with SPACECHAR in a loop 3 .. increment count if word continues 4 Exit loop when SPACECHAR encountered or when end of FNString reached 5 Apply substring function and Return

This question in 9618/21 May/June 2021

5 (a) A student is learning about arrays. She wants to write a program to: • declare a 1D array RNum of 100 elements of type INTEGER • assign each element a random value in the range 1 to 200 inclusive • count and output how many numbers generated were between 66 and 173 inclusive. (i) Write pseudocode to represent the algorithm. … … … … … … … … … … … … … … [6] (ii) The student decides to modify the algorithm so that each element of the array will contain a unique value. Describe the changes that the student needs to make to the algorithm. … … … … … … [3] (b) The following is a pseudocode function. Line numbers are given for reference only. 01 FUNCTION StringClean(InString : STRING) RETURNS STRING 02 03 DECLARE NextChar : CHAR 04 DECLARE OutString : STRING 05 DECLARE Counter : INTEGER 06 07 OutString "" 08 09 FOR Counter 1 TO LENGTH(InString) 10 NextChar MID(InString, Counter, 1) 11 NextChar LCASE(NextChar) 12 IF NOT((NextChar < 'a') OR (NextChar > 'z')) THEN 13 OutString OutString & NextChar 14 ENDIF 15 NEXT Counter 16 17 RETURN OutString 18 19 ENDFUNCTION (i) Examine the pseudocode and complete the following table. Answer Give a line number containing an example of an initialisation statement. Give a line number containing the start of a repeating block of code. Give a line number containing a logic operation. Give the number of parameters to the function MID(). [4] (ii) Write a simplified version of the statement in line 12. … … [2]

15 marks

Mark scheme: 5(a)(i) DECLARE RNum : ARRAY[1:100] OF INTEGER 6 DECLARE Index, Count : INTEGER Count ← 0 FOR Index ← 1 TO 100 RNum[Index] ← INT(RAND(200)) + 1 IF RNum[Index] >= 66 AND RNum[Index] <= 173 THEN Count ← Count + 1 ENDIF NEXT Index OUTPUT Count Mark as follows: 1 Array declaration 2 Loop for 100 iterations 3 Array element index 'syntax' (left-hand side of assignment expression) in a loop 4 Use of RAND() to generate value in range (and assign to array element) in a loop 5 Check if random number within range and if so, increment count in a loop 6 Output of count (following a reasonable attempt) after the loop 5(a)(ii) One mark per bullet / sub-bullet point 3 1 Initialise the array to a rogue value (to indicate 'unassigned' element) 2 Add a conditional loop to: 3 Generate and store a random number (in the correct range) 4 Check the stored number against values already in the array 5 If the stored number is found then generate another random value 6 Otherwise add it to the array (and exit loop) Note: Max 3 marks 5(b)(i) 4 Answer Give a line number containing an example of an 07 initialisation statement. Give a line number containing the start of a repeating 09 / 10 block of code. Give a line number containing a logic statement. 12 Give the number of parameters of function MID(). 3 One mark for each row 5(b)(ii) IF (NextChar >= 'a') AND (NextChar <= 'z') THEN 2 One mark for IF ... AND ... One mark for both conditions

This question in 9618/22 May/June 2021

6 The following diagram represents an Abstract Data Type (ADT) for a linked list. A C D E Ø The free list is as follows: Ø (a) Explain how a node containing data value B is added to the list in alphabetic sequence. … … … … … … … [4] (b) Describe how the linked list in part (a) may be implemented using variables and arrays. … … … … [2]

6 marks

Mark scheme: 6(a) One mark per point: 4 1 Check for a free node 2 Search for correct insertion point 3 Assign data value B to first node in free list / node pointed to by start pointer of free list 4 Pointer from A will be changed to point to node containing B (instead of C) 5 Pointer from B will be changed to point to node containing C 6 Start pointer in free list moved to point to next free node Note: max 4 marks 6(b) One mark per point: 2 • An array (1D) to store the data and a second array (1D) to store the pointers • An (integer) variable to hold the start pointer and an (integer) variable to store the next free pointer ALTERNATIVE: • Define a record type comprising a data element and a pointer and declare an array (1D) of this type • An integer variable to hold the start pointer and an integer variable to store the next free pointer

This question in 9618/23 May/June 2021

7 A program is needed to take a string containing a full name and produce a new string of initials. Some words in the full name will be ignored. For example, "the", "and", "of", "for" and "to" may all be ignored. Each letter of the abbreviated string must be upper case. For example: Full name Initials Integrated Development Environment IDE The American Standard Code for Information Interchange ASCII The programmer has decided to use a global variable FNString of type STRING to store the full name. It is assumed that: • words in the full name string are separated by a single space character • space characters will not occur at the beginning or the end of the full name string • the full name string contains at least one word. The programmer has started to define program modules as follows: Module Description • Called with an INTEGER as a parameter, representing the number of a word in FNString. • Returns the character start position of that word in FNString or GetStart() returns –1 if that word does not exist • For example: if FNString contains the string "hot and cold", GetStart(3) returns 9 • Called with a parameter representing the position of the first character of a word in FNString GetWord() • Returns the word from FNString • For example: if FNString contains the string "hot and cold", GetWord(9) returns "cold" (a) Write pseudocode for the module GetStart(). … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … [7] (b) The programmer has decided to use a global ten-element 1D array IgnoreList of type STRING to store the ignored words. Unused elements contain the empty string ("") and may occur anywhere in the array. A new module AddWord() is needed as follows: Module Description • Called with a parameter representing a word • Stores the word in an unused element of the IgnoreList array AddWord() and returns TRUE • Returns FALSE if the array was already full or if the word was already in the array Write a detailed description of the algorithm for AddWord(). Do not include pseudocode statements in your answer. … … … … … … … … … … … … [4]

11 marks

Mark scheme: 7(a) FUNCTION GetStart (WordNum : INTEGER) RETURNS INTEGER 7 DECLARE Index, ThisPos, NumFound : INTEGER DECLARE ThisChar : Char CONSTANT SPACECHAR = ' ' Index ← -1 Numfound ← 0 ThisPos ← 1 IF WordNum = 1 THEN // if looking for word 1... Index ← 1 // Word 1 always starts at index // position 1 ELSE // Otherwise start counting spaces... WHILE ThisPos <= LENGTH(FNString) AND Index = -1 ThisChar ← MID(FNString, ThisPos, 1) IF ThisChar = SPACECHAR THEN NumFound ← NumFound + 1 IF NumFound = WordNum - 1 THEN Index ← ThisPos + 1 // the start of the // required word ENDIF ENDIF ThisPos ← ThisPos + 1 ENDWHILE ENDIF RETURN Index ENDFUNCTION 1 mark for each of the following: 1 Function heading, including return type and function end 2 Loop counting spaces until word found or end of FNString 3 extract a character from FNString in a loop 4 compare with SPACECHAR and increment count if equal in a loop 5 compare count with WordNum - 1 (depending on initialisation value) in a loop 6 if equal then set flag or Index to ThisPos + 1 in a loop 7 Return Index (correctly in all cases / following a reasonable attempt) 8 Works for special case when looking for word 1 Note: Max 7 marks 7(b) Marks awarded for any reference to each of the following steps of the algorithm: 4 1 Mention of variable for use as array index 2 Use of a loop (to check through the array) 3 If word is the same as the current array element then return FALSE / set flag 4 If word not already in array, loop to find unused element (second loop) 5 Store word in unused element and return TRUE, otherwise return FALSE VARIATION: 1 Mention of variable for use as array index 2 Use of a loop (to check through the array) 3 Save index of (first) unused element found 4 If word is the same as the current array element then return FALSE / set flag 5 If word not already in array and unused element available, store word in unused element and return TRUE otherwise return FALSE Note: Max 4 marks 7(c) FUNCTION GetWord (Index : INTEGER) RETURNS STRING 5 DECLARE NextWord : STRING DECLARE Done : BOOLEAN DECLARE ThisChar : CHAR DECLARE Index : INTEGER CONSTANT SPACECHAR = ' ' NextWord ← "" Done ← FALSE REPEAT ThisChar ← MID(FNString, Index, 1) IF ThisChar <> SPACECHAR THEN NextWord ← NextWord & ThisChar // build up NextWord ENDIF IF ThisChar = SPACECHAR OR Index = LENGTH(FNString) THEN Done ← TRUE ENDIF Index ← Index + 1 UNTIL Done = TRUE RETURN NextWord ENDFUNCTION 1 mark for each of the following: 1 Conditional loop 2 Extract char from FNString and compare with SPACECHAR in a loop 3 Concatenate with NextWord if not SPACECHAR in a loop 4 Exit loop when SPACECHAR encountered or when end of FNString reached 5 Return NextWord (after reasonable attempt at forming, and must have been initialised) 7(c) The ‘length and substring’ solution: FUNCTION GetWord (Index : INTEGER) RETURNS STRING DECLARE Done : BOOLEAN DECLARE ThisChar : CHAR DECLARE Index, NextPos : INTEGER CONSTANT SPACECHAR = ' ' Done ← FALSE NextPos ← Index // must be at least one character in // the required word REPEAT ThisChar ← MID(FNString, NextPos, 1) IF ThisChar = SPACECHAR OR NextPos = LENGTH(FNString) THEN Done ← TRUE ELSE NextPos ← NextPos + 1 ENDIF UNTIL Done = TRUE IF NextPos = LENGTH(FNString) THEN NextPos ← NextPos - 1 // special case when last word ENDIF RETURN MID(FNString, Index, NextPos - Index) ENDFUNCTION 1 mark for each of the following: 1 Conditional loop 2 ...extract char from FNString and compare with SPACECHAR in a loop 3 .. increment count if word continues 4 Exit loop when SPACECHAR encountered or when end of FNString reached 5 Apply substring function and Return

This question in 9618/23 May/June 2021

1 (a) A programmer applies decomposition to a problem that she has been asked to solve. Describe decomposition. … … … … … … [2] (b) The following pseudocode assigns a value to an element of an array: ThisArray[n] 42 ← Complete the following table by writing the answer for each row. Answer The number of dimensions of ThisArray The technical terms for minimum and maximum values that the variable n may take The technical term for the variable n in the pseudocode statement [3] (c) Complete the pseudocode expressions so that they evaluate to the values shown. Any functions and operators used must be defined in the insert. Expression Evaluates to … 67 ('C') … 54 2 * ("27") … 13 (27 / … ) "Sub" & … ("Abstraction" , … , … ) "Subtract" [4] (d) Evaluate the expressions given in the following table. The variables have been assigned values as follows: PumpOn TRUE ← PressureOK TRUE ← HiFlow FALSE ← Expression Evaluates to PressureOK AND HiFlow PumpOn OR PressureOK NOT PumpOn OR (PressureOK AND NOT HiFlow) NOT (PumpOn OR PressureOK) AND NOT HiFlow [2]

11 marks

Mark scheme: Question Answer Marks 1(a) The process involves: 2 1 Breaking down a problem / task into sub problems / steps / smaller parts 2 In order to explain / understand // easier to solve the problem 3 Leading to the concept of program modules // assigning problem parts to teams Max 2 1(b) 3 Answer The number of dimensions of ThisArray 1 The technical terms for minimum and Lower bound, upper bound maximum values that variable n may take The technical term for the variable n in the Index / Subscript pseudocode expression. One mark per row 1(c) 4 Expression Evaluates to ASC('C') 67 2 * STR_TO_NUM ("27") 54 INT(27 / 2) 13 "Sub" & MID("Abstraction" , 4 , 5) "Subtract" One mark per row Function names must be exactly as shown 1(d) 2 Expression Evaluates to PressureOK AND HiFlow FALSE PumpOn OR PressureOK TRUE NOT PumpOn OR (PressureOK AND NOT HiFlow) TRUE NOT (PumpOn OR PressureOK) AND NOT HiFlow FALSE 1 mark for any two rows correct 2 marks for all rows correct.

This question in 9618/22 Oct/Nov 2021

8 A program allows a user to save passwords used to login to websites. A stored password is inserted automatically when the user logs into the corresponding website. A student is developing a program to generate a password. The password will be of a fixed format, consisting of three groups of four alphanumeric characters. The groups are separated by the hyphen character '-'. An example of a password is: "FxAf-3haV-Tq49" A global 2D array Secret of type STRING stores the passwords together with the website domain name where they are used. Secret contains 1000 elements organised as 500 rows by 2 columns. Unused elements contain the empty string (""). These may occur anywhere in the array. An example of a part of the array is: Array element Value Secret[27, 1] "www.thiswebsite.com" Secret[27, 2] Secret[28, 1] "www.thatwebsite.com" Secret[28, 2] Note: • For security, passwords are stored in an encrypted form, shown as "" in the example. • The passwords cannot be used without being decrypted. • Assume that the encrypted form of a password will not be an empty string. The programmer has started to define program modules as follows: Module Description RandomChar() • Generates a single random character from within one of the following ranges: ○ 'a' to 'z' ○ 'A' to 'Z' ○ '0' to '9' • Returns the character Encrypt() • Takes a password as a parameter of type string • Returns the encrypted form of the password as a string Decrypt() • Takes an encrypted password as a parameter of type string • Returns the decrypted form of the password as a string For reference, relevant ASCII values are as follows: Character range ASCII range 'a' to 'z' 97 to 122 'A' to 'Z' 65 to 90 '0' to '9' 48 to 57 (a) Write pseudocode for module RandomChar(). You may wish to refer to the insert for a description of the CHR() function. Other functions may also be required. … … … … … … … … … … … … … … … … … … … [6] (b) A new module is defined as follows: Module Description FindPassword() • Takes a website domain name as a parameter of type string • Searches for the website domain name in the array Secret • If the website domain name is found, the decrypted password is returned • If the website domain name is not found, a warning message is output, and an empty string is returned Write pseudocode for module FindPassword(). Assume that modules Encrypt() and Decrypt() have already been written. … … … … … … … … … … … … … … … … … … … …

6 marks

Mark scheme: 8(a) FUNCTION RandomChar() RETURNS CHAR 6 DECLARE ThisRange : INTEGER DECLARE ThisChar : CHAR //First select the range ThisRange  INT(RAND(3)) + 1 // 1 to 3 CASE OF ThisRange 1: ThisChar  CHR(INT(RAND(26) + 65)) // 65 to 90: 'A' to 'Z' ThisChar  LCASE(ThisChar) // 'a' to 'z' 2: ThisChar  CHR(INT(RAND(26) + 65)) // 65 to 90: A to Z 3: ThisChar  NUM_TO_STR(INT(RAND(10)) // '0' to '9' ENDCASE RETURN ThisChar ENDFUNCTION Mark as follows: 1 Generation of any integer random number 2 Randomly decide which of the three ranges to select 3 Selection structure based on range 4 One alphanumeric character range correct 5 All alphanumeric character ranges correct 6 Return ThisChar, following a reasonable attempt to generate a character in each range 8(b) FUNCTION FindPassword(Name: STRING) RETURNS STRING 7 DECLARE Index : INTEGER DECLARE Password : STRING Password  "" Index  1 WHILE Password = "" AND Index <= 500 IF Secret[Index, 1] = Name THEN Password  Decrypt(Secret[Index, 2]) ELSE Index  Index + 1 ENDIF ENDWHILE IF Password = "" THEN OUTPUT "Domain name not found" ENDIF RETURN Password ENDFUNCTION Mark as follows: 1 Declare all local variables used, attempted solution has to be reasonable 2 Conditional loop while not found and not end of array 3 Compare value of element in column 1 with parameter passed into function 4 ...and use Decrypt() with element in column 2 as parameter 5 …use the return value of Decrypt() 6 Output warning message if parameter not found 7 Return STRING value 8(c) One mark for the name, one for the description 3 Name:  Stub testing Description:  A simple module is written to replace each of the modules.  The simple module will return an expected value // will output a message to show they have been called 8(d) Accept one example of a valid password to Max 2 2 One mark for each password example that breaks one of the rules due to:  Length too long // length too short  Invalid character  Incorrect grouping (including number of hyphens)  Duplicated characters 8(e) One mark for each part: 3  Generate a random integer divisible by 3  Split range into 1/3 and set as numeric  Else alphabetic character

This question in 9618/21 May/June 2022

5 A program will store attendance data about each employee of a company. The data will be held in a record structure of type Employee. The fields that will be needed are as shown: Field Typical value Comment EmployeeNumber 123 A numeric value starting from 1 Name "Smith,Eric" Format: <last name>','<first name> Department "1B" May contain letters and numbers Born 13/02/2006 Must not be before 04/02/1957 Attendance 97.40 Represents a percentage (a) (i) Write pseudocode to declare the record structure for type Employee. … … … … … … … [4] (ii) A 1D array Staff containing 500 elements will be used to store the employee records. Write pseudocode to declare the Staff array. … … [2] (b) There may be more records in the array than there are employees in the company. In this case, some records of the array will be unused. (i) State why it is good practice to have a standard way to indicate unused array elements. … … [1] (ii) Give one way of indicating an unused record in the Staff array. … … [1] (c) A procedure Absentees() will output the EmployeeNumber and the Name of all employees who have an Attendance value of 90.00 or less. Write pseudocode for the procedure Absentees(). Assume that the Staff array is global. … … … … … … … … … … … … … … … … … … [4]

12 marks

Mark scheme: 5(a)(i) TYPE Employee 4 DECLARE EmployeeNumber : INTEGER DECLARE Name : STRING DECLARE Department : STRING DECLARE Born : DATE DECLARE Attendance : REAL ENDTYPE One mark for each: 1. TYPE Employee and ENDTYPE 2. Fields: EmployeeNumber and Name and Department 3. Field: Born 4. Field: Attendance 5(a)(ii) DECLARE Staff : ARRAY [1:500] OF Employee 2 One mark per underlined phrase 5(b)(i) Example answers to Max 1: 1  So that unused elements may be recognised when processing / searching  Otherwise the element may contain old / unexpected data 5(b)(ii) Use of any 'impossible' field value, for example: 1  An EmployeeNumber field. e.g. < 1  An empty string / impossible string e.g. "EMPTY" for name or department  DOB a long time ago...  Zero / Negative value for attendance 5(c) PROCEDURE Absentees() 4 DECLARE Index : INTEGER FOR Index  1 TO 500 IF Staff[Index].EmployeeNumber <> −1 THEN // not empty IF Staff[Index].Attendance <= 90 THEN OUTPUT Staff[Index].EmployeeNumber OUTPUT Staff[Index].Name ENDIF ENDIF NEXT Index ENDPROCEDURE Marks as follows to Max 4: 1 Procedure heading and ending and declaration of loop counter 2 loop through 500 elements 3 attempt to skip unused element 4 test Staff[Index].Attendance <= 90 in a loop 5 if so, output EmployeeNumber and Name fields in a loop

This question in 9618/23 May/June 2022

9 A program allows a user to save passwords used to log in to websites. A stored password is then inserted automatically when the user logs in to the corresponding website. A student is developing a program to generate a strong password. The password will be of a fixed format, consisting of three groups of four alphanumeric characters, separated by the hyphen character '-'. An example of a password is: "FxAf-3hzV-Aq49" A valid password: • must be 14 characters long • must be organised as three groups of four alphanumeric characters. The groups are separated by hyphen characters • may include duplicated characters, provided these appear in different groups. The programmer has started to define program modules as follows: Module Description • Generates a single random character from within one of the following ranges: ○ 'a' to 'z' RandomChar() ○ 'A' to 'Z' ○ '0' to '9' • Returns the character • Takes two parameters: ○ a string ○ a character Exists() • Performs a case-sensitive search for the character in the string • Returns TRUE if the character occurs in the string, otherwise returns FALSE • Generates a valid password Generate() • Uses RandomChar() and Exists() • Returns the password Note: in a case-sensitive comparison, 'a' is not the same as 'A'. (a) Write pseudocode for the module Generate(). … … … … … … … … … … … … … … … … … … … … … … … … … … … [7] (b) A global 2D array Secret of type STRING stores the passwords together with the website domain name where they are used. Secret contains 1000 elements organised as 500 rows by 2 columns. Unused elements contain the empty string (""). These may occur anywhere in the array. An example of part of the array is: Array element Value Secret[27, 1] "www.thiswebsite.com" Secret[27, 2] Secret[28, 1] "www.thatwebsite.com" Secret[28, 2] Note: • For security, the passwords are stored in an encrypted form, shown as "●●●●●●●●●●●●" in the example. • The passwords cannot be used without being decrypted. • You may assume that the encrypted form of a password will not be an empty string. Additional modules are defined as follows: Module Description • Takes a password as a string Encrypt() • Returns the encrypted form of the password as a string • Takes an encrypted password as a string Decrypt() • Returns the decrypted form of the password as a string • Takes a website domain name as a string • Searches for the website domain name in the array Secret • If the website domain name is found, the decrypted password is FindPassword() returned • If the website domain name is not found, an empty string is returned • Takes two parameters as strings: a website domain name and a password • Searches for the website domain name in the array Secret and AddPassword() if not found, adds the website domain name and the encrypted password to the array • Returns TRUE if the website domain name and encrypted password are added to the array, otherwise returns FALSE The first three modules have been written.

7 marks

Mark scheme: 9(a) FUNCTION Generate() RETURNS STRING 7 DECLARE Password, Group : STRING DECLARE NextChar : CHAR DECLARE ACount, BCount : INTEGER CONSTANT HYPHEN = '-' Password  "" FOR ACount  1 TO 3 Group  "" FOR BCount  1 TO 4 REPEAT NextChar  RandomChar() UNTIL Exists(Group, NextChar) = FALSE Group  Group & NextChar NEXT BCount Password  Password & Group & HYPHEN NEXT ACount Password  LEFT(Password, 14) // remove final hyphen RETURN Password ENDFUNCTION Marks as follows to Max 7: 1 Declaration and initialisation of Password as STRING 2 Outer loop for three groups / until password is complete // three group loops 3 Attempt to use of both RandomChar() and Exists()in a loop 4 (Inner) loop for 4 characters in a group // note every 4 chars in a loop 5 Conditional loop until char is unique 6 Concatenating unique character to Group in a loop 7 Concatenate Group / random character to Password in a loop 8 (Attempt to) insert hyphens between groups (or removing later) and Return Password 9(b) FUNCTION AddPassword(Name, Password : STRING) 6 RETURNS BOOLEAN DECLARE Index : INTEGER DECLARE Added : BOOLEAN Added  FALSE Index  1 IF FindPassword(Name) = "" THEN // Domain name not in // array WHILE Added = FALSE AND Index <= 500 IF Secret[Index, 1] = "" THEN Secret[Index, 1]  Name Secret[Index, 2]  Encrypt(Password) Added  TRUE ELSE Index  Index + 1 ENDIF ENDWHILE ENDIF RETURN Added ENDFUNCTION Marks as follows: 1 Check that the website domain name isn't already in array using FindPassword() / linear search, otherwise: 2 (Conditional) loop while not added and not end of array 3 Check for unused element by testing value in column 1 in a loop 4 If unused, write parameter values to column 1 and 2 and set flag / variable 5 ...having used Encrypt() on the password 6 Return BOOLEAN value (correctly in all cases) 9(c) One mark per point to Max 3. 3 Solution based on field length:  Convert the length of the website domain name (either field) …  … to a string of fixed length  Form a string by concatenate this string with the other two (and write as one line of the file) Solution based on use of separator character:  Select a (separator) character that cannot occur in the domain name (e.g. space)  Create a string from the domain name followed by the separator  ...Concatenate the encrypted password (and write as one line of the file)

This question in 9618/23 May/June 2022

1 (a) An algorithm includes a number of complex calculations. A programmer is writing a program to implement the algorithm and decides to use library routines to provide part of the solution. State three possible benefits of using library routines in the development of the program. 1 … … 2 … … 3 … … [3] (b) The following pseudocode is part of a program that stores names and test marks for use in other parts of the program. DECLARE Name1, Name2, Name3 : STRING DECLARE Mark1, Mark2, Mark3 : INTEGER INPUT Name1 INPUT Mark1 INPUT Name2 INPUT Mark2 INPUT Name3 INPUT Mark3 (i) The pseudocode needs to be changed to allow for data to be stored for up to 30 students. Explain why it would be good practice to use arrays to store the data. … … … … … … [3] (ii) The following pseudocode statement includes array references: OUTPUT "Student ", Name[Count], " scored ", Mark[Count] State the purpose of the variable Count and give its data type. Purpose … … Data type … [2] (c) The pseudocode statements in the following table may contain errors. State the error in each case or write ‘NO ERROR’ if the statement contains no error. Assume that any variables used are of the correct type for the given function. Statement Error IF EMPTY "" THEN ← Status IS_NUM(-23.4) ← X STR_TO_NUM("37") + 5 ← Y STR_TO_NUM("37" + "5") ← [4]

12 marks

Mark scheme: Question Answer Marks 1(a) One mark per point: 3 1 They are tried and tested so free from errors 2 They perform a function that you may not be able to program yourself (for example encryption) 3 They are readily available / speed up development time 1(b)(i) One mark per point: 3 1 Algorithm to process / search / organise the data is easier to implement // Values may be accessed via a loop-controlled variable / iterated through using index 2 Makes the program easier to design / code / test / understand 3 Multiple instances referenced via a single identifier / so fewer identifiers needed // Easier to amend the program when the number of students increases 1(b)(ii) One mark per point: 2 Purpose: It identifies / references an individual array element // provides the index to the array Data type: Integer 1(c) One mark per row: 4 Statement Error IF EMPTY  "" THEN Should be "=" not  Status  IS_NUM(-23.4) Parameter should be a string (or char) // should not be a real X  STR_TO_NUM("37") + 5 NO ERROR Y  STR_TO_NUM("37" + "5") Wrong operator – should be & or Parameter is not a string

This question in 9618/21 Oct/Nov 2022

5 A program uses two 1D arrays of type integer. Array1 contains 600 elements and Array2 contains 200 elements. Array1 contains sample values read from a sensor. The sensor always takes three consecutive samples and all of these values are stored in Array1. A procedure Summarise() will calculate the average of three consecutive values from Array1 and write the result to Array2. This will be repeated for all values in Array1. The diagram below illustrates the process for the first six entries in Array1. Array1 Array2 Comment 10 15 average of first three values 20 41 average of next three values 15 } 40 41 42 } Write pseudocode for the procedure Summarise(). … … … … … … … … … … … … … … … … [5]

5 marks

Mark scheme: 5 Mark as follows (Max 5): 5 1 Procedure heading and ending and declaration of both indexes 2 Loop to process all elements from Array1 3 Sum (any) three consecutive values from Array1 and divide by 3 in a loop 4 Convert result to Integer 5 Assign value to correct element of Array2 in a loop 6 Increment Array2 index in a loop PROCEDURE Summarise() DECLARE Value : REAL DECLARE IxA, IxB : INTEGER // Index variables IxB  1 FOR IxA  1 TO 598 STEP 3 Value  Array1[IxA] + Array1[IxA + 1] + Array1[IxA + 2] Value  Value / 3 Array2[IxB]  INT(Value) IxB  IxB + 1 NEXT IxA ENDPROCEDURE

This question in 9618/21 Oct/Nov 2022

4 (a) A program contains a 1D array DataItem with 100 elements. State the one additional piece of information required before the array can be declared. … … [1] (b) A programmer decides to implement a queue Abstract Data Type (ADT) in order to store characters received from the keyboard. The queue will need to store at least 10 characters and will be implemented using an array. (i) Describe two operations that are typically required when implementing a queue. State the check that must be carried out before each operation can be completed. Operation 1 … … Check 1 … … Operation 2 … … Check 2 … … [4] (ii) Describe the declaration and initialisation of the variables and data structures used to implement the queue. … … … … … … … … … … … [5]

10 marks

Mark scheme: 4(a) The data type (of the item to be stored) 1 4(b)(i) Operation: Add an item / Enqueue 4 Check: There are unused elements in the array // The queue is not full Operation: Remove an item / Dequeue Check: There are items in the array // The queue is not empty One mark for reason and one mark for reason it could not be completed. 4(b)(ii) One mark per point (Max 5): 5 1 Declare a (1D) array of size >= 10 2 …of data type CHAR 3 Declare integer variable for FrontOfQueuePointer 4 Declare integer variable for EndOfQueuePointer 5 Initialise FrontOfQueuePointer and EndOfQueuePointer to represent an empty queue 6 Declare integer variable or NumberInQueue 7 Declare integer variable for SizeOfQueue to count / limit the max number of items allowed // Reference to mechanism for defining 'wrap' of circular queue 8 Initialise SizeOfQueue // Initialise NumberInQueue

This question in 9618/23 Oct/Nov 2022

6 A video-conferencing program supports up to six users. Speech from each user is sampled and digitised (converted from analogue to digital). Digitised values are stored in array Sample. The array Sample consists of 6 rows by 128 columns and is of type integer. Each row contains 128 digitised sound samples from one user. The digitised sound samples from each user are to be processed to produce a single value which will be stored in a 1D array Result of type integer. This process will be implemented by procedure Mix(). A procedure Mix() will: • calculate the average of each of the 6 sound samples in a column • ignore sound sample values of 10 or less • store the average value in the corresponding position in Result • repeat for each column in array Sample The diagram uses example values to illustrate the process: 1 2 3 ... 126 127 128 1 20 20 20 30 30 2 2 20 20 30 50 30 3 3 20 20 40 40 40 4 Sample: 4 20 20 50 40 50 20 5 20 3 5 6 60 4 6 20 4 2 4 70 30 Result: 20 20 35 40 46 25 Write pseudocode for procedure Mix(). Assume Sample and Result are global. … … … … … … … … … … … … … … … … … … … … … [6]

6 marks

Mark scheme: 6 PROCEDURE Mix() 6 DECLARE Count, Total ThisNum : INTEGER DECLARE ThisUser, ThisSample : INTEGER FOR ThisSample  1 TO 128 Count  0 Total  0 FOR ThisUser  1 TO 6 IF Sample[ThisUser, ThisSample] > 10 THEN Count  Count + 1 Total  Total + Sample[ThisUser, ThisSample] ENDIF NEXT ThisUser Result[ThisSample]  INT(Total / Count) NEXT ThisSample ENDPROCEDURE Mark as follows: 1 Declaration and initialisation before inner loop of Count and Total 2 Outer Loop for 128 iterations 3 Inner loop for six iterations 4 Test for sample > 10 in a loop 5 and if true sum Total and increment Count 6 Calculate average value and assign to Result array after inner loop and within outer loop 7 Use of INT()/ DIV to convert average to integer Max 6 Marks

This question in 9618/21 May/June 2023

2 A program stores a user’s date of birth using a variable MyDOB of type DATE. (a) Write a pseudocode statement, using a function from the insert, to assign the value corresponding to 17/11/2007 to MyDOB. … [1] (b) MyDOB has been assigned a valid value representing the user’s date of birth. Write a pseudocode statement to calculate the number of months from the month of the user’s birth until the end of the year and to assign this to the variable NumMonths. For example, if MyDOB contains a value representing 02/07/2008, the value 5 would be assigned to NumMonths. … [2] (c) The program will output the day of the week corresponding to MyDOB. For example, given the date 22/06/2023, the program will output "Thursday". An algorithm is required. An array will be used to store the names of the days of the week. Define the array and describe the algorithm in four steps. Do not use pseudocode statements in your answer. Array definition … … Step 1 … … … Step 2 … … … Step 3 … … … Step 4 … … … [6]

9 marks

Mark scheme: 2(a) MyDOB  SETDATE(17, 11, 2007) 1 2(b) NumMonths  12 - MONTH(MyDOB) 2 One mark per underlined part 2(c) 6 One mark per array definition bullet:  A (1D) array containing 7 elements  of type STRING One mark per Step: Step1: Assign value "Sunday" to first element, "Monday" to second element etc. Step2: Use the function DAYINDEX() to return / find the day number from MyDoB Step3: Use the returned value as the array index / to access the element that contains the name / string Step4: Output the element / name / string Note: Max 2 for Array definition, Max 4 for steps

This question in 9618/22 May/June 2023

1 The following pseudocode represents part of the algorithm for a program. Line numbers are for reference only. 10 DECLARE Sheet4 : ARRAY[1:2, 1:50] OF INTEGER … 100 FOR PCount 0 TO 49 101 Sheet4[1, PCount] 0 102 Sheet4[2, PCount] 47 103 NEXT PCount (a) The pseudocode contains references to an array. Complete the table by writing the answer for each row. Answer The dimension of the array The name of the variable used as an array index The number of elements in the array [3] (b) The pseudocode contains two errors. One error is that variable PCount has not been declared. Identify the other error and state the line number where it occurs. Error … … … Line number … [2] (c) The pseudocode does not include a declaration for PCount. State the data type that should be used in the declaration. … [1] (d) The pseudocode statements given in the following table are used in other parts of the algorithm. Complete the table by placing one or more ticks (✓) in each row. The first row has already been completed. Pseudocode statement Input Process Output INPUT MyChoice ✓ OUTPUT FirstName & LastName WRITEFILE YourFile, TextLine READFILE MyFile, TextLine Result SQRT(NextNum) [4]

10 marks

Mark scheme: Question Answer Marks 1(a) 3 Answer The dimension of the array 2 The name of the variable used as an array index PCount The number of elements in the array 100 1(b) One mark per point: 2  The (second dimension/index of the) array is declared from 1 to 50 but the loop runs from 0 to 49  Line number: 10 / 100 / 101 / 102 1(c) Integer 1 1(d) One mark for each of rows 2 - 5 4 Pseudocode statement Input Process Output INPUT MyChoice  OUTPUT FirstName & LastName   WRITEFILE OutputFile, TextLine  READFILE MyFile, TextLine  Result  SQRT(NextNum) 

This question in 9618/23 May/June 2023