CP4 Computing June 2006

[1](a)

Describe a computer application where a queue is the most appropriate data structure to use, and explain why it is the most appropriate data structure.

[2]

a job queue for a printer
because it is a First In First Out data structure - the jobs get printed in the order they are received.

(b)

Describe a computer application where a stack is the most appropriate data structure to use, and explain why it is the most appropriate data structure.

[2]

storing return addresses for subroutines
...because it is a Last In First Out data structure.

[2]

It is very important that a computer system has a well designed Human-Computer Interface (HCI).

(i)

Describe two advantages and one disadvantage of handwriting recognition as an input method.

[3]

there is no need for a bulky keyboard - all that is needed is a stylus or pen to write on a touch-sensitive screen/pad.
a simple and natural way of entering data- almost everyone can write.
people with bad handwriting might find it difficult to use as the computer may not recognise the letter shapes.

(ii)

Describe two advantages and one disadvantage of speech synthesis as an output method.

[3]

no need for bulky input peripherals - a simple microphone is all that is needed.
it can be used by people who need their hands free such as drivers, pilots or surgeons.
there may be inaccuracies - some words may sound the same but are spelt differently (Eg. to,too,two)

(iii)

When might a text-based interface be preferable to a graphical user interface (GUI)?

[1]

when computer resources such as memory are minimal.

(iv)

What is meant by the term natural language interface?

[1]

an interface that uses language as a human might speak it - including possibly slang expressions.

[3](a)(i)

Convert the 12 bit binary number 101111010111 to hexadecimal.

[1]

(ii)

Why is hexadecimal often used as an alternative to binary?

[1]

less complex on the eye - it is easier to read so fewer mistakes.

(b)

In a certain computer program, real numbers are rounded before being added together.

(i)

Explain the term rounding, and give an example of its use.

[2]

a real number is converted to the nearest integer...
...if the decimal part is less than 0.5 then the real number is rounded down to the next integer below...
if the decimal part is 0.5 or more then the real number is rounded up to the next integer above.
Eg. Pupils' average exam marks could be rounded to the nearest integer.

(ii)

Why might the addition of rounded numbers cause excessive inaccuracy?

[1]

the decimal parts of the real numbers that are ignored when rounding could accumulate into a large amount.

(c)(i)

Give an example of a number which cannot be stored as an integer.

[1]

12.5

(ii)

Describe what is meant by floating point form.

[1]

a real number is represented as a mantissa and an exponent ...
...in the format (mantissa * 2 ^ exponent) for binary.

(iii)

Describe one advantage of storing a number as an integer when it is possible to do so, compared with storing the number in floating point form.

[1]

an integer uses less storage space than a floating point number.

[4](a)

Draw a labelled diagram to show what is meant by a linked list.

[2]

(b)

In a certain implementation, a linked list of integers is actually stored in table form as shown below:

Address	Integer	Pointer
101	6786
102	4231
103	6971
104	3217
105	2410
106	5233
...
...

The integers are to be processed in ascending numerical order.

(i)

The variable first points to the smallest integer in the list. What is the value of first?

[1]

(ii)

Copy the table and complete the pointer column.

[3]

Address	Integer	Pointer
101	6786	103
102	4231	106
103	6971	0
104	3217	102
105	2410	104
106	5233	101
...
...

[5](a)

A certain software tool includes a program trace facility and allows for break points to be set up.

(i)

What name is given to this type of software tool?

[1]

debugging tool

(ii)

Outline the role of a program trace facility.

[1]

it displays the lines of program code in the order they are executed.

(iii)

Outline the role of a break point.

[1]

the program stops execution at a break point and the programmer can check the values of variables.

(iv)

Name one other facility which this type of software tool is likely to include.

[1]

memory dump - to view the contents of memory
diagnostic error messages - to help identify errors in the program code.

(b)

Describe what is meant by a subprogram library and give an example of its use.

[2]

a collection of subroutines that have been. coded, tested and debugged.
For example, frequently used graphics routines could be stored in a subprogram library and used in the development of any other programs.

(c)

Give an example of an application which might use a special purpose language.

[1]

a special purpose program would be used to develop programs for industrial robots.

(d)

Describe two features of CASE tools which could be used during program development.

[2]

a project management tool for planning the development stages of the program.
a graphics tool for drawing flowcharts or data flow diagrams.

(e)

Explain what is meant by the term relocatable code.

[1]

program code that can be placed anywhere in the computer's memory when the program is loaded, and will run successfully.

[6]

J is the eight digit binary number 10110110
K is the eight digit binary number 01011010

There are three logical operations that can be carried out on a pair of binary numbers. These are AND, OR and XOR.

(i)

A logical operation is carried out out on J and K giving the result 11101100
Which logical operation has been carried out in this case?

[1]

(ii)

A different logical operation is carried out on J and K giving the result 11111110
Which logical operation has been carried out in this case?

[1]

(iii)

Write down the effect of carrying out the logical operation NOT J.

[1]

01001001

(iv)

Write down the effect of carrying out an arithmetic shift left by one place on K.

[1]

00101101

[7](a)

Explain what is meant by the term algorithm.

[2]

an ordered sequence of steps...
...used to perform a task.

(b)

One method of describing an algorithm is a flow chart.
State two other methods.

[2]

pseudocode
text description

(c)

A recursive algorithm is one which calls itself.
What other feature does a recursive algorithm need to have?

[1]

a terminating condition.

(d)(i)

A program can pass variables to a procedure. What name is given to the variables passed in this way?

[1]

parameters

(ii)

During this operation, variables are sometimes passed by value. Variables can be passed by another method.
Name the other method and explain how it operates.

[2]

by reference
the address of the parameter is passed to the procedure. Any changes to the value of the parameter survives when the procedure is completed.

[8]

One way of defining an integer is:

a plus sign or minus sign or neither, followed by one or more digits

For instance, the following are covered by this definition:

4 -3 +3 56 -247 0

(i)

Give an appropriate Backus Naur Form (BNF) expression for an integer, as defined above, defining any terms you introduce.

[4]

<unsigned integer> ::= <digit> | <digit><unsigned integer>
<integer> ::= + <unsigned integer> |
<unsigned integer> | - <unsigned integer>

(ii)

Draw a syntax diagram for the definition of an integer given above.

[2]

[9]

An algorithm is required to work out the minimum number of coins required to pay any amount of cash up to 99 pence (99p), and output a list of the required coins.

Note: coins of the following values are available: 50p 20p 10p 5p 2p 1p

For instance, for the amount 97p, the algorithm is required to output the following:

50p coin 20p coin 20p coin 5p coin 2p coin

The first few lines of the required algorithm are shown below.

algorithm SelectCoin

input (AmountInPence)

if AmountInPence >= 50 then
begin
output " 50p coin "
set AmountInPence = AmountInPence - 50
end

while AmountInPence >= 20
output " 20p coin "
set AmountInPence = AmountInPence - 20
endwhile

(i)

Complete this algorithm. (It is not necessary to copy the above, but you may do so if you wish.)

[4]

if AmountInPence >= 10
begin
     output "10p coin"
     set AmountInPence = AmountInPence - 10
end

if AmountInPence >= 5
begin
     output "5p coin"
     set AmountInPence = AmountInPence - 5
end

while AmountInPence >= 2
     output " 2p coin "
     set AmountInPence = AmountInPence - 2
endwhile

if AmountInPence = 1
begin
     output "1p coin"
     {set AmountInPence = AmountInPence - 1} (not needed)
end

(ii)

This algorithm will not give the minimum number of coins when the amount input is greater than 99p. Describe in detail what will happen if an amount greater than 99p is input.

[2]

There are no £1 coins available so a number of 50p coins should be used instead - the algorithm only allows for one 50p coin.
Example : £1.00
The algorithm gives 50p, 20p, 20p, 10p (4 coins)
...instead of 50p, 50p (two coins)

[10]

In the following question, additional credit (up to 3 marks) will be gained if your answer demonstrates skill in written communication.

Computer programs normally need to be translated into a form acceptable to the computer before they can be executed.

Briefly describe the purpose of a compiler, an interpreter and an assembler, ensuring that you distinguish between the three.

Describe in detail the principal stages of compilation.

[7+3]

A compiler translates a complete high level language program into executable machine code. This executable code can be run as often as needed without further compilation.
An interpreter translates and executes each instruction of a high level language program in turn.
An assembler converts a low level language (assembly language) program into an executable machine code program.

There are three stages of compilation :
lexical analysis - unnecessary text such as comments and spaces are removed from the program, and the program is converted into a symbol table. This is a table of numbers created by the compiler from the instructions, variables, numbers and strings used in the program.

syntax analysis - a check is made that the program obeys the rules of syntax of the language. Semantic analysis is carried out to analyse the meaning of the program and the order in which instructions are to be executed.

code generation - the executable object code is generated. Optimisation techniques make sure the finished program is as small as possible and runs as fast as possible.