F453 - programming techniques Flashcards
What type of traversal should be used to obtain reverse polish from a binary tree?
post-order (traversal)
State a data structure that may be associated with reverse polish notation
stack binary tree
What symbol used in mathematical expressions is not required in reverse polish?
bracket
How can functions and procedures develop a program in a structured way?
each module can be written as a functional procedure… …which can be tested individually library routines code is reusable main program consists of calls to functions/procedures… …which may be nested
Compare the use of local and global variables and parameters
local variables a variable defined within one part of program… …& is only accessible in that part data contained is lost when execution of that part of program is completed the same variable names can be used in different modules global variables a variable that is defined at the start of a program… & exists throughout program… …including functions/procedures allows data to be shared between modules overridden by local variables with the same name parameters information about an item of data… …supplied to a function or procedure can be passed by reference or by value used as a local variable
What data structure is used when procedures are called during program execution?
stack
What is the purpose of using a stack?
so program can return correctly when procedure has been completed/store return address allows data to be transferred
State the need for BNF
to unambiguously define the syntax of a computer language
What’s the use of functions, procedures and step-wise refinement when developing a program?
function: block of code… …which performs a single task/calculation… returns a single value uses local variables procedure: block of code… …which performs a task …which may or may not produce a single value uses local variables stepwise refinement: breaks a problem into sections… …which become progressively smaller… …until each module can be written as a single procedure/function each module can be tested separately library routines can be used
What data structure is used to handle procedure calling and parameter passing?
stack
What’s a parameter?
(information about) an item of data… …supplied to a procedure or function may be passed by reference or by value used as a local variable
What is the purpose of a syntax diagram?
to define terms unambiguously (for a computer language)
What is an advantage of reverse polish over infix notation?
any expression can be processed in order (left to right) no rules of precedence are needed/no brackets are needed/unambiguous
State what is meant by selection (2)
A condition is used to decide whether code should be executed (if statement)
State what is meant by iteration (2)
code is executed repeatedly (While or For loop)
Look at image
only 1 letter allowed
letter missing
Look at image
identifierA must include 1 or more letters
identifierB need not include any letters
eg $2 is valid for identifierB but not for identifierA…
…while $2ab is valid for both
Look at image
(b) (i) only 1 letter allowed/letter must be at start only [1] 8
(b) (ii) G is not defined (as a letter) [1] 8
(c) e.g. < DIGITS> ::= | < DIGIT> < LETTERS > ::= < LETTER > | < LETTER > < LETTERS > ::= < DIGITS> | < DIGITS> < LETTERS > • DIGITS defined correctly • LETTERS defined correctly • NEW_CODE defined correctly [
Look at image
(i) to define terms unambiguously (for a computer language) [1]
(ii) Backus-Naur Form
Look at image
Look at image
Look at image
Look at image
