Revision Library
Choose a subject
Menu
Computer Science
Need a new topic?
Missing a topic, found a bug, or want something added?

AS Paper 5: Mixed Practice B

A second mixed paper covering boolean logic and logic gates, computer architecture, networks, linear data structures, searching and sorting algorithms and writing and tracing short programs.

24 questions - 80 marks

Download PDF

Open A Level Computer Science workspace

Questions

Question 1 [1 mark]

Boolean Algebra and Logic Gates

A logic circuit implements the Boolean expression X = (A AND B) OR (NOT C).

Evaluate X when A = 1, B = 0 and C = 0.

Question 2 [3 marks]

Searching and Sorting Algorithms

A linear search checks each element of a list in turn, starting from index 0, until the target is found or the list is exhausted.

State the best-case number of comparisons for a linear search on a list of n elements, describe the circumstance in which this best case occurs, and state the best-case time complexity in Big O notation.

Question 3 [2 marks]

Networks and Communication

State what is meant by a network protocol, and give one example of a network protocol.

Question 4 [2 marks]

Boolean Algebra and Logic Gates

State the output of the logic expression A OR B for each of the four possible combinations of A and B (each 0 or 1).

Question 5 [3 marks]

Linear Data Structures

A stack supports push(), pop(), peek() (which returns the top value without removing it) and isEmpty().

The following operations are performed on an empty stack: push(6), push(2), peek(), pop(), isEmpty().

State the value returned by peek(), the value returned by pop(), and the value returned by isEmpty().

Question 6 [2 marks]

Boolean Algebra and Logic Gates

A logic circuit implements the Boolean expression Z = (A AND B) OR (B AND C) OR (A AND C), sometimes called a majority function.

Evaluate Z when A = 1, B = 1 and C = 0, and state, in words, what condition on A, B and C makes Z equal to 1.

Question 7 [3 marks]

Computer Architecture and the CPU

A CPU is connected to memory using three buses: the address bus, the data bus and the control bus.

State the purpose of each of these three buses.

Question 8 [4 marks]

Programming: Trace, Write and Explain

The following pseudocode is executed on the list values = [-3, 8, -1, 5, -9, 2]:

count = 0

FOR EACH v IN values

IF v < 0 THEN

count = count + 1

ENDIF

NEXT v

OUTPUT count

Complete a trace showing which values cause count to increase, and state the value output.

Question 9 [1 mark]

Computer Architecture and the CPU

A computer's memory hierarchy includes CPU registers, cache memory and main memory (RAM), typically in that order from fastest to slowest.

State one reason a computer does not simply use registers for all of its memory, given how much faster they are than main memory.

Question 10 [3 marks]

Programming: Trace, Write and Explain

A student writes the following pseudocode, intended to check whether a list of numbers, values, with n elements (indexed 0 to n - 1) is sorted in ascending order:

isSorted = TRUE

FOR i = 0 TO n - 3

IF values[i] > values[i + 1] THEN

isSorted = FALSE

ENDIF

NEXT i

OUTPUT isSorted

Explain why this code gives the wrong answer for the list [1, 2, 5, 3], and rewrite the FOR line so the code correctly checks every adjacent pair in a list of any length.

Question 11 [3 marks]

Boolean Algebra and Logic Gates

Use De Morgan's laws to write an equivalent expression for NOT (A OR B), using only AND, NOT and the individual variables A and B, then confirm your answer is correct by evaluating both expressions when A = 0 and B = 1.

Question 12 [3 marks]

Networks and Communication

In the client-server model, a web browser (the client) requests a web page from a web server.

Describe the roles of the client and the server in this exchange, and state one advantage of the client-server model over a peer-to-peer model for a busy website.

Question 13 [3 marks]

Programming: Trace, Write and Explain

A student writes the following pseudocode, intended to output the numbers 1 to 5:

i = 1

j = 1

WHILE i <= 5

OUTPUT i

j = j + 1

ENDWHILE

Explain why this code never terminates, and rewrite the loop body so it correctly outputs 1 to 5 and then stops.

Question 14 [4 marks]

Networks and Communication

An IPv4 address is 192.168.1.130 and its subnet mask is 255.255.255.192.

State the number of bits used for the network portion of the address under this subnet mask, and explain how a subnet mask is used to determine whether two IP addresses are on the same subnet.

Question 15 [4 marks]

Computer Architecture and the CPU

A program consists of 5,000,000 instructions. On a particular processor, each instruction takes an average of 3 clock cycles to complete, and the processor runs at a clock speed of 2.5 GHz (2,500,000,000 cycles per second).

Calculate the total number of clock cycles needed to run the program, and hence the total execution time in seconds.

Question 16 [4 marks]

Programming: Trace, Write and Explain

Write pseudocode for a function called IsPalindrome that takes a string, s, as its parameter, and returns TRUE if s reads the same forwards and backwards, and FALSE otherwise. You may assume a function LEN(s) returns the length of s, and that individual characters of s can be accessed using s[i], indexed from 0.

Question 17 [4 marks]

Searching and Sorting Algorithms

The list [5, 2, 9, 1, 6] is sorted using insertion sort, which builds a sorted section at the start of the list by inserting each new element into its correct position.

State the contents of the whole list after the first three elements (5, 2, 9) have been inserted into the sorted section, but before 1 is considered.

Question 18 [5 marks]

Programming: Trace, Write and Explain

Write pseudocode for a function called CountOccurrences that takes a list of values, items, and a target value, target, as parameters, and returns the number of times target appears in items.

Question 19 [5 marks]

Searching and Sorting Algorithms

Quicksort partitions a list around a pivot value: elements smaller than the pivot are moved before it, and elements larger are moved after it.

The list [8, 3, 12, 5, 9, 2] is partitioned using the last element, 2, as the pivot. The elements in each sublist keep their original relative order.

State the two sublists formed either side of the pivot after partitioning, and the pivot's final index (counting from 0).

Question 20 [3 marks]

Boolean Algebra and Logic Gates

Use De Morgan's laws to write an equivalent expression for NOT (A AND B AND C), using only OR, NOT and the individual variables, then confirm your answer is correct by evaluating both expressions when A = 1, B = 1 and C = 0.

Question 21 [5 marks]

Searching and Sorting Algorithms

Quicksort partitions a list around a pivot value: elements smaller than the pivot are moved before it, and elements larger are moved after it.

The list [10, 4, 15, 2, 8, 12] is partitioned using the lower of the two middle elements (index 2), 15, as the pivot. The elements in each sublist keep their original relative order.

State the two sublists formed either side of the pivot after partitioning, and the pivot's final index (counting from 0).

Question 22 [2 marks]

Boolean Algebra and Logic Gates

A logic circuit has inputs A, B and C, and its output Z is 1 for exactly these combinations: A = 1, B = 0, C = 0 and A = 1, B = 0, C = 1, and Z is 0 for every other combination.

Write the Boolean expression for Z as a sum of products (before simplification), then simplify it to its shortest form.

Question 23 [5 marks]

Computer Architecture and the CPU

A processor can find out that a device needs attention either by polling (repeatedly checking the device's status at regular intervals) or by using interrupts (the device signals the processor only when it actually needs attention).

Explain one disadvantage of polling compared with interrupts, and explain why a processor needs to save its current state before running an interrupt service routine (ISR).

Question 24 [6 marks]

Searching and Sorting Algorithms

Quicksort partitions a list around a pivot, then recursively sorts the sublist before the pivot and the sublist after the pivot.

The list [7, 3, 9, 1, 5] is partitioned using the last element, 5, as the pivot, giving the sublist [3, 1] before the pivot and [7, 9] after it, with 5 at index 2.

State the two recursive calls made next, and explain why quicksort's worst-case time complexity is O(n^2) even though its average case is O(n log n).

Model solutions

Mark scheme for Question 1 [1 mark]
Question 1[1 mark]
Answer or workingMarks
X = 1; correct output alone earns full creditA1
Final answer: X = 1.
Mark scheme for Question 2 [3 marks]
Question 2[3 marks]
Answer or workingMarks
stating the best case is 1 comparisonB1
describing this occurring when the target is the first element checked, at index 0B1
stating the best-case time complexity is O(1)B1
Final answer: Best case: 1 comparison, when the target is at index 0; best-case complexity O(1)
Mark scheme for Question 3 [2 marks]
Question 3[2 marks]
Answer or workingMarks
a definition such as: a set of rules that govern how devices communicate and exchange data over a networkB1
a valid example, such as TCP, IP, HTTP, HTTPS or FTPB1
Final answer: A set of rules governing how devices communicate, e.g. HTTP
Mark scheme for Question 4 [2 marks]
Question 4[2 marks]
Answer or workingMarks
the labelled rows 00 -> 0 and 01 -> 1B1
the labelled rows 10 -> 1 and 11 -> 1B1
Final answer: 00 -> 0; 01 -> 1; 10 -> 1; 11 -> 1.
Mark scheme for Question 5 [3 marks]
Question 5[3 marks]
Answer or workingMarks
peek() returning 2.A1
pop() returning 2.A1
isEmpty() returning false.A1
Final answer: peek returns 2; pop returns 2; isEmpty returns false because 6 remains.
Mark scheme for Question 6 [2 marks]
Question 6[2 marks]
Answer or workingMarks
Z = 1A1
the condition that at least two of A, B and C are 1B1
Final answer: Z = 1; Z is 1 exactly when at least two inputs are 1.
Mark scheme for Question 7 [3 marks]
Question 7[3 marks]
Answer or workingMarks
the address bus - carries the memory address the CPU wants to read from or write toB1
the data bus - carries the actual data being transferred between the CPU and memory (or another device)B1
the control bus - carries control signals, such as read/write signals, that coordinate and synchronise the transferB1
Final answer: Address bus: carries the memory address; data bus: carries the data itself; control bus: carries signals that coordinate the transfer
Mark scheme for Question 8 [4 marks]
Question 8[4 marks]
Answer or workingMarks
showing that -3 causes count to increaseM1
showing that -1 causes count to increaseM1
showing that -9 causes count to increase, with no other value identified as causing an increaseM1
output 3A1
Final answer: Count increases at -3, -1 and -9; counts after each item: 1,1,2,2,3,3; output 3.
Mark scheme for Question 9 [1 mark]
Question 9[1 mark]
Answer or workingMarks
stating one valid reason, such as registers being more expensive per byte than RAM or requiring more chip area per byte; either statement alone earns full credit.B1
Final answer: Registers are much more expensive per byte than RAM.
Mark scheme for Question 10 [3 marks]
Question 10[3 marks]
Answer or workingMarks
explaining that the loop omits the final adjacent pair at indices 2 and 3B1
explaining that the missed pair 5,3 is out of order, so the original output incorrectly stays TRUEB1
FOR i = 0 TO n - 2, or an equivalent bound covering every adjacent pairA1
Final answer: The bound n - 3 omits the final pair (5,3), so isSorted incorrectly stays TRUE. Replace with FOR i = 0 TO n - 2.
Mark scheme for Question 11 [3 marks]
Question 11[3 marks]
Answer or workingMarks
(NOT A) AND (NOT B), or an equivalent De Morgan expression using only AND and NOTA1
the original expression evaluating to 0 at A = 0, B = 1B1
the equivalent expression evaluating to 0 at A = 0, B = 1B1
Final answer: (NOT A) AND (NOT B); both sides are 0 at A = 0, B = 1.
Mark scheme for Question 12 [3 marks]
Question 12[3 marks]
Answer or workingMarks
describing the client's role, such as sending a request for a resource, for example an HTTP request for a pageB1
describing the server's role, such as receiving the request, processing it and returning the requested resourceB1
a valid advantage, such as centralised control and management of data and security, or resources being easier to back up when kept in one placeB1
Final answer: The client requests a resource; the server processes the request and returns it. Client-server gives centralised control of data and security
Mark scheme for Question 13 [3 marks]
Question 13[3 marks]
Answer or workingMarks
explaining that only j changes, so i stays 1 and the guard i <= 5 never becomes falseB1
retaining OUTPUT i in the repaired loop bodyM1
incrementing i by 1 after output, producing 1 to 5 and then stopping; removing j is optionalA1
Final answer: i remains 1 because only j changes, so i <= 5 is always true and 1 is output repeatedly. Replace the loop body with OUTPUT i followed by i = i + 1.
Mark scheme for Question 14 [4 marks]
Question 14[4 marks]
Answer or workingMarks
converting the last octet, 192, to binary: 11000000M1
26 network bits in total (8 + 8 + 8 + 2)A1
explaining a bitwise AND is performed between an IP address and the subnet mask to find its network addressB1
stating two addresses are on the same subnet if this calculation gives the same network address for bothB1
Final answer: 26 network bits; two addresses are on the same subnet if ANDing each with the subnet mask gives the same network address
Mark scheme for Question 15 [4 marks]
Question 15[4 marks]
Answer or workingMarks
calculating instructions * cycles per instruction: 5000000 * 3.M1
15000000 cycles.A1
dividing total cycles by 2500000000 cycles/s.M1
0.006 seconds; accept 6 milliseconds.A1
Final answer: 15000000 cycles; 0.006 s = 6 ms
Mark scheme for Question 16 [4 marks]
Question 16[4 marks]
Answer or workingMarks
IsPalindrome with parameter sM1
comparing mirrored characters, or an equivalent comparison with the reversed stringM1
returning FALSE when any corresponding characters differA1
returning TRUE when all corresponding characters match; accept equivalent algorithms without requiring early return or a midpoint boundA1
Final answer: FUNCTION IsPalindrome(s) left = 0 right = LEN(s) - 1 WHILE left < right IF s[left] != s[right] THEN RETURN FALSE ENDIF left = left + 1 right = right - 1 ENDWHILE RETURN TRUE ENDFUNCTION
Mark scheme for Question 17 [4 marks]
Question 17[4 marks]
Answer or workingMarks
2 being shifted before 5 to give the sorted section 2, 5M1
9 remaining after 5, since it is already larger, giving the sorted section 2, 5, 9M1
the unsorted elements 1 and 6 remaining unchanged in their original positionsA1
the complete list 2, 5, 9, 1, 6 Award all 4 marks for the complete correct requested answer: [2,5,9,1,6]. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations.A1
Final answer: [2,5,9,1,6].
Mark scheme for Question 18 [5 marks]
Question 18[5 marks]
Answer or workingMarks
CountOccurrences with items and target parametersM1
initialising a zero counterM1
inspecting every element for equality with targetM1
counting each matching occurrence without stopping earlyM1
returning the count; equivalent valid algorithms receive creditA1
Final answer: FUNCTION CountOccurrences(items, target) count = 0 FOR EACH v IN items IF v = target THEN count = count + 1 ENDIF NEXT v RETURN count ENDFUNCTION
Mark scheme for Question 19 [5 marks]
Question 19[5 marks]
Answer or workingMarks
recognising every other element, 8, 3, 12, 5 and 9, is greater than the pivot value 2M1
concluding no elements belong before the pivotM1
the pivot moving to index 0A1
the sublist after the pivot containing 8, 3, 12, 5, 9A1
the sublist before the pivot being empty Award all 5 marks for the complete correct requested answer: Before pivot: []; after pivot: [8,3,12,5,9]. Pivot 2 finishes at index 0. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations.B1
Final answer: Before pivot: []; after pivot: [8,3,12,5,9]. Pivot 2 finishes at index 0.
Mark scheme for Question 20 [3 marks]
Question 20[3 marks]
Answer or workingMarks
(NOT A) OR (NOT B) OR (NOT C), or an equivalent De Morgan expression using only OR and NOTA1
the original expression evaluating to 1 at A = 1, B = 1, C = 0B1
the equivalent expression evaluating to 1 at A = 1, B = 1, C = 0B1
Final answer: (NOT A) OR (NOT B) OR (NOT C); both sides are 1 at (1,1,0).
Mark scheme for Question 21 [5 marks]
Question 21[5 marks]
Answer or workingMarks
identifying the middle element (index 2), value 15, as the pivotM1
comparing each remaining element, 10, 4, 2, 8, 12, against the pivot value 15M1
recognising every one of these elements is smaller than 15A1
concluding no elements belong after the pivot, so the pivot moves to the last index, index 5A1
the sublist before the pivot containing all five remaining elements, 10, 4, 2, 8, 12, in their original relative order Award all 5 marks for the complete correct requested answer: Using the explicitly named pivot 15: before pivot [10,4,2,8,12]; after pivot []; final index 5. The list has two middle positions, so the wording should identify index 2 (the lower middle). Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations.B1
Final answer: Before pivot: [10,4,2,8,12]; pivot 15 at index 5; after pivot: [].
Mark scheme for Question 22 [2 marks]
Question 22[2 marks]
Answer or workingMarks
the unsimplified sum of products (A AND NOT B AND NOT C) OR (A AND NOT B AND C), accepting reordered termsM1
the shortest expression A AND NOT B; no separate derivation is requestedA1
Final answer: Z = (A AND (NOT B) AND (NOT C)) OR (A AND (NOT B) AND C) = A AND (NOT B).
Mark scheme for Question 23 [5 marks]
Question 23[5 marks]
Answer or workingMarks
one valid disadvantage of polling compared with interrupts, such as wasted CPU time or delayed response to a device.B1
a linked explanation: repeated checks consume time even when no service is needed, or a newly ready device must wait until the next poll; either route earns both disadvantage marks.B1
preserving a return address or program counter before running the ISR.B1
preserving working register values that the ISR might overwrite.B1
explaining restoration allows the interrupted computation to resume correctly; accept an equivalent explanation of sufficient saved context.B1
Final answer: Polling spends CPU time checking inactive devices; saved state permits correct resumption
Mark scheme for Question 24 [6 marks]
Question 24[6 marks]
Answer or workingMarks
identifying the first recursive call as sorting the sublist before the pivot, [3, 1]M1
identifying the second recursive call as sorting the sublist after the pivot, [7, 9]A1
explaining the average case splits the list into two roughly equal halves each time, giving O(log n) levels of recursion with O(n) work partitioning at each level, hence O(n log n)B1
explaining the worst case occurs when a pivot is chosen that is the smallest or largest remaining value each time, for example on an already-sorted list with a fixed choice of pivotB1
explaining this gives sublists of size (n-1) and 0 at every level, meaning n levels of recursion instead of log nB1
concluding n levels each doing O(n) work partitioning gives O(n^2) overall in the worst caseB1
Final answer: Recursive calls sort [3, 1] and [7, 9]; the worst case is O(n^2) because a poor pivot choice (e.g. smallest/largest each time) gives n levels of recursion instead of log n, each doing O(n) work

Build a free practice pack.

Pick the topics, add the student's name and print one PDF.