What is the difference between a stack and a queue?

A stack follows Last In, First Out (LIFO) order—like a pile of plates where you add and remove from the top. A queue follows First In, First Out (FIFO)—like a line of people where the first person in is served first. Stacks are used for undo operations and function calls, while queues are used for scheduling tasks or buffering data.

How do I choose which sorting algorithm to use?

Consider the size of the data and whether it's nearly sorted. For small datasets (n < 50), bubble sort or insertion sort may be fine due to simplicity. For larger datasets, use merge sort (O(n log n) guaranteed) or quicksort (fast average but O(n^2) worst-case). If memory is limited, in-place sorts like quicksort or heapsort are better. Always analyse the trade-offs between time and space complexity.

What is Big O notation and why is it important?

Big O notation describes the upper bound of an algorithm's time or space complexity as input size grows. It ignores constants and lower-order terms to focus on the dominant factor. For example, O(n) means linear growth, O(n^2) means quadratic growth. It's important because it helps you compare algorithm efficiency and predict performance for large inputs, which is critical in real-world applications.

Can you explain two's complement for negative numbers?

Two's complement is a method for representing signed integers in binary. To get the two's complement of a positive number, invert all bits (change 0 to 1 and 1 to 0) and add 1. For example, +5 in 8-bit is 00000101; invert to 11111010, add 1 gives 11111011 for -5. The leftmost bit indicates the sign (0 for positive, 1 for negative). This allows subtraction using addition circuits.

What is the difference between an array and a linked list?

An array stores elements in contiguous memory locations, allowing fast O(1) access by index but slow O(n) insertion/deletion. A linked list stores elements in nodes with pointers to the next node, allowing fast O(1) insertion/deletion at the head but slow O(n) access. Arrays are better for frequent random access; linked lists are better for frequent insertions/deletions.

How do I trace through a recursive algorithm?

Trace recursion by following the function calls and returns. For example, with factorial(n): if n=0, return 1; else return n * factorial(n-1). For factorial(3): call factorial(3) → 3 * factorial(2) → 2 * factorial(1) → 1 * factorial(0) → 1. Then unwind: factorial(0)=1, factorial(1)=1*1=1, factorial(2)=2*1=2, factorial(3)=3*2=6. Use a stack diagram to track each call's state.

Data types, data structures and algorithms

Q: What is Big O notation and why is it important?

Big O notation describes the upper bound of an algorithm's time or space complexity as input size grows. It ignores constants and lower-order terms to focus on the dominant factor. For example, O(n) means linear growth, O(n^2) means quadratic growth. It's important because it helps you compare algorithm efficiency and predict performance for large inputs, which is critical in real-world applications.

Q: Can you explain two's complement for negative numbers?

Two's complement is a method for representing signed integers in binary. To get the two's complement of a positive number, invert all bits (change 0 to 1 and 1 to 0) and add 1. For example, +5 in 8-bit is 00000101; invert to 11111010, add 1 gives 11111011 for -5. The leftmost bit indicates the sign (0 for positive, 1 for negative). This allows subtraction using addition circuits.

Q: What is the difference between an array and a linked list?

An array stores elements in contiguous memory locations, allowing fast O(1) access by index but slow O(n) insertion/deletion. A linked list stores elements in nodes with pointers to the next node, allowing fast O(1) insertion/deletion at the head but slow O(n) access. Arrays are better for frequent random access; linked lists are better for frequent insertions/deletions.

Q: How do I trace through a recursive algorithm?

Trace recursion by following the function calls and returns. For example, with factorial(n): if n=0, return 1; else return n * factorial(n-1). For factorial(3): call factorial(3) → 3 * factorial(2) → 2 * factorial(1) → 1 * factorial(0) → 1. Then unwind: factorial(0)=1, factorial(1)=1*1=1, factorial(2)=2*1=2, factorial(3)=3*2=6. Use a stack diagram to track each call's state.

OCR

A-Level

This topic covers the representation and storage of data using various primitive types and complex structures, alongside the algorithms used to manipulate them. It also encompasses Boolean algebra, including logic gates, truth tables, and the simplification of expressions using Karnaugh maps and algebraic laws.

Objectives

Exam Tips

Pitfalls

Key Terms

Mark Points

Topic Overview

Data types, data structures, and algorithms form the backbone of computer science, enabling efficient storage, organisation, and manipulation of data. In OCR A-Level Computer Science, you'll explore primitive data types (integer, real, char, string, Boolean) and composite types (arrays, records, tuples). Understanding how data is represented in memory—including binary, hexadecimal, and two's complement—is essential for writing efficient code and solving problems logically.

Data structures like stacks, queues, trees, and graphs provide systematic ways to organise data, each with specific strengths. Algorithms such as searching (binary search, linear search) and sorting (bubble sort, merge sort, quick sort) are analysed for time and space complexity using Big O notation. This topic directly links to programming projects and exam questions, where you must choose appropriate structures and algorithms to optimise performance.

Mastering these concepts is crucial for developing computational thinking skills. You'll learn to break down problems, design efficient solutions, and evaluate trade-offs between different approaches. This knowledge is assessed through both written exams and the non-exam assessment (NEA), where you implement and justify your choices in a real-world context.

Key Concepts

Core ideas you must understand for this topic

→Primitive data types: integer, real, char, string, Boolean—and how they are stored in binary (e.g., two's complement for signed integers, ASCII/Unicode for characters).
→Composite data types: arrays (static, dynamic), records (structs), tuples, and linked lists—understanding their structure, memory allocation, and use cases.
→Abstract data types (ADTs): stack (LIFO), queue (FIFO), tree (binary, binary search), graph (directed, undirected)—their operations and typical implementations.
→Algorithm complexity: Big O notation for time and space (e.g., O(1), O(n), O(n^2), O(log n)), and how to analyse worst-case, best-case, and average-case scenarios.
→Standard algorithms: linear search, binary search, bubble sort, insertion sort, merge sort, quick sort—their steps, efficiency, and when to use each.

What You Need to Demonstrate

Key skills and knowledge for this topic

Correct representation of positive integers in binary and hexadecimal
Accurate use of sign and magnitude and two's complement for negative binary numbers
Correct floating point representation and normalisation
Accurate application of bitwise manipulation (shifts, AND, OR, XOR)
Correct implementation of data structure operations (traversal, insertion, deletion)
Accurate simplification of Boolean expressions using De Morgan's Laws and Karnaugh maps
Correct construction of logic gate diagrams and truth tables for D-type flip flops, half and full adders

Marking Points

Key points examiners look for in your answers

Correct representation of positive integers in binary and hexadecimal
Accurate use of sign and magnitude and two's complement for negative binary numbers
Correct floating point representation and normalisation
Accurate application of bitwise manipulation (shifts, AND, OR, XOR)
Correct implementation of data structure operations (traversal, insertion, deletion)
Accurate simplification of Boolean expressions using De Morgan's Laws and Karnaugh maps
Correct construction of logic gate diagrams and truth tables for D-type flip flops, half and full adders

Examiner Tips

Expert advice for maximising your marks

💡Practice converting between binary, denary, and hexadecimal fluently as these are foundational
💡Always show your working for floating point calculations to gain method marks
💡Use truth tables to verify your Boolean algebra simplifications
💡Be prepared to trace algorithms on paper for stacks, queues, and trees
💡Ensure you can distinguish between the different types of data structures and when each is most efficient to use
💡When analysing algorithms, always state the best, worst, and average-case complexities. Use examples to show you understand the reasoning behind each (e.g., why quicksort is O(n log n) on average but O(n^2) in the worst case).
💡For data structure questions, draw diagrams to illustrate how data is organised (e.g., a stack with push/pop operations). This helps you visualise and avoid errors in written answers.
💡In programming questions, justify your choice of data structure or algorithm by linking it to the problem's requirements (e.g., 'I used a queue because tasks need to be processed in order of arrival').

Common Mistakes

Pitfalls to avoid in your exam answers

Confusing sign and magnitude with two's complement representation
Incorrectly normalising floating point numbers (e.g., failing to ensure the mantissa starts with 0.1 or 1.0)
Errors in bitwise shift operations, particularly regarding logical vs arithmetic shifts
Misapplying Boolean laws during simplification
Failing to correctly identify the base case or recursive step in data structure algorithms
Misconception: Binary search can be used on any list. Correction: Binary search requires the list to be sorted; otherwise, linear search must be used.
Misconception: A stack and a queue are the same thing. Correction: A stack follows Last In, First Out (LIFO), while a queue follows First In, First Out (FIFO). They have different use cases (e.g., stack for function calls, queue for print spooling).
Misconception: Big O notation tells you the exact runtime. Correction: Big O describes how runtime grows with input size, not the actual time. An O(n) algorithm can be slower than an O(n^2) for small n due to constants.

Frequently Asked Questions

Common questions students ask about this topic

Before You Start

Prior knowledge that will help with this topic

•Basic programming concepts: variables, loops, conditionals, and functions (from GCSE or AS Level).
•Number systems: binary, denary, hexadecimal conversions and binary arithmetic (addition, subtraction using two's complement).
•Logical reasoning: ability to trace through simple algorithms and understand flowcharts.

Likely Command Words

How questions on this topic are typically asked

Calculate

Convert

Simplify

Construct

Explain

Trace

Define

Ready to test yourself?

Practice questions tailored to this topic

Data types, data structures and algorithms

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in OCR A-Level Computer Science

Algorithms

Analysis of the problem

Applications Generation

Boolean Algebra

Topic Synopsis

Key Concepts & Core Principles

Exam Tips & Revision Strategies

Common Misconceptions & Mistakes to Avoid

Examiner Marking Points

Data types, data structures and algorithms

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

What is the difference between a stack and a queue?

How do I choose which sorting algorithm to use?

What is Big O notation and why is it important?

Can you explain two's complement for negative numbers?

What is the difference between an array and a linked list?

How do I trace through a recursive algorithm?

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in OCR A-Level Computer Science

Algorithms

Analysis of the problem

Applications Generation

Boolean Algebra