CP4 Computing June 2008

[1]

Pupil information in a school is held on a computer system.

(i)

Give an example involving pupil information where a record would be the most appropriate data structure. Describe why an array would not be suitable in this case.

[2]

PupilName (string); DateOfBirth(Date); AverageExamMark(Real)
An array would not be suitable as the data types are different.

(ii)

Draw a diagram to show a situation involving pupil information where a three-dimensional array would be the most appropriate data structure.

[2]

Year 7 Exam	Maths	English	Science
Tom	67	38	49
Jenny	56	55	59
Adrian	78	62	77

Year 8 Exam	Maths	English	Science
Tom	67	69	52
Jenny	77	80	75
Adrian	83	57	77

Exam marks for three pupils and three subjects for two years.

[2]

A well designed human computer interface (HCI) is very important to the users of a computer system.

(i)

For each of the following three types of HCI, describe a different situation which could sensibly use this type of HCI and give one reason why this would be beneficial in each case.

(I)

handwriting input;

[2]

a palmtop computer used to store diary events
a keyboard would be too large for the palmtop

(II)

speech recognition input;

[2]

a surgeon may input requests for information from a computerised database
hands may be occupied with a surgical operation

(III)

speech synthesis output.

[2]

a spoken warning that a seat-belt may not be done up in a car.
no need for the driver to take his eyes of the road when driving

(ii)

Describe three problems associated with speech recognition input

[3]

regional accents may not be recognised
different languages would need to be used in different countries
someone with a cold or voice problem may not be able to use it.

[3](a)

Write down truth tables for:

(i)

the AND operation

[2]

AND 0 1

0 0 0

1 0 1

(ii)

the OR operation

[2]

OR 0 1

0 0 1

1 1 1

(b)

If A=10110001

B=11001011

Carry out the following operations:

(i)

(A AND B)

[2]

10000001

(ii)

(A AND B) OR A

[2]

10110001

[4]

A queue is a type of data structure.

(i)

Explain, using a diagram, the term queue.

[2]

A FIFO (First In First Out) data structure.
Two pointers to show the START and END of the queue

(ii)

Explain what should happen when an attempt is made to add an item to a full queue.

[1]

an error message 'Queue full' should be output.

(iii)

Describe a situation where a queue would be used in a computer system, and explain why the queue is the most appropriate data structure in this case.

[2]

jobs waiting for output to a printer would be put in a queue
It is a FIFO structure - the first job to join the queue would be the first one to be printed.

[5](a)

A standard code for storing characters in a computer system stores the following characters in ascending binary order:

"0" 00110000

"1" 00110001

"2" 00110010

Write down the codes for:

(i)

"3"

[1]

00110011

(ii)

"9"

[1]

00111001

(b)

In a certain computer sign/magnitude representation is used to store positive and negative integers using 8 bits.

(i)

Explain what is meant by the term sign/magnitude representation.

[1]

the first bit of the number indicates whether the number is positive or negative (0 = positive; 1 = negative). The remaining bits give the size of the number.

(ii)

Demonstrate the use of the sign/magnitude representation using 8 bits, for the integers 5 and -5

[2]

5 = 00000101
-5 = 10000101

(c)

Explain the term overflow when used in connection with storing numbers in a computer.

[1]

If a number has too many bits for the storage space then an overflow has occurred.

(d)

Numbers are often stored in computers in floating point form.

(i)

State one benefit of storing numbers in floating point form.

[1]

a greater range of numbers is possible.

(ii)

State one problem associated with storing numbers in floating point form.

[1]

a loss of precision (accuracy) may result as some numbers cannot be represented exactly.

[6](a)

State two methods of describing algorithms.

[2]

flowchart
pseudocode

(b)

Quicksort is a recursive algorithm.

(i)

Explain the term recursive algorithm.

[2]

an algorithm that calls itself
there must be a terminating condition for the algorithm to resolve itself.

(ii)

Briefly outline how Quicksort operates.

[2]

Two pointers are placed at each end of a list of data. The pivot is the middle data item.
The left pointer is moved until a number greater than the pivot is found. The right pointer is moved left until a number less than the pivot is found. These two numbers are swapped.
The process continues until the pointers meet. The pivot number is now in the correct place.
The resulting two sub-lists are recursively sorted.

[7](a)

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

[1]

programming an embedded system such as a washing machine

(b)

Describe two features normally available in a fourth generation language (4GL).

[2]

generate a database query
output a report on the data

Describe the difference between a procedural programming language and a non-procedural programming language.

[2]

procedural - instructions are executed in a sequence, one after the other until the end of the program is reached.
non-procedural - a set of facts and rules are used to make deductions

(ii)

Give an example of a suitable use for each type of programming language: procedural and non-procedural.

[2]

procedural - a computer game
non-procedural - an artificial intelligence program that may be found in an expert system

(d)

Describe briefly what is meant by an object oriented approach to programming.

[1]

objects are defined which have properties and methods.

The email addresses of students at Clynnog College are made up of the surname plus three digits, followed by the @ sign, followed by clynnog.ac.uk

All letters used are in lower case. Assume all surnames consist of letters only, and can be of any length.

For instance, the email address for David Jones is jones034@clynnog.ac.uk

(i)

Produce a Backus Naur Form (BNF) definition for a Clynnog College student email address.

[4]

<letter> ::=a|b|c|d|e...x|y|z
<digit> ::= 0|1|2|3|4|5|6|7|8|9
<word> ::= <letter> | <letter> <word>
<name> ::= <word> <digit> <digit> <digit>
<email> ::= <name> @clynnog.ac.uk

(ii)

Produce a syntax diagram for a Clynnog College student email address.

[3]

The following incomplete algorithm is intended to perform a linear search for an item Search Value in an array Numbers[1..n] and output the position if the item if it is found.

The asterisks below indicate four lines which are incomplete.

1		input SearchValue
2	*	set FoundPosition :=
3		set CurrentPosition := 0
4			while ((FoundPosition = 0) and (CurrentPosition < n))
5	*			CurrentPosition :=
6	*			if
7					then FoundPosition := CurrentPosition
8				endif
9			endwhile
10	*	output

Copy and complete the four lines indicated by asterisks.

[4]

2) set FoundPosition := 0
5) CurrentPosition := CurrentPosition + 1
6) if Numbers[CurrentPosition] = SearchValue
10) output FoundPosition

[10]

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

A compiler is used when a computer program is translated into a form ready for execution by a computer. Describe in detail the main stages of compilation.

Once the program has been successfully compiled, a debugging program may be used with it. Describe in detail the various elements which may be available in a debugging program.

[8+3]

In Lexical Analysis, all comments and unnecessary spaces are removed, and the program is converted into numerical tokens.

During Syntax Analysis, the tokens are used to produce a Symbol Table of numerical values and a dictionary of variable names and string values. The tokens are checked that they obey the syntax rules of the language used and any error messages are output if they do not.

Semantic Analysis checks that all variables are properly declared and no incorrect operations are being used such as assigning real values to integer variables.

Code Generation converts the program into executable machine code and there may be some code optimisation to make the program smaller or run faster.

A debugging program may allow breakpoints to be placed in the program. The program is run, stops at the breakpoint and the programmer can then check the values of variables to see if they are as expected. Single-stepping will allow one line of code to be executed at a time. Traces will show the order in which the lines of the program are executed.