2023 NJC P2 Question Paper

NATIONAL JUNIOR COLLEGE Mathematics Department General Certificate of Education Advanced Level Higher 2 COMPUTING Paper 2 (Lab-based) 9569/2 15 Aug 2023 3 hours Additional Materials: Electronic version of ARRIVALS.TXT data file Electronic version of WORDS.TXT data file Electronic version of TASK4.db Electronic version of ADDITIONS.CSV Insert Quick Reference Guide READ THESE INSTRUCTIONS FIRST Answer all questions. All tasks must be done in the computer laboratory. You are not allowed to bring in or take out any pieces of work or materials on paper or electronic media or in any other form Approved calculators are allowed. Save each task as it is completed. The use of built-in functions, where appropriate, is allowed for this paper unless stated otherwise. Note that up to 5 marks out of 100 will be awarded for the use of common coding standards for programming style. The number of marks is given in the brackets [ ] at the end of each question or part question. The total number of marks for this paper is 100. This document consists of 12 printed pages and 4 blank pages. NJC Mathematics 2023 [Turn over

2 NJC Mathematics 2023 [Turn over Instructions to candidates: Copy the folder from the thumb drive to the PC's desktop and rename the folder on the desktop to <your name>.(For example, TanKengHan). All the resource files are found in the folder and you should work on the folder in the desktop. Your program code and output for each of Task 1 to 3 should be saved in a single .ipynb file. For example, your program code and output for Task 1 should be saved as Task_1_<your name>.ipynb. You should have a total of three .ipynb files to submit at the end of the paper. At the end of the exam, copy the working folder on your desktop to the thumb drive. 1 Name your Jupyter Notebook as Task1_<your name>.ipynb. This task uses an Object Oriented Programming (OOP) and layered approach to implement linked list, stack and queue data structures. Each data structure will be implemented by using the abstractions (attributes and operations) provided by a previously implemented data structure. For each sub-task, add a comment statement, at the beginning of the code using the hash symbol "#", to indicate the sub-task the program code belongs to, for example: In [1]: #Task 1.1 Program code Output: Task 1.1 A linked list is a dynamic data structure where the storage for new data is allocated on demand and the data items are accessed by using pointers to traverse the linked list. Implement a linked list class and a node class, using Python code. The node class will be used to encapsulate and store the data item and will have the following attributes: • data, stores the data item. • next, points to the next node in the linked list. The linked list class will have the following attributes a nd operations: • start , this attribute points to the first node in the linked list. A None value indicates an empty linked list • is_empty(),returns True if the linked list is empty and False otherwise.

3 NJC Mathematics 2023 [Turn over • insert_front(), inserts a data item at the front of the linked list, so that it is accessible by the start attribute. • remove_front(), removes and returns the first item from the linked list. • __repr__(), returns a string representation of the linked list as follows: o [ <item>, <item>,… ], where <item> is the data item in the linked list starting from the first item pointed by the start attribute. [8] Task 1.2 A stack is a data structure with the following attribute and operations: • top, pointer that points to a linked list data structure. • push(item: object) , inserts an item into the top of the stack. • pop(): object , returns and removes the item at the top of the stack. If the stack is empty None is returned. • peek(): object, returns the item at the top of the stack without removing it. If the stack is empty None is returned. • constructor(), creates and initialises attributes used by the stack object. • is_empty(), returns True if stack is empty, else returns False. Implement the stack class by using the linked list implemented in Task 1.1. [4] Task 1.3 Write test cases to test the stack implementation in Task 1.2. [1]

4 NJC Mathematics 2023 [Turn over Task 1.4 A queue is a data structure with the following operations: • enqueue(item: object) , inserts an item into the queue . • dequeue(): object , returns the first item inserted into the queue. If the queue is empty None is returned. • constructor(n:integer), creates the queue object. Implement the queue class by using ONLY the stack data structure implemented in Task 1.2 and you are allowed to use only the operations and attributes provided by the stack data structure. You may need to include additional attributes and operations. [6] Task 1.5 Write test cases to test the queue implementation in Task 1.4. [1] Task 1.6 A new data structure named MaxQueue is to be implemented by inheriting from the queue class implemented in Task 1.4. The MaxQueue has a new operation peek_max() which will return the data item that has the highest value among all the data items currently in the queue. You can assume that t he data item's value can be compare using the default < and > operators. [10] Save your Jupyter Notebook for Task 1.

5 NJC Mathematics 2023 [Turn over 2 Name your Jupyter Notebook as Task2_<your name>.ipynb. The journeys taken by two buses were recorded in the file ARRIVALS.TXT and depicted in the diagram below: The first bus started its journey from bus interchange A and ended its journey at bus interchange B. The second bus started its journey from bus interchange B and ended its journey at bus interchange A. The numbers, 1,2,3, ... N in the diagram represents the sequence of stops made by each bus in Direction 1 and 2. The data in the file has the following fields, StopSequence, Direction, BusStopCode, Distance, ArrivalTime described below: Each bus stop (including the bus interchanges) has a unique bus stop code, BusStopCode. The sequence of the bus stops visited by each bus is recorded as a StopSequence number for each Direction. The ArrivalTime is recorded in 24-hour format and the Distance is the cumulative distance travelled by the bus in km. You can assume that the two routes taken by the buses in Direction 1 and Direction 2 are on the same straight line and have the same distance. The outputs shown may not be the correct results. In [1]: #Task 2.1 Program code Output: Task 2.1 Write Python code to determine the bus stop code of the two interchanges A and B where the two buses start and end their journeys . The bus interchanges have the same bus stop codes in both directions. Print the two bus stop codes. [3] B A 1 N 2 3 1 N 2 3 Direction 1 Direction 2

6 NJC Mathematics 2023 [Turn over Task 2.2 Write Python code to determine the start time, end time and total time it takes for the two buses to travel in Direction 1 and Direction 2 respectively. The output should look like this: Direction Start End Total 1 0500 0627 1H,27m 2 0600 0730 1H,30m [5] Task 2.3 For both directions, write Python code to determine all the adjacent bus stops that the buses took more than two minutes to travel between them. Print the bus stop codes of the adjacent bus stops and the time taken in minutes.The output should look like this: Direction 1 76069 to 96289: 4m 80219 to 80169: 3m 02119 to 03019: 3m 03217 to 05649: 3m Direction 2 14089 to 14069: 3m 80161 to 80211: 4m 96281 to 76061: 4m [4] Task 2.4 For both directions, write Python code to determ