CP4 Computing June 2004

1(a)

The stack is a type of data structure.

(i)

Explain, using a diagram, the term stack.

[2]

a stack is a Last In First Out (LIFO) data structure.
a stack pointer shows the position of the data item at the top of the stack (data is added and removed from the Top of the stack):

8		Top of Stack = 4
7
6
5
4	Sally
3	Sarah
2	George
1	Tom

(ii)

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

[1]

An error message should be displayed -'Stack overflow'

(b)

The queue is another type of data structure.

Explain, using a diagram, the term queue.

[2]

a queue is a First In First Out (FIFO) data structure
two pointers show where the Front and the Back of the queue are (data is added to the back and removed from the front):

8		Front = 2 Back = 5
7
6
5	Ian
4	Sally
3	Sarah
2	George
1

2. (a)

A certain character set represents the character 'A' in binary as 01000001, 'B' as 01000010 'C' as 01000011 and so on.

What two characters does the bit pattern 01000111 01000010 represent?

[1]

(b) (i)

convert the 8 bit binary number 10100111 to hexadecimal

[1]

(ii)

Describe an advantage of representing numbers in hexadecimal rather than binary.

[1]

there are fewer digits involved so the numbers are easier to work with and errors are less likely to occur.

Computer systems often round or truncate numbers.

(i)

Explain each of the terms round and truncate.

[2]

round - if the decimal part of a number is 0.5 or greater then the integer part of the number is rounded up to the integer above. Otherwise it is left as the integer below.
truncate - the decimal part of a number is removed.

(ii)

Explain how rounding may cause a problem in a computer calculation.

[1]

if a number is rounded, it is replaced by an approximation of that number. This inaccurate effect may be compounded if many numbers are rounded in a calculation.

4. (a)

Draw and label a diagram to show the structure of a linked list.

[2]

(b)

In a certain implementation, a linked list of surnames is stored in an array as follows:

Address	Surname	Pointer
1	Smith
2	Peters
3	Zaman
4	Davies
5	Kwei
6
...

The list is required to be produced in alphabetical order.

A pointer value -1 indicates the end of the list.

(i)

The variable start points to the first item in the list. What is the value of start?

[1]

start = 4

(ii)

The variable next points to the next free space in the list. What is the value of next?

[1]

next = 6

(iii)

Copy the table and complete the pointer column.

[3]

Address	Surname	Pointer
1	Smith	3
2	Peters	1
3	Zaman	-1
4	Davies	5
5	Kwei	2
6
...

5. (a)

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

[2]

running queries to search for data
generating reports based on stored data

(b) (i)

When is a visual programming language particularly useful?

[1]

when writing an application for a GUI (Graphical User Interface)

(ii)

State a human computer interface (HCI) feature which could be produced very easily in a visual programming language.

[1]

'point and click' with a mouse pointer to select options.

(c)

Name a situation where a special purpose programming language would be useful.

[1]

when programming an embedded system in eg a robot

(d)

Computer aided software engineering (CASE) tools are often used during program development. Describe two features available in a CASE tool.

[2]

menu creator which allows easy set-up of menus and their options.
interface creator which allows the programmer to define how the interface will look.

(e)

Describe what is meant by a non-procedural programming language and describe an example of a suitable use for this type of programming language.

[2]

a language which consists of a set of facts and a set of rules for making deductions.
one use would be in developing artificial intelligence applications.

6. (a)

N is the 8 bit binary number 00010101

MASK is the 8 bit binary number 00000001

(i)

Carry out on the number N an arithmetic shift left by two places. Write down the answer.

Explain the effect of this operation on the number N

[2]

01010100
it multiplies the number by 4

(ii)

Carry out on the original number N a logical shift right by one place.

[1]

00001010

(iii)

Using the original value of N, carry out the logical operation N AND MASK.

[1]

00000001

(iv)

What effect does MASK have when an AND operation is carried out between MASK and any 8 bit binary number?

[1]

it changes all of the first 7 bits to 0

(b)

Numbers are often stored in floating point form. What does the term floating point mean?

[1]

a number is represented as a fraction (mantissa) multiplied by a power of 2 (exponent)

The email addresses of students at Glyder College are made up of one or more initials, followed by the student's surname, followed by the @ sign, followed by glyder.ac.uk

The initials are separated from each other and from the surname by full-stops. All the letters used are in lower case. Assume that all surname's consist of letters only, and can be of any length.

For instance, the email address of Sian M Evans is s.m.evans@glyder.ac.uk

(i)

Produce an appropriate Backus Naur Form (BNF) definition for a Glyder College student email name.

[4]

letter ::= a|b|c|d|e|f|....|w|x|y|z
initial ::= letter . | letter . initial
surname ::= letter | letter surname
email ::= initial surname @glyder.ac.uk

(ii)

The following incomplete diagram is intended to express the same information as the BNF definition.

(I)

What is the name of this type of diagram?

[1]

syntax diagram

(II)

Copy and complete the diagram.

[2]

8. (a)

Explain what is meant by the term algorithm.

[2]

a sequence of steps needed to perform a task.

(b)

Quicksort is a recursive sort algorithm

(i)

Explain why Quicksort is often used to sort items.

[1]

it is a fast method of sorting if the data items are very jumbled.

(ii)

Explain the term recursive.

[2]

a recursive algorithm calls itself repeatedly
...until a terminating condition is met.

(iii)

Briefly outline how Quicksort operates.

[2]

a pivot number is selected in the middle of the list, with two pointers set at the start and the end of the list
the start pointer is moved up the list until a number is found greater than the pivot, and the end pointer is moved down until a number is found less than the pivot. These two numbers are swapped. This is repeated until the pointers meet.
After the pass, the pivot number should be in the correct place and defines two smaller lists which now need sorting....

9. (a)

What is the purpose of a compiler?

[2]

it converts a high level language program into executable machine code.

(b)

Describe the lexical analysis stage of compilation.

[2]

the program is analysed and tables are created for the numbers, strings, labels it contains.
from these tables a symbol table is created. The program has been converted into a set of numbers.

(c)

In another stage of compilation, checks are made that real values are not being assigned to integer variables and that there is no illegal mixed-mode arithmetic. What is the name of this stage?

[1]

syntax analysis

(d)

Describe the function of a linking loader.

it loads previously compiled code into the program and provides links to run it at the appropriate places.

10.

The following incomplete algorithm is intended to find the maximum mark and mean mark of a set of examination marks.

In the algorithm, the asterisks indicate lines which are incomplete.

1		set MaxMark = 0
2		set Count = 0
3	*	set
4		repeat
5		read NextMark
6	*	set Total =
7	*	set Count =
8		if NextMark > MaxMark
9	*	then
10		until end of data
11		set MeanMark = Total / Count
12		output MeanMark
13	*	output

Copy and complete the five lines indicated by asterisks

[5]

1		set MaxMark = 0
2		set Count = 0
3	*	set Total = 0
4		repeat
5		read NextMark
6	*	set Total = Total + NextMark
7	*	set Count = Count + 1
8		if NextMark > MaxMark
9	*	then MaxMark = NextMark
10		until end of data
11		set MeanMark = Total / Count
12		output MeanMark
13	*	output MaxMark

11.

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

The human computer interface (HCI) is a very important part of any computer system.

Various types of HCI are in use, including text-based, graphical user interface (GUI), handwriting recognition and speech recognition. It is particularly important that the HCI takes into account the needs of different types of user, and that the design of the HCI should be evaluated.

Describe in detail the issues facing the designer of an HCI, with reference to the terms shown in green above.

[9+3]

The designer of an HCI must take into consideration the IT skills of the user. An expert user may be capable of using a text-based interface where commands are typed in. This type of interface allows a greater choice of options. A less-skilled user such as a child may find it easier to use a GUI where the options are selected by clicking on icons representing the applications.

Handwriting recognition interfaces may be more appropriate for small palm-top computers where keyboards would be too large. The user would use a special pen to write on a sensitive pad.

Speech recognition may be a better option for situations where the user does not have their hands free - for example a surgeon or a fighter pilot.

The designer will also need to consider the resources available as GUIs will take up more storage space in memory than text-based interfaces.

It is important that the design of the HCI is properly evaluated to make sure it is suitable for the applications needed and for the IT skills of the users. This will involve checking that the design is easy to learn for the user and easy to remember. It should also be a pleasure to use which will motivate the user, and should be free from errors.