←

Fundamentals of data structures

From Paper 1 (on-screen programming, practice version)
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.
From Paper 1 (on-screen programming, practice version)
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.

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()
From Paper 1 (on-screen programming, practice version)
162 marks
Identify the data structure used to store the cells and explain how a cell is accessed.
Score 0 / 11 · 0 of 3 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.

Fundamentals of data structures Exam Questions: AQA A-Level Computer Science | Plasmo