2025 mock paper

Adjacent items are compared and swapped if they are in the wrong order. Multiple passes are made through the list. After each pass the largest value moves to the end. The process continues until a pass occurs with no swaps.

The algorithm can stop early if a pass is completed with no swaps. A flag can be used to detect whether any swaps have occurred. This reduces the number of passes required.

Insertion sort maintains a sorted and an unsorted section. Initially the sorted list is empty and the unsorted list is 20 8 15 36. 20 is inserted into the sorted list. 8 is inserted before 20. 15 is inserted between 8 and 20. 36 is inserted at the end. The final sorted list is 8 15 20 36.

The recursive function is quickSort(). The recursive calls occur on lines 21 and 22. The partition() function uses count-controlled iteration. The partition() function selects a pivot and rearranges values so smaller values are on one side and larger values are on the other. To sort into descending order the comparison is reversed so values greater than the pivot are placed first.

Divide and conquer is a problem-solving approach where a problem is broken into smaller subproblems, each subproblem is solved, and the solutions are combined to produce the final solution.

A linear search checks each item sequentially from the first to the last and does not require sorted data. Its worst and average time complexity is O(n), so the time increases in proportion to the number of items. A binary search requires the data to be sorted and repeatedly compares the target with the middle value, discarding half of the remaining items each time. Its worst and average time complexity is O(log n), so the time increases logarithmically with the number of items. Both have O(1) space complexity. For a file of 50 million sorted usernames binary search is more efficient because far fewer comparisons are required, so binary search should be used.

Data mining is the process of analysing large quantities of data to identify patterns and relationships. A company could analyse customer activity such as items viewed and purchased to identify patterns in behaviour. This could be used to make recommendations, personalise the website or improve product placement to improve the customer experience.

A stack is a LIFO data structure where items are added using push() and removed using pop(). Push() checks if the stack is full, increments the pointer and stores the value. Pop() checks if the stack is empty, returns the top value and decrements the pointer. The pointer indicates the position of the top element and changes as items are added or removed.

Pipelining divides instruction processing into stages such as fetch, decode and execute. Different instructions can be processed simultaneously at different stages, for example one instruction fetched while another is decoded and another executed. For the first four instructions instruction 1 is fetched first, then instruction 1 decoded and instruction 2 fetched, then instruction 1 executed while instruction 2 decoded and instruction 3 fetched, and so on. This increases throughput and allows many instructions to be processed efficiently. However efficiency depends on mostly sequential execution and may be reduced by jumps that require the pipeline to be reset. Overall pipelining is suitable because it allows millions of instructions to be processed efficiently.

The graph is a graphical representation that simplifies the problem. Nodes represent planets and edges represent routes between planets. The arrows show direction of travel and the edge values show costs, making the problem easier to understand.

Starting at A with distance 0, distances are updated to neighbouring nodes. The final shortest path is A → B → E → D → F → G → H with a total distance of 31. Distances are A=0, B=10 via A, C=15 via B, E=11 via B, D=16 via E, F=21 via D, G=28 via F, H=31 via G.

A heuristic is an estimated cost to the goal. The heuristic value is added to the current distance to decide the next node to explore. The algorithm focuses on promising routes and does not explore every possible route, making it faster.

Breakpoints allow the program to stop at set points to check variable values and flow. Stepping allows code to be executed one line at a time to check behaviour. A variable watch window allows variable values or data structures to be viewed during execution. Error diagnostics report and locate errors.

Global variables are accessible throughout the program and exist for the entire runtime. Local variables only exist within the scope in which they are declared such as a function or procedure.

Global variables use memory throughout the program execution and may waste memory.

Local variables only exist within the subroutine where they are declared so data must be passed as parameters and returned. This can make programming more complex and time consuming.

The function receives a copy of the variable. Changes are made to the copy and do not affect the original value. The copy is discarded when the function finishes.

Create a new linkedList object called createList. Insert nodes containing 10, 25 and 39 using insertNode(). Call outputList() for the object and output the returned values.

Start at the head pointer and compare the data with the value to remove. Move through the list node by node until the value is found or the end is reached. When the node is found the pointer of the previous node is set to point to the next node so the node is removed.

Any three of: problem decomposition, abstraction, backtracking, data mining, heuristics, performance modelling, pipelining or visualisation.

An object-oriented linked list uses dynamic memory and creates nodes when needed so the number of elements does not need to be known in advance and memory is used efficiently. The class can be reused in other programs with small changes. An array implementation uses static memory so the maximum size must be known in advance and memory may be wasted or run out. Arrays require extra management such as tracking free elements. Object-oriented lists are generally more reusable and flexible while arrays may be simpler but less efficient. Either approach can be justified depending on requirements.