Computational Thinking and Data Structures: Computer Science 9618 (Cambridge International AS & A Level)

A newly hired programmer at a small gym is asked to design a membership management system. Before writing any code, she splits the overall problem into four separate pieces: a module to register new members, a module to record a member's check-in at the front desk, a module to process a member's monthly payment, and a module to generate a usage report for the gym's owner.

Which computational thinking technique is illustrated by this splitting of the problem into four pieces?

A small music club stores basic information about each upcoming event using a single record for each event: the event's name, its ticket price, and whether a particular member is currently marked as attending.

(a) Write Cambridge pseudocode to define a user-defined data type called EventRecord, with three fields: EventName (a string), TicketPrice (a real number) and Attending (a boolean value). [3]

(b) Write pseudocode to declare a variable called NextEvent of type EventRecord, and then write pseudocode statements that store the following values in its three fields: EventName is "Chess Club Finals", TicketPrice is 2.50, and Attending is TRUE. [2]

(c) Write a single pseudocode statement that would output the value stored in the TicketPrice field of NextEvent, and state the value that this statement would output for the data given in part (b). [1]

A furniture store calculates a delivery charge for each order based on its weight, then adds up the charges for all of that day's orders. The task is described using this structured English description:

1. Set TotalCharge to 0.
2. Input the number of orders placed today, NumOrders.
3. Repeat the following steps NumOrders times: a. Input the weight, in kg, of the next order, OrderWeight. b. If OrderWeight is greater than 50, set Charge to 45.00. c. Otherwise, if OrderWeight is greater than 20, set Charge to 25.00. d. Otherwise, set Charge to 10.00. e. Add Charge to TotalCharge.
4. Output TotalCharge.

(a) Complete an identifier table for this algorithm, giving a suitable Cambridge pseudocode data type for each of the four identifiers NumOrders, OrderWeight, Charge and TotalCharge. [2]

(b) Write Cambridge pseudocode for the complete algorithm described above, using a count-controlled loop and selection statement(s) as needed. [5]

(c) Step 3 of the structured English description is an example of one of the three basic constructs used in pseudocode: sequence, selection or iteration. State which construct this is, and justify your answer. [1]

A web browser needs to store the addresses of the pages a user has visited, so that clicking a "Back" button always returns to the most recently visited page first, then to the page visited before that, and so on.

(a) State which abstract data type, a stack or a queue, should be used to store the page addresses so that the browser's "Back" button behaves as described above, and justify your answer by referring to the order in which addresses are added and removed. [2]

(b) The browser implements this abstract data type, named PageStack, using a 1D array of up to 4 elements, DECLARE PageStack : ARRAY[1:4] OF STRING, together with an integer pointer variable Top that stores the array index of the item most recently added (Top = 0 means PageStack is currently empty). Starting from an empty PageStack, the following page visits and Back-button presses occur, in order:

• Visit "Home" (PUSH)
• Visit "News" (PUSH)
• Visit "Sport" (PUSH)
• Press Back (POP)
• Visit "Weather" (PUSH)
• Press Back (POP)

Complete a trace table showing the value of Top and the contents of PageStack after each of these six operations. [4]

(c) State which page address would be returned to if the user presses Back one more time, immediately after the six operations above. [1]

(d) Describe, with reference to the pointer variable Top, how the PUSH and POP operations keep PageStack behaving as a stack rather than as a queue. [1]

(a) A small warehouse records which slots on its storage shelving are currently occupied using a 2D array declared in pseudocode as DECLARE Shelves : ARRAY[1:8, 1:12] OF BOOLEAN, where TRUE means that slot is occupied. State the upper bound of the first index, the upper bound of the second index, and the total number of storage slots represented by this array. [3]

(b) A charity records six donation amounts, in whole pounds, received during one collection, in the array DECLARE Donations : ARRAY[1:6] OF INTEGER, containing the values 15, 42, 8, 61, 8, 27 at indices 1 to 6 respectively. A linear search is used to find the index of the first donation of exactly £8. Complete a full trace table showing each comparison made by the linear search until the target is found, and state the index at which it is found. [3]

(c) A separate array of five exam scores is declared as DECLARE Scores : ARRAY[1:5] OF INTEGER, containing the values 29, 12, 47, 8, 33 at indices 1 to 5 respectively. A bubble sort is used to sort Scores into ascending order. Complete a full trace table showing the contents of Scores after each pass of the bubble sort, including a final pass that confirms the array is sorted, and state the fully sorted array. [4]

A trainee programmer is drawing a flowchart, using the standard flowchart symbols, for an algorithm that reads a student's percentage score from the keyboard and then displays "Pass" if the score is 60 or more, or "Fail" otherwise.

The flowchart needs one box that tests whether the score is 60 or more, so that the flow of control can branch to one of two different paths depending on the result of that test.

Which flowchart symbol shape should be used for this box?

A school library records the titles of books that are currently overdue in a text file called "Overdue.txt", which already contains one book title per line. Assume the variable BookTitle has already been assigned the title of a newly identified overdue book, as a string.

(a) Write Cambridge pseudocode to open "Overdue.txt" so that a new line can be added to the end of the file without erasing any of the lines already stored in it, write the value of BookTitle to a new line in the file, and then close the file. [3]

(b) Write Cambridge pseudocode, using a WHILE loop and the EOF function, to open "Overdue.txt" for reading, read every line from the file in turn, count how many lines (book titles) the file contains, output this count once every line has been read, and then close the file. [5]

(c) State one reason why a program should close a text file once it has finished reading from or writing to it. [1]

A university's network print server must process print jobs from students in the exact order they are submitted: the job submitted first must always be printed first.

(a) State which abstract data type, a stack or a queue, should be used to store the waiting print jobs so that they are processed in the order described above, and justify your answer by referring to the order in which jobs are added and removed. [2]

(b) The print server implements this abstract data type, named PrintQueue, using a 1D array of up to 5 elements, DECLARE PrintQueue : ARRAY[1:5] OF STRING, together with two integer pointer variables: Front (the array index of the job at the front of the queue, next to be printed) and Rear (the array index of the job most recently added). Both Front and Rear start at 0, meaning PrintQueue is empty. Starting from this empty state, the following operations occur, in order:

• ENQUEUE "Report1"
• ENQUEUE "Report2"
• ENQUEUE "Report3"
• DEQUEUE
• ENQUEUE "Report4"
• DEQUEUE

Complete a trace table showing the value of Front, the value of Rear, and the contents of PrintQueue after each of these six operations. [5]

(c) State which print job would be produced if DEQUEUE were called one more time, immediately after the six operations above. [1]

(d) Front and Rear in this implementation only ever increase, they never wrap back around to the start of the array. State one limitation this causes, illustrating your answer with a specific example based on the array PrintQueue. [2]

A tutor keeps a simple linked list of the students in a small tutor group who have arrived so far today, kept in alphabetical order by name. The linked list is implemented using two parallel 1D arrays, DECLARE StudentName : ARRAY[1:5] OF STRING and DECLARE NextPointer : ARRAY[1:5] OF INTEGER, together with an integer variable StartPointer holding the array index of the first student in the list. A NextPointer value of 0 means "end of list" (there is no next student).

Currently, the arrays hold:

and StartPointer = 3.

(a) State the logical order of the three students currently in the linked list, and explain how StartPointer and the NextPointer array are used to work this out. [3]

(b) A new student, "Ben", arrives and must be inserted into the linked list in his correct alphabetical position, without moving any of the data already stored at indices 1, 2 or 3. State the array index at which "Ben" should be stored, and give the new value of every NextPointer element (and of StartPointer, if it needs to change) that must be updated to correctly insert "Ben" into the list at that position. [4]

(c) Explain one advantage of implementing this linked list using two parallel arrays and pointers, rather than storing the student names in a single 1D array that is always kept in continuous alphabetical order, when a new name needs to be inserted into the middle of the list. [2]

A city bike-rental app needs a way to help a user find the nearest bike station that currently has at least one bike available. In the real world, each physical bike station has many attributes, including: its GPS coordinates (latitude and longitude), the number of bikes currently available at it, its total docking capacity, the date it was installed, the name of the company that maintains it, and the colour of its signage.

(a) State the computational thinking technique used when a systems designer builds a simplified model of a bike station for this "find the nearest station with an available bike" feature, keeping only the details relevant to that specific feature and leaving out the rest. [1]

(b) State which two of the six attributes listed above should be kept in this simplified model for the "find the nearest station with an available bike" feature, and explain why the other four attributes can safely be left out of this particular model. [4]

(c) Explain, in general terms, why using this technique, rather than including every real-world attribute of a bike station in the app's model, is beneficial for a system like this one. [2]