Key term
WJEC A-Level Computer Science 601-5345-3
Hardware: Architecture, Memory and Storage
Networks and Data Transmission
Logic Gates and Boolean Algebra
Data Representation and Data Types
Data Structures
Organisation of Data: Files and Records
Database Systems
The Operating System
Algorithms and Programs
Principles of Programming
Systems Analysis
Software Engineering and Program Construction
Topic overviewIntegrated development environments and their purposeEditors, syntax highlighting and code entry toolsDebugging tools: breakpoints, stepping and watchesTranslation, source code and object codeLexical analysis and the symbol tableSyntax and semantic analysisCode generation and optimisation
Types of Software System
Practical Programming
Data Security and Integrity
Computing, Society and the Law
Topic overviewSocial and economic change from computingComputers and the nature of employmentThe digital divide and cultural changeEnvironmental cost of computingData protection and freedom of information lawThe Computer Misuse Act 1990 and computer crimeCopyright, surveillance and professional codes
Advanced Data Structures and Logic
Recursion, Sorting and Searching
Programming Paradigms and Translators
Topic overviewFunctional, declarative and imperative paradigmsClasses, methods and object-oriented designStandardisation of computer languagesAmbiguity in natural language and unambiguous notationBackus-Naur form and syntax diagramsCompilers, interpreters and assemblersTranslation and execution errors
System Design and Human-Computer Interaction
Software Engineering Tools and Professional Practice
Topic overviewSoftware tools for the software engineering processSoftware packages in systems analysis and specificationSoftware packages in systems designTesting tools and testing strategiesProgram version managementProgram libraries and project management toolsCodes of conduct and professional behaviour
Advanced Architecture and Assembly Language
Communication Networks and File Organisation
Number Representation and Floating Point
Databases and Distributed Systems
Topic overviewConsistency, redundancy and data independenceRelational organisation and normalisationRestructuring data into third normal formEntity relationship modellingQuery languages and SQLValidation, verification and the DBMSBig Data, data warehousing and miningDistributed systems and distributed databases
Operating System Management
Software Systems and Applications
Data Security, Cryptography and Attack
Recursion, Sorting and Searching
- 7 subtopics
- 21 things to know
- A2 Unit 3
What Recursion, Sorting and Searching covers
Recursion, Sorting and Searching is examined in A2 Unit 3, Programming and System Development. It covers recursion, quicksort and merge sort, comparing sorting algorithms, big O notation and algorithm complexity, searching and shortest-path algorithms, traversal of data structures and data compression and its efficiency.
The 7 subtopics
Each one has its own page.
- RecursionRecursive algorithm, factorial function recursively and fibonacci sequence recursively.Open →
- Quicksort and merge sortRecall questions on the pivot and partitioning worked on a list, the base case, why the choice of pivot decides the worst case, the median-of-three, how two ordered lists are merged, the levels of merging, why merge sort is O(n log n) even at worst, and which suits a file too large for memory.Open →
- Comparing sorting algorithmsFour measures used to compare the efficiency of sorting algorithms, stable sort and pass through the data in a sorting algorithm.Open →
- Big O notation and algorithm complexityTime complexity and space complexity.Open →
- Searching and shortest-path algorithmsRecall questions on the complexity of linear and binary search and why, the comparisons needed on a million items, when linear beats binary, why binary needs an array, what Dijkstra's algorithm records and why it can finalise the smallest distance, negative weights, a worked shortest route, and A*.Open →
- Traversal of data structuresTraversing a data structure, how a linked list is traversed and pre-order traversal of a binary tree.Open →
- Data compression and its efficiencyCompression ratio of a compressed file and principle behind Huffman coding.Open →
What you need to know
Answer each one before you reveal it.
Your recallNot started
Key term
Why does no single sorting algorithm suit every situation?
Key term
How does the A* algorithm differ from Dijkstra's algorithm?
Key term
Describe how a linked list is traversed.
Key term
On what principle does quicksort work?
Key term
What does Big O notation express about an algorithm?
Key term
Define the compression ratio of a compressed file.
Key term
What is a recursive algorithm?
Key term
What is the pivot in quicksort?
Key term
Name four measures used to compare the efficiency of sorting algorithms.
Key term
What is time complexity?
Key term
State the complexity of a binary search and explain why it has that complexity.
Key term
What is meant by traversing a data structure?
Numbers
A 5 MB file is compressed to 2 MB. Calculate the saving percentage.
Key term
What happens when a recursive routine is written without a base case?
Key term
The list 7, 2, 9, 4, 1, 8, 5 is partitioned about the pivot 5. Which values end up on each side of it?
Key term
What effect does a swap flag have on the best-case running time of a bubble sort?
Key term
What is space complexity?
Key term
State the greatest number of comparisons a binary search makes on a sorted list of 1,000,000 items.
Key term
Why can a singly linked list not be traversed backwards?
Key term
A file of 800 KB is compressed to 200 KB. State the compression ratio and the saving percentage.
Take Recursion, Sorting and Searching further
The same content, four other ways.
Questions from this topic
Each one with the model answer underneath.
- 1
What is a recursive algorithm?
Model answer
A recursive algorithm is one that solves a problem by calling itself on a smaller version of the same problem.
- 2
Name the two parts every recursive definition must have.
Model answer
It must have a base case that is answered without any further call, and a general case that calls the routine again on a smaller problem.
- 3
What happens when a recursive routine is written without a base case?
Model answer
The calls never stop, so the stack keeps growing until the memory reserved for it is exhausted and the program crashes.
- 4
Which data structure supports recursion while a program runs, and what is stored on it?
Model answer
A stack supports it, holding one frame for each unfinished call containing that call's return address, parameters and local variables.
- 5
Define the factorial function recursively.
Model answer
The factorial of 1 is 1, and the factorial of any n greater than 1 is n multiplied by the factorial of n − 1.
- 6
A recursive factorial routine with a base case of 1 is asked for the factorial of 5. How many times is the routine entered, and what value is returned?
Model answer
It is entered five times, for 5, 4, 3, 2 and 1, and it returns 120.
What is inside Levo
Six ways to work the same material.
Recursion, Sorting and Searching revision questions
- What does Recursion, Sorting and Searching cover in WJEC A-Level Computer Science?
- 7 subtopics: recursion, quicksort and merge sort, comparing sorting algorithms, big o notation and algorithm complexity, searching and shortest-path algorithms, traversal of data structures and data compression and its efficiency. Each one has its own page with questions and model answers.
- How is Recursion, Sorting and Searching organised?
- By the WJEC 601-5345-3 specification, subtopic by subtopic, so it matches the order you are taught it in.
Every question in Recursion, Sorting and Searching, 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.