COMPUTER SCIENCE 9618
PSEUDO-CODE - LINEAR SEARCH
9618/21/O/N/24/Q8(a)
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:
(a) Write pseudocode for module CheckMark(). [6]
Steps:
FUNCTION CheckMark(Mark : INTEGER) RETURNS BOOLEAN
DECLARE Index, Lower, Upper : INTEGER
FOR Index ← 1 TO 5
Lower ← GradeBoundary[Index] - 2
Upper ← GradeBoundary[Index] + 2
IF Mark >= Lower AND Mark <= Upper THEN
RETURN TRUE
ENDIF
NEXT Index
RETURN FALSE
ENDFUNCTION
9618/22/O/N/24/Q8(a)
A program is being developed to implement a game for up to six players. During the game, each player assembles a team of characters. At the start of the game there are 45 characters available. Each character has four attributes, as follows:
The programmer has defined a record type to define each character. The record type definition is shown in pseudocode as follows:
The Player field indicates the player to which the character is assigned (1 to 6). The field value is 0 if the character is not assigned to any player. The programmer has defined a global array to store the character data as follows: DECLARE Character : ARRAY[1:45] OF CharacterType At the start of the game all record fields are initialised, and all Player field values are set to 0 The programmer has defined a program module as follows:
(a) Write pseudocode for module Assign(). [7]
Steps:
PROCEDURE Assign(ThisRole : STRING, ThisPlayer : INTEGER)
DECLARE Index : INTEGER
DECLARE Done : BOOLEAN
Done ← FALSE
Index ← 1
WHILE Index < 46 AND Done = FALSE
IF Character[Index].Player = 0 AND Character[Index].Role = ThisRole THEN
Character[Index].Player ← ThisPlayer
Done ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Done = TRUE THEN
OUTPUT Character[Index].Name, " the ", Character[Index].Role, " has been assigned to player ", ThisPlayer
ELSE
OUTPUT "No characters with this role are available"
ENDIF
ENDPROCEDURE
9618/23/O/N/24
A program is being developed to implement a game for up to six players. During the game, each player assembles a team of characters. At the start of the game there are 45 characters available. Each character has four attributes, as follows:
The programmer has defined a
record type to define each character. The record type definition is shown in
pseudocode as follows:
TYPE CharacterType
DECLARE Player : INTEGER
DECLARE Role : STRING
DECLARE Name : STRING
DECLARE SkillLevel : INTEGER
ENDTYPE
The Player field indicates the player to which the character is assigned (1 to 6). This field value is 0 if the character is not assigned to any player. The programmer has defined a global array to store the character data, as follows:
DECLARE Character : ARRAY[1:45] OF CharacterType
At the start of the game all record fields are initialised, and all Player fields are set to 0 The programmer has defined a program module as follows:
(a) Complete the pseudocode for module Count().
PROCEDURE Count(ThisPlayer : INTEGER, ThisRole : STRING) [7]
Steps:
PROCEDURE Count(ThisPlayer : INTEGER, ThisRole : STRING)
DECLARE Index, Num, Total : INTEGER
Num ← 0
Total ← 0
FOR Index ← 1 TO 45
IF Character[Index].Player = ThisPlayer AND Character[Index].Role = ThisRole THEN
Num ← Num + 1
Total ← Total + Character[Index].SkillLevel
ENDIF
NEXT Index
IF Num > 0 THEN
OUTPUT "Player ", ThisPlayer, " has ", Num, " characters with the role of ", ThisRole, " and the total skill level is ", Total
ELSE
OUTPUT "No characters with that role are assigned to this player"
ENDIF
ENDPROCEDURE
9618/21/M/J/23/Q8(b)
(b) A new module has been defined:
Write efficient pseudocode for module CheckNewItem(). [7]
Steps:
FUNCTION CheckNewItem(NewLine : STRING) RETURNS BOOLEAN
DECLARE NotFound : BOOLEAN
DECLARE NewItemNum, ThisItemNum, ThisLine : STRING
NotFound <- TRUE
ThisItemNum <- "0000"
OPENFILE "Stock.txt" FOR READ
NewItemNum <- LEFT(NewLine, 4)
WHILE NOT EOF("Stock.txt") AND NotFound = TRUE AND ThisItemNum < NewItemNum
READFILE("Stock.txt", ThisLine)
ThisItemNum <- LEFT(ThisLine, 4)
IF ThisItemNum = NewItemNum THEN
NotFound <- FALSE
ENDIF
ENDWHILE
CLOSEFILE "Stock.txt"
RETURN NotFound
END FUNCTION
9618/23/M/J/23/Q8(b)
(b) A new module is required:
Write pseudocode for module Report_1(). [6]
Steps:
PROCEDURE Report_1(Supp : STRING)
DECLARE Count : INTEGER
DECLARE ThisItemNum, ThisDesc, ThisLine, ThisCode : STRING
Count ← 0
OPENFILE "Stock.txt" FOR READ
OUTPUT "Report for Supplier: " & Supp
OUTPUT ""
OUTPUT "Item Description"
OUTPUT ""
WHILE NOT EOF("Stock.txt")
READFILE("Stock.txt", ThisLine)
ThisCode ← MID(ThisLine, 5, 3)
IF ThisCode = Supp THEN
ThisItemNum ← LEFT(ThisLine, 4)
ThisDesc ← RIGHT(ThisLine, LENGTH(ThisLine) - 7)
OUTPUT ThisItemNum & " " & ThisDesc
Count ← Count + 1
ENDIF
ENDWHILE
CLOSEFILE "Stock.txt"
OUTPUT ""
OUTPUT "Number of items listed: " & Count
ENDPROCEDURE
9618/21/O/N/23/Q4(a)
Q4) 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
(a) Write pseudocode for the function TooMany(). [6]
STEPS:
FUNCTION TooMany(Search : STRING, Max : INTEGER) RETURNS BOOLEAN
DECLARE Count, Index : INTEGER
Count ← 0
FOR Index ← 1 TO 150
IF Data[Index] = Search THEN
Count ← Count + 1
ENDIF
NEXT Index
IF Count > Max THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
9618/22/O/N/23/Q2(a)
Q2) An algorithm will:
1. input a sequence of integer values, one at a time
2. ignore all values until the value 27 is input, then sum the remaining values in the sequence.
3. stop summing values when the value 0 is input and then output the sum of the values.
(a) Draw a program flowchart to represent the algorithm. [5]
9618/22/O/N/23/Q8(a)
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: 
(a) Write pseudocode for module GetPort().
Assume DestinationID contains a valid three-digit string. [7]
Steps:
FUNCTION GetPort(ThisDest : STRING) RETURNS INTEGER
DECLARE Index, DNum, Port : INTEGER
DNum ← STR_TO_NUM(ThisDest)
Index ← 1
Port ← -1
REPEAT
IF RouteTable[Index, 1] <> -1 THEN
IF DNum >= RouteTable[Index, 1] AND DNum <= RouteTable[Index, 2] THEN
Port ← RouteTable[Index, 3]
ENDIF
ENDIF
Index ← Index + 1
UNTIL Index = 7 OR Port <> -1
RETURN Port
ENDFUNCTION
9618/23/O/N/23/Q2(a)
Q2) Data is a 1D array of integers, containing 30 elements. All element values are unique. (a) An algorithm will output the index of the element with the smallest value. Draw a program flowchart to represent the algorithm. [5]
9618/21/M/J/22/Q8(b)
(b) A new module is defined as follows:
Write pseudocode for module FindPassword().
Assume that modules Encrypt() and Decrypt() have already been written. [7]
Steps:
FUNCTION FindPassword(Name : STRING) RETURNS STRING
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
9618/22/M/J/22/Q8(a)
Q8) 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 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:
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.
The programmer has started to define program modules as follows:
Note: in a case-sensitive comparison, 'a' is not the same as 'A'.
(a) Write pseudocode for the module Exists(). [5]
Steps:
FUNCTION Exists(ThisString : STRING, Search : CHAR) RETURNS BOOLEAN
DECLARE Found : BOOLEAN
DECLARE Index : INTEGER
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= LENGTH(ThisString)
IF MID(ThisString, Index, 1) = Search THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
RETURN Found
ENDFUNCTION
9618/22/M/J/22/Q8(b)
(b) A new module SearchDuplicates() will:
• search for the first password that occurs more than once in the array and output a message each time a duplicate is found.
For example, if the same password was used for the three websites ThisWebsite.com, website27.net and websiteZ99.org, then the following messages will be output:
"Password for ThisWebsite.com also used for website27.net"
"Password for ThisWebsite.com also used for websiteZ99.org"
• end once all messages have been output.
The module will output a message if no duplicates are found.
For example: "No duplicate passwords found"
Write efficient pseudocode for the module SearchDuplicates(). Encrypt() and Decrypt() functions have been written. [8]
Note: It is necessary to decrypt each password before checking its value.
Steps:
PROCEDURE SearchDuplicates()
DECLARE IndexA, IndexB : INTEGER
DECLARE ThisPassword, ThisValue : STRING
DECLARE Duplicates : BOOLEAN
Duplicates ← FALSE
IndexA ← 1
WHILE Duplicates = FALSE AND IndexA < 500
ThisValue ← Secret[IndexA, 2]
IF ThisValue <> "" THEN
ThisPassword ← Decrypt(ThisValue)
FOR IndexB ← IndexA + 1 TO 500
IF Secret[IndexB, 2] <> "" THEN
IF Decrypt(Secret[IndexB, 2]) = ThisPassword THEN
OUTPUT "Password for " & Secret[IndexA, 1] &" also used for " & Secret[IndexB, 1]
Duplicates ← TRUE
ENDIF
ENDIF
NEXT IndexB
ENDIF
IndexA ← IndexA + 1
ENDWHILE
IF Duplicates = FALSE THEN
OUTPUT "No duplicate passwords found"
ENDIF
ENDPROCEDURE
9618/23/M/J/22/Q5(c)
Q5) 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:
(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(). [4]
Assume that the Staff array is global.
Steps:
PROCEDURE Absentees()
DECLARE Index : INTEGER
FOR Index ← 1 TO 500
IF Staff[Index].EmployeeNumber <> -1 THEN
IF Staff[Index].Attendance <= 90 THEN
OUTPUT Staff[Index].EmployeeNumber
OUTPUT Staff[Index].Name
ENDIF
ENDIF
NEXT Index
ENDPROCEDURE
9618/23/M/J/22/Q9(b)
(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:
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:
The first three modules have been written.
Write pseudocode for the module AddPassword(). [6]
Steps:
FUNCTION AddPassword(Name, Password : STRING) 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
9618/21/O/N/22/Q3
Q3) A 1D array Data of type integer contains 200 elements. Each element has a unique value.
An algorithm is required to search for the largest value and output it.
Describe the steps that the algorithm should perform.
Do not include pseudocode statements in your answer. [5]
9618/22/O/N/22/Q7(a)
Q7) A teacher is designing a program to perform simple syntax checks on programs written by students.
Two global 1D arrays are used to store the syntax error data. Both arrays contain 500 elements.
• Array ErrCode contains integer values that represent an error number in the range 1 to 800.
• Array ErrText contains string values that represent an error description.
The following diagram shows an example of the arrays.
Note:
• There may be less than 500 error numbers so corresponding elements in both arrays may be unused. Unused elements in ErrCode have the value 999. The value of unused elements in ErrText is undefined.
• Values in the ErrCode array are stored in ascending order but not all values may be present, for example, there may be no error code 31.
The teacher has defined two program modules as follows:
(a) Write efficient pseudocode for module OutputError(). [6]
Steps:
PROCEDURE OutputError(LineNum, ErrNum : INTEGER)
DECLARE Index : INTEGER
Index <-- 0
// Search until ErrNum found OR not present OR end of array
REPEAT
Index <-- Index + 1
UNTIL ErrCode[Index] >= ErrNum OR Index = 500
IF ErrCode[Index] = ErrNum THEN
OUTPUT ErrText[Index], " on line ", LineNum // Found
ELSE
OUTPUT "Unknown error on line ", LineNum // Not found
ENDIF
ENDPROCEDURE
9618/23/O/N/22/Q7(a)
Q7) A teacher is designing a program to perform simple syntax checks on programs written by students.
Two global 1D arrays are used to store the syntax error data. Both arrays contain 500 elements.
• Array ErrCode contains integer values that represent an error number in the range 1 to 800.
• Array ErrText contains string values that represent an error description.
The following diagram shows an example of the arrays.
Note:
• There are less than 500 error codes so corresponding elements in both arrays may be unused. Unused elements in ErrCode have the value 999. These will occur at the end of the array. The value of unused elements in ErrText is undefined.
• Values in the ErrCode array are stored in ascending order but not all values may be present. For example, there may be no error code 31.
• Some error numbers are undefined. In these instances, the ErrCode array will contain a valid error number but the corresponding ErrText element will contain an empty string.
The teacher has defined one program module as follows:
(a) Write pseudocode for module OutputRange(). Assume that the two numbers input represent a valid error number range. [8]
9618/21/M/J/21/Q2(c)
(c) A program will:
• input 50 unique integer values
• output the largest value
• output the average of the values excluding the largest value.
Draw a program flowchart to represent the algorithm.
Variable declarations are not required.
It is not necessary to check that each input value is unique.
< ON THE NEXT PAGE >
9618/21/M/J/21/Q7(a)
Q7) 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:
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:
(a) Write pseudocode for the module GetStart(). [7]
Steps:
9618/21/M/J/21/Q7(b)
(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:
Write a detailed description of the algorithm for AddWord(). Do not include pseudocode statements in your answer. [4]
9618/21/M/J/21/Q7(c)
(c) As a reminder, the module description of GetWord() is repeated:
Write pseudocode for the module GetWord(). [5]
Steps:
9618/22/M/J/21/Q8(a)
Q8) A program is needed to take a string containing a full name and to 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 new string must be upper case.
For example:
The programmer has decided to use the following global variables:
• a ten element 1D array IgnoreList of type STRING to store the ignored words
• a string FNString to store the full name string
Assume that:
• each alphabetic character in the full name string may be either upper or lower case
• the full name string contains at least one word.
The programmer has started to define program modules as follows:
(a) Write pseudocode for the module IgnoreWord(). [5]
Steps:
9618/21/O/N/21/Q6(b)
(b) The module description of SearchInRow() is provided here for reference.
Write pseudocode to implement the module SearchInRow(). [8]
Steps:
9618/21/O/N/21/Q6(c)
(c) The following new module is introduced:
Write pseudocode to implement the module GetCentreCol(). [6]
Steps:
9618/22/O/N/21/Q3(b)
(b) A procedure GetIDs() will:
• prompt and input the number of a club
• output the StudentID of all the students who are members of that club
• output a count of all students in the given club.
Write pseudocode for the procedure GetIDs(). [7]
Steps:
9618/22/O/N/21/Q6(a)
Q6) A mobile phone has a touchscreen. The screen is represented by a grid, divided into 800 rows and 1280 columns.
The grid is represented by a 2D array Screen of type INTEGER. An array element will be set to 0 unless the user touches that part of the screen.
Many array elements will set to 1 by a single touch of a finger or a stylus.
The following diagram shows a simplified touchscreen. The dark line represents a touch on the screen. All grid elements that are wholly or partly inside the outline will be set to 1. These elements are shaded.
The element shaded in black represents the centre point of the touch.
A program is needed to find the coordinates (the row and column) of the centre point. The centre point on the diagram shown is row 6, column 11.
Assume:
• the user may only touch one area at a time
• screen rotation does not affect the touchscreen.
The programmer has decided to use global values CentreRow and CentreCol as coordinate values for the centre point.
The programmer has started to define program modules as follows:
(a) Write efficient pseudocode for the module FirstRowSet(). [7]
Steps:
9618/22/O/N/21/Q6(b)
(b) Describe a feature of your solution to part (a) that indicates the pseudocode represents an efficient algorithm. [2]
9618/22/O/N/21/Q6(d)
(d) An additional module GetCentre() is defined as follows:
Write pseudocode for the module GetCentre(). [6]
Steps:
9618/23/O/N/21/Q2(a)
Q2a) An algorithm to sort a 1D array into ascending order is described as follows:
• move the largest value to the end
• keep repeating until the array is sorted.
Apply the process of stepwise refinement to this algorithm in order to produce a more detailed description.
Write the more detailed description using structured English. Your explanation of the algorithm should not include pseudocode statements.
9618/23/O/N/21/Q6(b)
(b) The module description of SearchInRow() is provided here for reference.
Write pseudocode to implement the module SearchInRow(). [8]
Steps:
0 Reviews