Data Types, Data Structures and Boolean Algebra - Worksheets, Questions and Revision
11 original exam-style questions - 9 pages of questions with a full mark scheme - free printable PDF.
Data Types, Data Structures and Boolean Algebra revision guideWrite-in editionMore A Level Computer Science practiceMock exams
This topic is chapter 4 of A Level Computer Science Topic Workbook 1 and chapter 4 of A Level Computer Science 10-Minute Tests.
1.4 Data Types, Data Structures and Boolean Algebra
TYPE StudentRecord
DECLARE studentID : INTEGER
DECLARE name : STRING
DECLARE grade : CHARDECLARE student1 : StudentRecord student1.studentID <- 10234 student1.name <- "Amara Okafor" student1.grade <- 'B'
DECLARE stack : ARRAY[0:9] OF INTEGER
DECLARE top : INTEGER
top <- -1
PROCEDURE Push(value : INTEGER)
top <- top + 1
stack[top] <- value
ENDPROCEDURE
FUNCTION Pop() RETURNS INTEGER
DECLARE value : INTEGER
value <- stack[top]
top <- top - 1
RETURN value
ENDFUNCTIONEnqueue(value): queue[rear] <- value, then rear <- (rear+1) MOD 5
Dequeue(): value <- queue[front], then front <- (front+1) MOD 5, RETURN value
Discuss which data structure(s) would be most appropriate for (1) the print queue and (2) the spell-checker's word list, justifying your choice by comparing at least two suitable data structures for each scenario in terms of how their operations are performed and how efficient they are.
Question 1
- (a) UnicodeB1
- (a) Answer: Unicode
- (b) 72 caoB1
- (b) Answer: 72
- (c) Unicode includes code points for accented characters and non-Latin scripts, whereas standard 7-bit ASCII only encodes basic Latin letters, digits and symbolsB1
- (c) so names can be stored and displayed accurately rather than being corrupted or losing informationB1
- (c) Answer: Unicode covers accented and non-Latin characters that ASCII cannot represent, so names are stored and displayed correctly.
- (d) 27=128 (insufficient, since 128<200) and 28=256 (sufficient, since 256≥200) testedM1
- (d) 8 bits caoA1
- (d) Answer: 8 bits
Question 2
- (a) A=0,B=0 rows (C=0 then C=1) correctly give Q=1, Q=0B1
- (a) A=0,B=1 rows (C=0 then C=1) correctly give Q=1, Q=0B1
- (a) A=1,B=0 rows (C=0 then C=1) correctly give Q=1, Q=0B1
- (a) A=1,B=1 rows (C=0 then C=1) correctly give Q=1, Q=1B1
- (a) Answer: Q values (A,B,C from 000 to 111): 1, 0, 1, 0, 1, 0, 1, 1
- (b) 2n rowsB1
- (b) because each of the n variables can independently take one of 2 values (0 or 1), giving 2 x 2 x ... (n times) = 2n possible combinationsB1
- (b) Answer: 2n rows, since each of the n inputs can independently be 0 or 1.
- (c) an AND gate with inputs A and B, and a NOT gate with input CB1
- (c) the outputs of the AND gate and the NOT gate are connected as the two inputs to an OR gate, whose output is QB1
- (c) Answer: AND gate (inputs A, B) and NOT gate (input C) feed into an OR gate, whose output is Q.
- (d) XOR (exclusive OR)B1
- (d) Answer: XOR
Question 3
- (a) 45 correctly represented in binary (00101101) and correctly inverted (11010010)M1
- (a) 11010011 cao (invert then add 1)A1
- (a) Answer: 11010011
- (b) 01001101 caoB1
- (b) Answer: 01001101
- (c) correct bit-by-bit binary addition attempted with carries shownM1
- (c) final carry out of the 8th bit correctly discardedM1
- (c) 00100000 cao (= 32, since -45 + 77 = 32)A1
- (c) Answer: 00100000 (= 32)
- (d) 10000000 statedB1
- (d) explanation that both operands are positive (sign bit 0) but the result has sign bit 1 (negative), which is impossible when adding two positive numbers, so overflow has occurredB1
- (d) Answer: 10000000 (overflow, since 127+1=128 cannot be represented as a positive 8-bit two's complement number)
Question 4
- (a) a recordB1
- (a) Answer: A record.
- (b) "Amara Okafor" caoB1
- (b) Answer: Amara Okafor
- (c) array declared with correct bounds for 30 elements of type StudentRecord, e.g. DECLARE cohort : ARRAY[0:29] OF StudentRecordM1
- (c) correct index used for the 5th element (index 4, since arrays are zero-indexed)M1
- (c) correct dot notation used to access and assign the field, e.g. cohort[4].grade <- 'A' (any correct logic, ignore minor syntax)A1
- (c) Answer:
DECLARE cohort : ARRAY[0:29] OF StudentRecord cohort[4].grade <- 'A'
- (d) all the data relating to one student is kept together under one index, so there is no risk of the arrays becoming out of step (e.g. after sorting or deleting an entry)B1
- (d) makes the code easier to read and maintain, since related fields are accessed via one structure (e.g. cohort[i].grade) rather than needing to keep several array indices synchronisedB1
- (d) Answer: Keeps each student's data together under one index, avoiding the arrays becoming mismatched, and makes the code clearer to maintain.
Question 5
- (a) a hash table is a data structure that stores key-value data in an array-like structure, using a function to determine where a given key's data should be storedB1
- (a) the hash function takes a key as input and returns an index (address) within the table, so the same key always maps to the same indexB1
- (a) this allows data to be stored and retrieved directly, typically in constant / O(1) average time, without searching through the whole structureB1
- (a) Answer: A hash table stores data using a hash function that maps each key to an index in the table, allowing fast (average O(1)) storage and retrieval.
- (b) correct MOD 7 calculation shown or implied for at least 3 of the 5 keysM1
- (b) all 5 indices correct: 15->1, 22->1, 9->2, 30->2, 16->2A1
- (b) collisions correctly identified: 22 collides with 15 (both index 1); 30 and 16 each collide, since index 2 is already used by 9 (and then 30)A1
- (b) Answer: 15->1, 22->1, 9->2, 30->2, 16->2. Collisions: 22 (with 15); 30 (with 9); 16 (with 9 and 30).
- (c) 15 placed at slot 1 (home slot, no collision)M1
- (c) 22 probes from slot 1 (occupied) to slot 2 (empty), placed at slot 2; 9 then probes from slot 2 (occupied) to slot 3 (empty), placed at slot 3M1
- (c) 30 probes slots 2 and 3 (occupied) to slot 4 (empty), placed at slot 4; 16 probes slots 2, 3 and 4 (occupied) to slot 5 (empty), placed at slot 5M1
- (c) final table fully correct: slot0=empty, 1=15, 2=22, 3=9, 4=30, 5=16, 6=emptyA1
- (c) Answer: Slot0: empty, Slot1: 15, Slot2: 22, Slot3: 9, Slot4: 30, Slot5: 16, Slot6: empty.
- (d) keys that collide tend to cluster together in consecutive slots (primary clustering)B1
- (d) this means later insertions and searches may need to probe through many occupied slots before finding an empty slot or the target key, increasing average access time towards O(n)B1
- (d) Answer: Linear probing causes clustering of colliding keys in consecutive slots, so as the table fills, insertions and searches must probe through more slots, increasing average access time.
Question 6
- (a) 22 written in binary (10110) and expressed as a normalised fraction, e.g. 0.10110 x 25M1
- (a) exponent 5 correctly converted to 4-bit two's complement (0101)M1
- (a) mantissa 01011000 and exponent 0101 both correct (oe equivalent padding)A1
- (a) Answer: mantissa = 01011000, exponent = 0101
- (b) normalised means the mantissa's first two bits differ (no redundant leading 0s or 1s before the significant digits)B1
- (b) normalisation gives each number a single, unique representation and maximises the number of significant bits available, maximising precisionB1
- (b) Answer: Normalised means the first two mantissa bits differ; this is used to maximise precision and give a unique representation for each value.
- (c) 0.1 is a recurring (non-terminating) binary fraction, so it must be truncated/rounded to fit the fixed number of mantissa bitsB1
- (c) the small rounding error accumulates over repeated additions, causing the running total to drift from the mathematically expected valueB1
- (c) Answer: 0.1 cannot be represented exactly in binary so it is rounded; repeated addition accumulates this rounding error, causing the total to drift from the true value.
- (d) (i) more exponent bits increases the range of values that can be representedB1
- (d) (ii) more mantissa bits increases the precision (accuracy) of the values representedB1
- (d) Answer: (i) increases range; (ii) increases precision.
Question 7
- (a) StackB1
- (a) LIFO (Last In, First Out)B1
- (a) Answer: Stack; LIFO (Last In, First Out).
- (b) Push(6): top=0, stack[0]=6B1
- (b) Push(2): top=1, stack[1]=2B1
- (b) Push(9): top=2, stack[2]=9B1
- (b) Pop() returns 9, top becomes 1B1
- (b) Push(4): top=2, stack[2]=4B1
- (b) Pop() returns 4 (top becomes 1), then Pop() returns 2 (top becomes 0)B1
- (b) Answer: Returned values in order: 9, 4, 2. Final top = 0.
- (c) 2 caoB1
- (c) Answer: 2
- (d) a stack is LIFO, so the last (most recent) action pushed onto the stack is the first one popped off / undone, matching the required behaviourB1
- (d) a queue is FIFO and would instead undo the oldest recorded action first, which would not match how 'undo' is expected to behaveB1
- (d) Answer: A stack's LIFO order means the most recent action is undone first, matching the required behaviour; a FIFO queue would undo the oldest action first instead.
Question 8
- (a) as items are dequeued from the front, the front pointer moves forward but the freed slots at the start of the array are not reusedB1
- (a) so once the rear pointer reaches the end of the array, no more items can be enqueued even though slots earlier in the array are emptyB1
- (a) Answer: Freed slots at the front of the array cannot be reused once the rear pointer reaches the end, so the queue appears full despite having empty slots.
- (b) the rear (and front) pointer wraps around to index 0 once it passes the last index, e.g. using MOD arithmeticB1
- (b) so slots freed near the start of the array can be reused, meaning the queue is only full when all slots are genuinely occupiedB1
- (b) Answer: The pointers wrap around to the start of the array using MOD arithmetic, so freed slots are reused and the queue is only full when genuinely at capacity.
- (c) Enqueue(15): queue[0]=15, rear=1B1
- (c) Enqueue(23) and Enqueue(8): queue[1]=23, queue[2]=8, rear=3B1
- (c) Dequeue() returns 15, front becomes 1B1
- (c) Enqueue(41) and Enqueue(6): queue[3]=41, queue[4]=6, rear wraps to 0 (since (4+1) MOD 5=0)B1
- (c) Dequeue() returns 23, front becomes 2B1
- (c) Answer: Dequeue() calls return 15, then 23. After all operations: front=2, rear=0.
- (d) front=2, rear=0B1
- (d) values in order: 8, 41, 6B1
- (d) Answer: front=2, rear=0; queue contents (front to rear): 8, 41, 6.
Question 9
- (a) 50B1
- (a) Answer: 50
- (b) left child = 20B1
- (b) right child = 40B1
- (b) Answer: Left child = 20, right child = 40.
- (c) left child = 60B1
- (c) right child = 80B1
- (c) Answer: Left child = 60, right child = 80.
- (d) root 50 visited first, correctly followed by the complete left subtreeM1
- (d) left subtree correctly given as 30, 20, 40, 35M1
- (d) full sequence 50, 30, 20, 40, 35, 70, 60, 80 caoA1
- (d) Answer: 50, 30, 20, 40, 35, 70, 60, 80
- (e) sequence 20, 30, 35, 40, 50, 60, 70, 80 attempted with correct methodM1
- (e) sequence fully correct (cao)A1
- (e) explanation that at every node, all values in its left subtree are smaller and all values in its right subtree are larger (the BST property)B1
- (e) so visiting left subtree, then the node, then right subtree at every level guarantees values are output smallest-firstB1
- (e) Answer: 20, 30, 35, 40, 50, 60, 70, 80; because at every node all values in its left subtree are smaller and all values in its right subtree are larger, processing left-node-right at each level always yields ascending order.
- (f) inserting into a BST only requires traversing a single path from the root (typically O(log n) comparisons for a balanced tree) and attaching a new nodeB1
- (f) whereas inserting into a sorted array requires shifting all subsequent elements along by one position to keep the array in order, which is O(n)B1
- (f) Answer: Inserting into a BST only needs a single root-to-leaf path traversal (no shifting), far more efficient than a sorted array, where all following elements must be shifted along.
Question 10
- (a) NOT(A AND B) = (NOT A) OR (NOT B)B1
- (a) Answer: NOT(A AND B) = (NOT A) OR (NOT B)
- (b) NOT(A OR B) = (NOT A) AND (NOT B)B1
- (b) Answer: NOT(A OR B) = (NOT A) AND (NOT B)
- (c) De Morgan's second law applied to NOT(NOT A OR NOT B), giving NOT(NOT A) AND NOT(NOT B)M1
- (c) double negation (involution) law applied: NOT(NOT A) AND NOT(NOT B) = A AND BdM1
- (c) expression now reads Q = (A AND B) OR (A AND B); idempotent law applied (X OR X = X)dM1
- (c) Q = A AND B caoA1
- (c) Answer: Q = A AND B
- (d) A factorised out using the distributive law: A AND (B OR NOT B)M1
- (d) complement law applied: B OR NOT B = 1, giving A AND 1dM1
- (d) identity law applied: A AND 1 = A, so Q = A caoA1
- (d) Answer: Q = A
- (e) the student is correctB1
- (e) this is the distributive law (OR distributes over AND, just as AND distributes over OR): A OR (B AND C) = (A OR B) AND (A OR C)B1
- (e) Answer: Correct; this is an application of the distributive law.
Question 11
- Level 3 Discusses both scenarios in detail, comparing at least two suitable data structures for each with accurate, specific justification based on how operations (insertion, deletion, search/access) are performed and their efficiency (e.g. time complexity or real-world behaviour). Recognises the importance of the required order of operations (FIFO for the print queue) and the effect of frequent updates on the choice of data structure for the spell-checker. The answer is coherent, well-structured and uses correct technical terminology throughout.7-9
- Level 2 Discusses both scenarios with some relevant comparison of data structures, but justification may be partial, one-sided, or lack detail on efficiency/complexity for one of the two scenarios. Some correct use of technical terminology; reasoning is mostly clear but may lack depth or contain minor inaccuracies.4-6
- Level 1 Identifies at least one appropriate data structure for at least one scenario, with limited or no justification, or justification that is largely inaccurate. The answer may address only one of the two scenarios, or lack coherence.1-3
- Level 0 No relevant content, or the response does not address data structures in the context given.0
- Indicative content:
- Print queue: a queue (FIFO) is appropriate because print jobs must be processed in the order they are received, which is fair to users and matches how a physical printer works.
- Print queue: a stack (LIFO) would be inappropriate, since the most recently submitted job would be printed first, which is unfair and does not reflect the required behaviour.
- Print queue: a (circular) queue implemented with an array or linked list allows efficient O(1) enqueue and dequeue operations at each end, without needing to shift other jobs.
- Spell-checker word list: an unsorted array requires a linear search, O(n), to check whether a word exists, which becomes slow for 50000 words.
- Spell-checker word list: a binary search tree allows searching in O(log n) time if the tree remains reasonably balanced, and also supports straightforward insertion of new words as the dictionary changes.
- Spell-checker word list: a hash table allows average O(1) lookup and insertion using a hash function, making it very efficient for a large, frequently-changing word list, though collisions must be managed (e.g. by chaining or probing).
- A hash table (or a well-balanced BST) is likely preferable to an unsorted array for the spell-checker because lookups will be performed very frequently and must be fast; a BST may degrade towards O(n) if it becomes unbalanced, whereas a well-designed hash table maintains near O(1) average performance.
- Valid alternative structures and justifications should be credited if properly explained and appropriate to the scenario, e.g. a sorted array with binary search, O(log n), for the spell-checker if insertions are rare.
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.