Specimen Paper Computing

1(a)

Analysts and programmers sometimes need to choose between programming languages.

For instance, a programmer might have to choose between an imperative and a declarative language.

(i)

Explain what is meant by an imperative language, and state an example of an application which could sensibly use an imperative language.

[2]

Each command is an action to be carried out.
Example : Computer game

(ii)

Explain what is meant by a declarative language, and state an example of an application which could sensibly use a declarative language.

[2]

Each statement is a fact or a rule
Example : Expert system for medicine

(b)

A programmer is required to write a program to simulate the arrival of trains at a busy station. He/she has the choice of a specialist simulation language or a general purpose language.

Describe one advantage of each type of language.

[2]

simulation language - has facilities for timing events
general purpose language - may be used for a number of different types of program

(c)

A certain programmer chooses to use an object-oriented approach, using a visual programming language. Explain the two terms object-oriented and visual programming languages and describe two advantages which their use might have over a more traditional approach.

[4]

object-oriented - data types have properties and methods (procedures) associated with them.
visual programming - allows application development for windows (GUI environment)

2(a)

In Computer A, positive or negative integers are represented by the use of two's complementation, using 8 bits.

(i)

Show how the number +30₁₀ is represented.

[1]

00011110

(ii)

Show how the number -30₁₀ is represented.

[1]

11100010

(b)

In Computer B, positive or negative integers are represented by the use of 1 sign bit and 7 magnitude bits. The sign bit is the most significant bit, and is set to 1 to represent negative and set to 0 for zero or positive. Show how the number -30₁₀ is represented in this case.

[1]

10011110

(c)(i)

Convert the number 29₁₀ into hexadecimal.

[1]

(ii)

Binary numbers used by computers are often converted into hexadecimal numbers for the benefit of the human programmers. Describe the advantage of hexadecimal over binary for the programmer.

[1]

hex is easier for humans to read than long binary numbers.

(iii)

These binary numbers could instead be converted into denary (base 10). Describe the advantage of hexadecimal over denary.

[1]

there is a better relationship between hex numbers and binary numbers (4 bits correspond with each hex digit)

3(a)

The names Smith, Jala, Taylor, Avery, Hill, Brown, Ivor, Wang and Rigby are to be entered in the above order into a binary tree structure. In each case the left pointer indicates the condition:

earlier in the alphabet.

The tree structure is started below. Copy and complete the diagram. You can use just the initial letter of each name if you wish: S, J, T, A, H, B, I, W and R.

(b)(i)

Give one advantage of a binary tree structure over a linear linked list.

[1]

It is much faster to find a record.

(ii)

Give one advantage of a linear linked list over a binary tree structure

[1]

programming is more straightforward

4(a)

One (not very satisfactory) way of defining a positive decimal number is:
zero or more digits, followed by a decimal point, followed by zero or more digits.

For instance, the following are covered by this definition:

12.3 0.3 .3 . 2.05 12.

Give an appropriate Backus Naur Form (BNF) definition for a positive decimal number as defined above, defining any terms you introduce.

[2]

<digit> ::= 0|1|2|3|4|5|6|7|8|9
<integer> ::= <digit> | <digit><integer>
<number> ::= null | integer
<positive decimal number> ::= <number>.<number>

(b)

The definition in part (a) is not very satisfactory in that it allows two unusual forms:

the integer followed by a point (eg 12.)
the point on its own (.)

Amend your definition so that these two forms are not allowed.

[2]

<positive decimal number> ::= <integer>.<integer> | .<integer> | <integer>

5(a)

Explain why a compiled program will normally execute faster than an interpreted program.

[2]

There is no translation when execution takes place for a compiled program.
For an interpreted program each line is translated before being executed.

(b)

Most programming environments include some sort of debugging software.

(i)

One example of debugging software is a program trace. Explain the term program trace.

[1]

A trace allows a program to be run line by line.

(ii)

Give an example of an error which debugging software will not be able to find.

[1]

A logical error eg the wrong counters on a loop

(c)

Compilation of a high level language includes the following processes.
Describe each of these processes.

(i)

lexical analysis

[2]

removes all comments and un-necessary spaces etc
converts each element of the program into numerical tokens

(ii)

syntax analysis

[2]

creates a numerical symbol table
checks that the rules of the language have been obeyed

6(a)

Draw up a truth table to demonstrate the EXCLUSIVE OR (XOR) operation.

[2]

XOR	0	1
0	0	1
1	1	0

(b)(i)

Carry out a bit-wise XOR operation on the following two 8-bit binary numbers:

X = 10001011

K = 11100010

[2]

01101001

(ii)

State what the results would be if you carried out a bit-wise XOR on your answer to part b(i) and the number K.

[1]

10001011 (K)

7(a)

Define the term algorithm.

[2]

a sequence of steps to perform a task

(b)

Algorithms are often described using pseudocode. State two other methods of specifying algorithms.

[2]

flowchart
written in English

(c)

Programmers sometimes use recursive algorithms.

(i) Describe the key features of a recursive algorithm.

[2]

the algorithm calls itself
it must have a terminating condition

(ii) Describe two advantages of a recursive algorithm when available.

[2]

a recursive algorithm may be very simple, so easy to program
smaller code means faster programs

(d)

The following algorithm is intended to work out the minimum number of coins required to pay any amount of cash up to £4.99, and output a list of the required coins.

(Note : coins of the following types are available: £1 50p 20p 10p 5p 2p 1p. You should assume that there is no £2 coin available).

For instance, for the amount £1.71, the algorithm will correctly output the following:

£1 coin 50p coin 20p coin 1p coin

algorithm select_coin;

input (amount_in_pounds);
set amount_in_pence = amount_in_pounds * 100;

if amount_in_pence >= 100 then
output "£1 coin";
set amount_in_pence = amount_in_pence - 100;
endif;

if amount_in_pence >= 50 then
output "50p coin";
set amount_in_pence = amount_in_pence - 50;
endif;

if amount_in_pence >= 20 then
output "20p coin";
set amount_in_pence = amount_in_pence - 20;
endif;

if amount_in_pence >= 10 then
output "10p coin";
set amount_in_pence = amount_in_pence - 10;
endif;

if amount_in_pence >= 5 then
output "5p coin";
set amount_in_pence = amount_in_pence - 5;
endif;

if amount_in_pence >= 2 then
output "2p coin";
set amount_in_pence = amount_in_pence - 2;
endif;

if amount_in_pence >= 1 then output "1p coin".

This algorithm will not work correctly for every amount up to £4.99

(i)

Write down the output of this algorithm resulting from an input of

(I) £1.33

[1]

£1 coin 20p coin 10p coin 2p coin 1p coin

(II) £2.44

[1]

£1 coin 50p coin 20p coin 10p coin 5p coin 2p coin 1p coin

(ii)

To correct the algorithm, it is necessary to make one change concerning the number of £1 coins output, and also a similar change relating to two other coins. Write down the other two coins.

[1]

20p coin and 2p coin

(iii)

Copy and amend part of the algorithm so that the correct number of £1 coins is output. (You do not need to consider the other coins you mentioned in part (ii)).

[4]

if amount_in_pence >= 100 then
output "£1 coin";
set amount_in_pence = amount_in_pence - 100;
endif;

should be re-written to...

while amount_in_pence >=100
output "£1 coin"
set amount_in_pence = amount_in_pence - 10
endwhile

8(a)

Most graphical user interfaces (GUIs) systems use a mouse. State why a mouse is particularly suitable for a GUI system.

[1]

Items may be selected by a simple click on the desired icon
The user can look at the screen all the time

(b)

Once the system has been developed, describe how its GUI system might be evaluated.

[2]

ask users whether they had any problems
ask them to fill in a questionnaire about whether they found it easy to use
determine whether errors have been made by the user.

(c)

Several of the software developers are members of a professional computing organisation, and have agreed to be bound by its Code of Conduct. Outline two relevant statements which such a Code of Conduct might contain.

[2]

members should understand current laws
members should always be considerate about the needs of clients

In the following part-question, additional credit will be gained if your answer demonstrates skill in written communication.

(d)

A software development team has been asked to develop a suite of technical programs for use by scientists in a laboratory. It is intended that the package will control scientific equipment and will record results directly. The package is required to have an interface which uses a mixture of GUI and text-based elements. Describe the benefits which a GUI would offer in this case and also the possible benefits of being able to change from a GUI to a text-based interface on occasions.

One method of input which was considered in this case but then rejected was a voice input system involving word recognition. Discuss the difficulties faced by those developing voice input systems.

[11]

The GUI interface has clearly identifiable icons representing different options. This makes it easy to learn for all of the scientists in the lab, whatever level of IT skills they may have. There will be no need for anybody to learn complex commands to operate the software. The icons used in the GUI are similar to those used in other standard software packages, so the users may already be familiar with them.

The alternative text-based interface will offer a wider range of options, as each command may have a number of optional 'switches'. As it will take up less memory the software should run much faster then the GUI. The text-based program may also be set up as a batch file and run automatically under a scheduling program.

Voice input may cause problems as people speak with different accents, at different speeds and possibly in different languages. There may also be problems identifying words that sound the same ('Which' and 'Witch'). People's voices may also be affected by illness - sore throat etc..