Key term
OCR A-Level Computer Science H446
Processors: Structure, Performance and Types
Input, Output and Storage
Systems Software
Topic overviewOperating systems: need, function and purposeMemory management: paging, segmentation and virtual memoryInterrupts and the interrupt service routineScheduling algorithms: first come first served, round robin and shortest job firstScheduling algorithms: shortest remaining time, multi-level feedback queues, traces and choosing an algorithmTypes of operating systemBIOS, device drivers and virtual machines
Applications Generation
Software Development
Types of Programming Language
Topic overviewProgramming paradigms and procedural languagesAssembly language and the Little Man ComputerModes of addressing memoryObject-oriented programming: classes and objects, attributes and methods, encapsulationObject-oriented programming: inheritance, polymorphism, advantages and disadvantages
Exchanging Data
Topic overviewCompressionEncryptionHashingFlat file and relational databases, keys and indexingReferential integrity, entity relationship diagrams and database management systemsNormalisation to 3NFSQL: Interpreting and Modifying QueriesCapturing, Selecting, Managing and Exchanging DataTransaction Processing, ACID, Record Locking and Redundancy
Networks
Web Technologies
Data Types and Number Representation
Topic overviewPrimitive data typesBinary, hexadecimal and denary conversionNegative numbers: sign and magnitude and two's complementBinary addition, subtraction and overflowFloating point representation and normalisationFloating point addition and subtraction, and fixed point comparedBitwise shiftsMasks with AND, OR and XORCharacter sets: ASCII and Unicode
Data Structures
Topic overviewArrays and recordsLists and tuples, and creating, traversing, adding and removing itemsLinked ListsStacksQueues and Circular QueuesGraphsTrees and binary search trees: structure, insertion and searchingDeleting from a binary search tree, traversals, uses of trees and general treesHash Tables
Boolean Algebra
Legal, Moral, Cultural and Ethical Issues
Topic overviewComputing related legislation: Data Protection Act 1998Computing related legislation: Computer Misuse Act 1990Computing related legislation: Copyright, Designs and Patents Act 1988Computing related legislation: Regulation of Investigatory Powers Act 2000Moral and ethical issues: computers in the workforce, automated decision making and artificial intelligenceMoral and ethical issues: environmental effects, censorship, monitoring behaviour and analysing personal informationMoral and ethical issues: piracy, offensive communications, layout, colour and character sets
Elements of Computational Thinking
Problem Solving and Programming
Topic overviewProgramming techniques: Programming constructsProgramming techniques: RecursionProgramming techniques: Global and local variablesProgramming techniques: modularity, functions and procedures, and parameter passingProgramming techniques: Use of an IDE to develop/debug a programProgramming techniques: Use of object oriented techniquesComputational methods: solvable problems, problem recognition, decomposition, and divide and conquerComputational methods: Use of abstraction and backtrackingComputational methods: data mining, heuristics and performance modellingComputational methods: pipelining, visualisation and choosing a method
Algorithms
Topic overviewDesigning and analysing an algorithmMeasuring efficiency and Big O notationComparing algorithms and choosing one for a taskStacksQueuesLinked listsTrees and binary search treesTraversing a tree: depth-first and breadth-firstBubble sortInsertion sortMerge sortQuick sortComparing the four sorting algorithmsLinear searchBinary searchDijkstra's shortest path algorithmThe A* algorithm
Data Structures
- 9 subtopics
- 21 things to know
- Component 01
What Data Structures covers
Data Structures is examined on component 01 of OCR Computer Science, Computer systems. 124 recall questions across 9 subtopics.
Where it is assessed
Component 01
Computer systems, the whole of the first paper.
Check the OCR specification ↗The 9 subtopics
Each one has its own page.
- Arrays and recordsRecall questions on one, two and three-dimensional arrays, calculating element addresses, why arrays give direct access, the limitations of arrays, records, and how arrays differ from records and are combined into arrays of records.Open →
- Lists and tuples, and creating, traversing, adding and removing itemsRecall questions on lists and tuples and how they differ from arrays, immutability, when to choose a tuple, and how to create, traverse, add to and remove from arrays, records and lists.Open →
- Linked ListsRecall questions on linked lists and how they are stored, the free list, advantages and disadvantages against arrays, creating, traversing and searching a list, adding, inserting and deleting nodes in the right pointer order, and doubly linked lists.Open →
- StacksRecall questions on stacks and their uses, the stack pointer, creating a static stack, push, pop and peek, overflow and underflow, static and dynamic stacks, tracing operations, and why recursion needs a stack rather than a queue.Open →
- Queues and Circular QueuesRecall questions on queues and their uses, front and rear pointers, enqueue and dequeue, the wasted space of a linear queue, circular queues with modulo arithmetic, telling full from empty, tracing operations, and static and dynamic queues.Open →
- GraphsRecall questions on directed, undirected and weighted graphs, adjacency matrices and adjacency lists and when to use each, creating graphs and adding or removing nodes and edges, traversals, visited lists, and how a tree relates to a graph.Open →
- Trees and binary search trees: structure, insertion and searchingRecall questions on tree terminology, binary trees and the binary search tree rule, how a tree is stored and created, inserting and searching for values with traces, search efficiency, and the effect of inserting sorted data.Open →
- Deleting from a binary search tree, traversals, uses of trees and general treesRecall questions on deleting leaf, one-child and two-children nodes from a binary search tree, in-order successors and predecessors, pre-order, in-order, post-order and breadth-first traversals, uses of trees, and adding nodes to a general tree.Open →
- Hash TablesRecall questions on hash tables and hash functions, inserting with linear probing, lookup, collisions and why they are unavoidable, separate chaining and other collision strategies, load factor, performance, deletion, and when a hash table fits.Open →
What you need to know
Answer each one before you reveal it.
Your recallNot started
Key term
What is the key difference between an array and a record?
Key term
What is a list?
Key term
How do you add an item to an array, and to a list?
Key term
How do you search a linked list for a value?
Key term
What is a stack?
Key term
Describe the push operation.
Key term
What does peek do, and how is it different from pop?
Key term
What is a queue?
Key term
Give three uses of a queue in a computer system.
Key term
What is wrong with a plain linear queue after it has been used for a while?
Key term
Give three real-world things that are naturally modelled as graphs.
Key term
A graph has nodes A, B, C, D and undirected edges A-B, A-C, B-D and C-D. Write out its adjacency matrix.
Key term
What makes a tree binary?
Process
Describe the procedure for inserting a value into a binary search tree.
Key term
The values 50, 30, 70, 20, 40, 60, 80 are inserted in that order into an empty binary search tree. Describe the tree that results.
Key term
How do you delete a node that has exactly one child?
Key term
How do you delete a node that has two children?
Key term
Give three uses of trees.
Key term
Why is deleting from a hash table that uses linear probing more awkward than it looks?
Numbers
How many elements does an array declared as 2 by 3 by 4 hold?
Take Data Structures further
The same content, four other ways.
Commonly confused
Pairs that lose marks when they are blurred together.
A stack vs A queue
A stack: a structure where the last item added is the first one removed. A queue: a structure where the first item added is the first one removed.
Stack overflow vs Stack underflow
Stack overflow: the error raised when something is pushed onto a structure that is already full. Stack underflow: the error raised when something is taken from a structure that is already empty.
An array vs A record
An array: an ordered collection of items of the same type, reached by index. A record: a collection of related fields which may each be of a different type.
Questions from this topic
Each one with the model answer underneath.
- 1
What is an array?
Model answer
An ordered, indexed collection of elements that are all of the same data type, held in a block of consecutive memory locations. It has a size fixed when it is created, and each element is reached by its index (position number) rather than by searching for it.
- 2
A one-dimensional array is a row of values. What does a two-dimensional array give you, and how do you get at a single element?
Model answer
A two-dimensional array is a table: rows and columns. You reach a single element with two indices, conventionally the row first and the column second, for example grid[2][5] meaning row 2, column 5. It is the natural structure for anything grid-shaped, such as a spreadsheet, a board game, a seating plan or a black-and-white image.
- 3
Describe what a three-dimensional array is and give a use for one.
Model answer
A three-dimensional array is effectively a stack of two-dimensional tables, so it needs three indices, for example cube[layer][row][column]. Uses include a three-dimensional game world or voxel model, a colour image where the third index selects the red, green or blue channel, or exam marks stored as [student][subject][term].
- 4
How many elements does an array declared as 2 by 3 by 4 hold?
Model answer
24. The sizes of the dimensions multiply: 2 x 3 x 4 = 24 elements.
- 5
Explain why an array can jump straight to element 500 without looking at the other 499.
Model answer
Because the elements are all the same size and stored contiguously, the computer can calculate the address of any element arithmetically rather than searching for it: address = base address + index x size of one element. That single calculation gives constant-time random access, which is the array's main strength.
- 6
An array of 4-byte integers begins at address 2000 and is indexed from 0. What is the address of element 6?
Model answer
2024. Address = 2000 + (6 x 4) = 2000 + 24 = 2024. Note that if the array were indexed from 1 instead, you would use (6 - 1) x 4, giving 2020 - always check the base index.
What is inside Levo
Six ways to work the same material.
Data Structures revision questions
- What does Data Structures cover in OCR A-Level Computer Science?
- 9 subtopics: arrays and records, lists and tuples, and creating, traversing, adding and removing items, linked lists, stacks, queues and circular queues, graphs, trees and binary search trees: structure, insertion and searching, deleting from a binary search tree, traversals, uses of trees and general trees and hash tables. Each one has its own page with questions and model answers.
- How is Data Structures organised?
- By the OCR H446 specification, subtopic by subtopic, so it matches the order you are taught it in.
Every question in Data Structures, on a schedule.
Attempt a question from memory, write the correct version, then attempt it again. Levo records the jump between your first attempt and your last, and brings each question back on the day you are due to forget it.
Or £46 a year, about £3.83 a month. Cancel anytime.