←

Paper 1 (on-screen programming, practice version)

Preliminary material: Skeleton program 'Treasure Hunt' (Python, written for this paper)

The skeleton program below is a simple grid game. The player starts in the top-left cell and moves N, S, E or W. Three treasures (+10) and five traps (−5) are hidden. The game ends after 20 moves or when the player quits.
import random GRID_SIZE = 8MAX_MOVES = 20 class Cell:    def __init__(self):        self.Treasure = False        self.Trap = False        self.Visited = False class Board:    def __init__(self, Seed=None):        random.seed(Seed)        self.Cells = [[Cell() for Col in range(GRID_SIZE)] for Row in range(GRID_SIZE)]        self.__PlaceItems(3, "Treasure")        self.__PlaceItems(5, "Trap")     def __PlaceItems(self, Count, Kind):        Placed = 0        while Placed < Count:            Row = random.randint(0, GRID_SIZE - 1)            Col = random.randint(0, GRID_SIZE - 1)            C = self.Cells[Row][Col]            if not C.Treasure and not C.Trap and (Row, Col) != (0, 0):                if Kind == "Treasure":                    C.Treasure = True                else:                    C.Trap = True                Placed += 1     def Display(self, PlayerRow, PlayerCol):        for Row in range(GRID_SIZE):            Line = ""            for Col in range(GRID_SIZE):                if (Row, Col) == (PlayerRow, PlayerCol):                    Line += "P "                elif self.Cells[Row][Col].Visited:                    Line += ". "                else:                    Line += "# "            print(Line) class Game:    def __init__(self):        self.Board = Board()        self.Row = 0        self.Col = 0        self.Score = 0        self.MovesLeft = MAX_MOVES        self.Board.Cells[0][0].Visited = True     def Move(self, Direction):        NewRow, NewCol = self.Row, self.Col        if Direction == "N":            NewRow -= 1        elif Direction == "S":            NewRow += 1        elif Direction == "E":            NewCol += 1        elif Direction == "W":            NewCol -= 1        if 0 <= NewRow < GRID_SIZE and 0 <= NewCol < GRID_SIZE:            self.Row, self.Col = NewRow, NewCol            self.MovesLeft -= 1            self.__CheckCell()        else:            print("You cannot move off the board.")     def __CheckCell(self):        C = self.Board.Cells[self.Row][self.Col]        if C.Treasure and not C.Visited:            self.Score += 10            print("You found treasure! +10")        elif C.Trap:            self.Score -= 5            print("A trap! -5")        C.Visited = True     def Play(self):        while self.MovesLeft > 0:            self.Board.Display(self.Row, self.Col)            print("Score:", self.Score, " Moves left:", self.MovesLeft)            Direction = input("Move (N/S/E/W) or Q to quit: ").upper()            if Direction == "Q":                break            self.Move(Direction)        print("Game over. Final score:", self.Score) if __name__ == "__main__":    MyGame = Game()    MyGame.Play()
14 marks
Figure 1 is the state transition table for a finite state machine (FSM). S0 is the start state and the only accepting state.
Current stateInput 0Input 1
S0 (start, accepting)S0S1
S1S1S0
For each input string, state whether it is accepted: (a) 1101 (b) 1001 (c) 111 (d) 0000. Describe in one sentence the language the FSM accepts.
23 marks
For the regular expression a(b|c)*d, state which of these strings match: ad, abcbd, abd, acdd.
34 marks
State the time complexity in Big-O notation of a linear search, a binary search and a bubble sort, and explain why binary search is more efficient for large data sets.
45 marks
A circular queue has 5 positions (0–4). It is empty with Front = 0 and Rear = −1. The operations Enqueue(A), Enqueue(B), Enqueue(C), Dequeue, Dequeue, Enqueue(D), Enqueue(E), Enqueue(F) are carried out. State the contents of each position and the final values of Front and Rear.
56 marks
A weighted undirected graph has edges A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 3. Use Dijkstra's algorithm to find the shortest distance from A to every other node and the shortest path from A to F.
64 marks
FUNCTION F(N)    IF N <= 1 THEN        RETURN 1    ELSE        RETURN N + F(N - 2)    ENDIFENDFUNCTION
Trace the call F(7). State the value returned and explain what is meant by a base case.
73 marks
Convert (5 + 2) × (8 − 3) into Reverse Polish notation and evaluate it, explaining why RPN suits stack-based evaluation.
84 marks
Explain the meaning of encapsulation and inheritance, giving an example of each from a program that models vehicles.
94 marks
A hash table has 11 slots (0–10). The hash function is key MOD 11 and collisions are resolved by linear probing. Insert the keys 23, 47, 56 and 12 in that order and state the slot of each.
1013 marks
Write a program that asks the user for a positive whole number and outputs whether it is a perfect number (equal to the sum of its proper divisors, e.g. 6 = 1 + 2 + 3). The program must reject input that is not a positive integer and ask again. Show the output for 28 and 12.

Preliminary material: Skeleton program 'Treasure Hunt' (Python, written for this paper)

The skeleton program below is a simple grid game. The player starts in the top-left cell and moves N, S, E or W. Three treasures (+10) and five traps (−5) are hidden. The game ends after 20 moves or when the player quits.
import random GRID_SIZE = 8MAX_MOVES = 20 class Cell:    def __init__(self):        self.Treasure = False        self.Trap = False        self.Visited = False class Board:    def __init__(self, Seed=None):        random.seed(Seed)        self.Cells = [[Cell() for Col in range(GRID_SIZE)] for Row in range(GRID_SIZE)]        self.__PlaceItems(3, "Treasure")        self.__PlaceItems(5, "Trap")     def __PlaceItems(self, Count, Kind):        Placed = 0        while Placed < Count:            Row = random.randint(0, GRID_SIZE - 1)            Col = random.randint(0, GRID_SIZE - 1)            C = self.Cells[Row][Col]            if not C.Treasure and not C.Trap and (Row, Col) != (0, 0):                if Kind == "Treasure":                    C.Treasure = True                else:                    C.Trap = True                Placed += 1     def Display(self, PlayerRow, PlayerCol):        for Row in range(GRID_SIZE):            Line = ""            for Col in range(GRID_SIZE):                if (Row, Col) == (PlayerRow, PlayerCol):                    Line += "P "                elif self.Cells[Row][Col].Visited:                    Line += ". "                else:                    Line += "# "            print(Line) class Game:    def __init__(self):        self.Board = Board()        self.Row = 0        self.Col = 0        self.Score = 0        self.MovesLeft = MAX_MOVES        self.Board.Cells[0][0].Visited = True     def Move(self, Direction):        NewRow, NewCol = self.Row, self.Col        if Direction == "N":            NewRow -= 1        elif Direction == "S":            NewRow += 1        elif Direction == "E":            NewCol += 1        elif Direction == "W":            NewCol -= 1        if 0 <= NewRow < GRID_SIZE and 0 <= NewCol < GRID_SIZE:            self.Row, self.Col = NewRow, NewCol            self.MovesLeft -= 1            self.__CheckCell()        else:            print("You cannot move off the board.")     def __CheckCell(self):        C = self.Board.Cells[self.Row][self.Col]        if C.Treasure and not C.Visited:            self.Score += 10            print("You found treasure! +10")        elif C.Trap:            self.Score -= 5            print("A trap! -5")        C.Visited = True     def Play(self):        while self.MovesLeft > 0:            self.Board.Display(self.Row, self.Col)            print("Score:", self.Score, " Moves left:", self.MovesLeft)            Direction = input("Move (N/S/E/W) or Q to quit: ").upper()            if Direction == "Q":                break            self.Move(Direction)        print("Game over. Final score:", self.Score) if __name__ == "__main__":    MyGame = Game()    MyGame.Play()
111 mark
State the name of one private method in the skeleton program.
121 mark
State the type of relationship between the Game class and the Board class.
132 marks
Explain why __PlaceItems checks that (Row, Col) != (0, 0).
142 marks
Explain the purpose of random.seed(Seed) in the Board constructor and how it could help testing.
153 marks
A player standing on a trap types X. Explain what happens and why this is a problem.
162 marks
Identify the data structure used to store the cells and explain how a cell is accessed.
172 marks
Explain why a WHILE loop rather than a FOR loop is used in __PlaceItems.
182 marks
State the maximum score a player can achieve and explain why.
198 marks
Modify the skeleton program so that only N, S, E, W or Q are accepted. Any other input must display 'Invalid direction' and must not use up a move. Show the new code and test evidence of entering X followed by E.
2011 marks
Modify the skeleton program so that: a trap only takes points the first time it is visited; the player starts with 3 lives and loses one each time they find a new trap; the game ends when lives reach 0, displaying 'Out of lives'. Lives must be displayed with the score. Show your code and a test with a fixed seed.
2116 marks
Add a Scan command (key R) that costs 2 moves and reports how many treasures (not yet found) are in the up to 8 cells surrounding the player. Scan cannot be used if fewer than 2 moves remain. Write a new method in the Board class to count the treasures, and show test evidence including a scan from a corner cell.

Finished?

Answer every question to finish (21 left), or finish when the time’s up.

Score 0 / 100 · 0 of 21 marked

This paper is written by Plasmo in the style of the AQA A-Level Computer Science exam. It is not a past paper and is not produced or endorsed by the exam board.

AQA A-Level Computer Science Mock Exam: Paper 1 (on-screen programming, practice version) | Plasmo