Process
AQA A-Level Computer Science 7517
Fundamentals of Programming
Topic overviewData typesProgramming concepts and program structureArithmetic operationsRelational Operations, Constants and VariablesBoolean operationsString-handling operationsRandom numbers and exception handlingSubroutines, parameters and return valuesVariable scope and stack framesRecursive techniquesProgramming paradigms and the procedural approachClasses, Objects, Inheritance and PolymorphismAggregation, Composition, Class Diagrams and Design Principles
Fundamentals of Data Structures
Fundamentals of Algorithms
Theory of Computation
Topic overviewLogic Problems and Algorithm ConstructsPseudo-Code, Hand-Tracing and Program CorrectnessRepresentational Abstraction, Generalisation and Information HidingProcedural and Functional AbstractionData Abstraction and Problem ReductionDecomposition and CompositionAutomation and Finite State MachinesSets and Set NotationSubsets and Set OperationsRegular expressions and regular languagesBackus-Naur Form and syntax diagramsComparing Algorithms and FunctionsOrder of complexity and Big-O notationLimits of computation, tractability and heuristicsComputable problems and the Halting problemTuring machines
Fundamentals of Data Representation
Topic overviewNumber systems and the sets of numbersNumber bases: decimal, binary and hexadecimalBits, bytes and units of informationUnsigned binary and binary arithmeticSigned binary using two's complementFixed point and floating point representationNormalisation of floating point numbersRounding errors, accuracy, range and precisionCharacter coding systemsError checking and correctionBit patterns, analogue and digitalBitmapped graphicsVector graphicsDigital representation of soundMIDI and Data CompressionEncryption
Fundamentals of Computer Systems
Topic overviewHardware, Software and Its ClassificationSystem Software and the Operating SystemTranslators and the Role of the Operating SystemClassification of programming languagesTypes of program translatorLogic Gates and Their Truth TablesLogic Circuits and D-Type Flip-FlopsHalf-Adders and Full AddersBoolean algebra
Fundamentals of Computer Organisation and Architecture
Topic overviewInternal components, buses and von Neumann and Harvard architecturesThe Stored Program Concept and the ProcessorThe Fetch-Execute cycleThe processor instruction setAddressing modesMachine-Code OperationsShifts, Halting and Assembly Language ProgramsInterruptsFactors affecting processor performanceInput and output devicesSecondary storage devices
Fundamentals of Communication and Networking
Topic overviewCommunication methodsCommunication basicsNetwork Topology and Types of NetworkingWireless networkingThe Internet and Packet SwitchingRouting, URLs and Domain NamesFirewalls, Worms, Trojans and VirusesEncryption, Digital Signatures and CertificatesTCP/IPStandard application layer protocolsIP Address Structure and Subnet MaskingIP Standards and Public and Private AddressesDHCP and Network Address TranslationClient server modelThin- versus thick-client computing
Consequences of Uses of Computing
Systematic Approach to Problem Solving
Fundamentals of Databases
Big Data
Fundamentals of Data Structures
Stacks
- 2 things to know
- Paper 1
Overview
Recall questions on push, pop and peek, what the top pointer holds, testing for empty and full, and tracing a sequence of operations on an array-based stack.
What you need to know
Answer each one before you reveal it.
Your recallNot started
Key term
What is meant by stack overflow and stack underflow?
Questions from this subtopic
Each one with the model answer underneath.
- 1
What is a stack?
Model answer
An abstract data type in which items are added and removed at the same end, called the top. It is a last in, first out (LIFO) structure: the most recently added item is the first one to be removed.
- 2
What does the top pointer of a stack hold, and how is a stack in an array of maxSize elements initialised?
Model answer
The top pointer holds the index of the item currently on top of the stack. It is initialised to -1, which means the stack is empty because no item has been pushed yet. The first item pushed raises the top pointer to 0 and is stored at index 0.
- 3
Describe the push operation.
Model answer
Push adds an item to the top of the stack. First test whether the stack is full; if it is, report stack overflow and do not add. Otherwise increase the top pointer by one and store the new item at the array position the top pointer now gives.
- 4
Describe the pop operation.
Model answer
Pop removes the item at the top of the stack and returns it. First test whether the stack is empty; if it is, report stack underflow and do not remove. Otherwise take the item at the position given by the top pointer, then decrease the top pointer by one so that it points at the item beneath.
- 5
What does peek (or top) do, and how does it differ from pop?
Model answer
Peek hands back the value on top without taking it off, so the stack is unchanged and the top pointer stays put. Pop also returns the top value but removes it, decreasing the top pointer by one. Peek must still test for an empty stack first, because there is no value to return if the stack is empty.
- 6
How do you test a stack for empty and for full?
Model answer
The stack is empty when the top pointer is -1, that is when nothing has been pushed or everything pushed has been popped. A stack held in an array is full when the top pointer has reached the last index, that is when top = maxSize - 1.
Other ways to work this
The same content, four other ways.
What is inside Levo
Six ways to work the same material.
Every question in Fundamentals of 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.