Programming Techniques

Question 1

Stepwise Refinement

Answer 1

Breaks problem into progressively smaller sections until each section can be written in single procedure/function.

Question 2

Top-down design

Answer 2

Produced through the process of stepwise refinement.

Question 3

Function

Answer 3

Block of code which performs a single task. Returns a single value. Uses local variables.

Question 4

Procedure

Answer 4

Block of code which performs a task. Receives parameter values. Uses local variables. It may or may not produce a single value

Question 5

Benefits of using proc/func Features of struct progs

Answer 5

Can be tested separately. Easier to maintain the program. Main program is simpler and code clearly structured. Use of library routines saves time. Code is reusable. Produced faster and to higher standard as proc/func may be shared between coders.

Question 6

Variable

Answer 6

An identifier / memory location representing a value needed by the program. Value may change while the program is running.

Question 7

Parameter

Answer 7

Is an item of data supplied to a procedure or function. Data can be passed by reference or by value. Used as local variables.

Question 8

Pass by value

Answer 8

Only actual value passed. Procedure/function can only modify a copy of original variable (and not the original variable itself).

Question 9

Pass by reference

Answer 9

Provides procedure/function with actual address to original variable therefore allowing it to permanently alter its contents.

Question 10

Local Variables

Answer 10

A variable defined within one part of the program (procedure/function) & 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 procedures and functions. An example of a local variable could be a loop counter.

Question 11

Global Variables

Answer 11

A variable defined at the start of the program which exists throughout the program (including within functions and procedures). Global variables allow data to be shared by modules. They are overridden by local variables with the same name
An example of a global variable could be VAT rate.

Question 12

Use of stack

Answer 12

To help control the flow of instructions. When a subroutine is called the return address is placed on the stack followed by the parameters of the subroutine (if there are any). When the subroutine executes it first pops the parameters off the stack. When it finishes it pops the return address off the stack so control can pass back to the instruction at the calling address.

Question 13

Backus-Naur Form

Answer 13

(BNF) is a notation technique used to unambiguously describe the syntax of programming languages.

Question 14

Why is BNF needed

Answer 14

To unambiguously define the syntax of a computer language.

Question 15

Recursion in BNF

Answer 15

::= 0|1|2|3|4|5|6|7|8|9

::= |

Question 16

Syntax Diagrams – Purpose

Answer 16

To define terms unambiguously (for a computer language).

Question 17

Infix Notation

Answer 17

The way we normally work e.g. 5 + 6

Question 18

Reverse Polish Notation

Answer 18

Also known as postfix notation e.g. 5 6 +

Question 19

RPN →infix conversion

Answer 19

1. Completely parenthesize the infix expression according to order of priority you want. 2. Move each operator to its corresponding right parenthesis. 3. Remove all parentheses.

Question 20

RPN Advantages

Answer 20

Simpler to evaluate by a machine (no need for brackets). Can be evaluated as they are entered, they are not limited to a certain number of operators in an expression.

Question 21

RPN↔infix - stacks

Answer 21

Stacks are used in the evaluation of RPN expressions.

Question 22

RPN↔infix - trees

Answer 22

Trees can be traversed in-order to obtain the infix and post-order to obtain the RPN (postfix).

Question 23

In-order traversal

Answer 23

Place a dot under each node. Trace around tree starting to left of root. As you pass underneath a node output its data.

Question 24

Post-order traversal

Answer 24

Place a dot on the right of each node. Trace around tree starting to left of root. As you pass to right of node output its data.

Question 25

Post-order Algorithm

Answer 25

1. Traverse the left sub tree until there isn’t one. 2. Traverse the right sub tree (if there is one). 3. Re-visit the root of the current branch. 4. Repeat 1, 2, 3 until every node has been visited.

Question 26

In-order Algorithm

Answer 26

1. Traverse the left branch until there is no left branch. 2. Visit the root of the current branch. 3. Traverse the right sub tree if there is one. 4. Repeat steps 1, 2 and 3 until every node has been visited.