CP4 Computing June 2005

A company's sales department uses a computer system to store information about its sales staff.

(a)

Give an example of sales staff data which would be best stored in the form of a record, explaining why a record is the most suitable data structure in this case.

[2]

Staff ID, Staff name, Date staff joined company, total number of sales...
There are different data types here (string, number, date etc) so a record is the most suitable data structure..

(b)

Using a diagram, give an example of sales staff data which would be best stored in the form of a three dimensional array.

[2]

Salesman ID	Sales Mon	Sales Tues	Sales Wed	Sales Thu	Sales Fri
SmithG02	23	12	9	11	4
ThomasP01	31	6	3	9	11
DaviesM04	12	4	15	7	8

The sales figures for each salesman, for each day of a particular week would be a two-dimensional array.
The same data for a number of different weeks would be stored in a three-dimensional array.

2. (a)

A graphical user interface and a text based interface are two different types of Human-Computer Interface (HCI)

(i) Describe three benefits of a graphical user interface over a text based interface.

[3]

More intuitive so it can be used by people with low IT skills.
It is easier to understand what the icons mean, so it is easier to learn to use the software.
There is no need to learn difficult commands.

(ii) Describe two benefits of a text based interface over a graphical user interface.

[1]

The speed of the running of the software is faster.
More complex commands can be typed in with a number of switches (options) available.

(b)

Hand held computer devices often use handwriting recognition as a means of input.

(i) Describe one feature which makes this form of input very suitable for hand held computers.

[1]

No peripherals (such as a keyboard or a mouse) need be attached to the palmtop.

(ii) Describe one drawback of this form of input.

[1]

Accuracy of input is not guaranteed if handwriting is poor.

(c)

Two other examples of HCI are forms dialogue and natural language interface. Briefly explain each of the terms:

(i) forms dialogue

[1]

A form with a number of input boxes or selection boxes needs to be filled in by the user.

(ii) natural language interface

[1]

Instructions to the computer are entered as the user would speak them to a computer.

(d)

Describe how an HCI can be evaluated.

[1]

The user would be asked to say whether the interface was easy to use and learn and did it perform the tasks correctly.

Explain the following terms when used in connection with storing numbers in a computer.

(a)

Overflow

[1]

The number is too large to be accurately stored in the space available.

(b)

Underflow

[1]

The number is too small to be stored accurately in the space available.

4. (a)

The following diagram shows a type of data structure. It contains a number of integers. In each case the right pointer indicates the condition 'higher number' and the left pointer indicates the condition 'lower or equal number'.

(i)

Write down the name of this data structure.

[1]

Binary tree

(ii)

Write down the integer contained in the root node.

[1]

2617

(iii)

Write down the order in which the nodes would be accessed to find the integer 2528.

[1]

2617 - 2456 - 2537 - 2528

(iv)

Copy the tree and show where a new node, containing the integer 3106 would be added.

[1]

(New node 3106 down and left from 3210)

(v)

The integer 2550 is not in the diagram. Explain what would happen if a search was made for this integer.

[1]

The search would access a terminal node without finding the node 2550, so an error message would be output.

(b)

Write down the names of two other data structures. In each case draw a simple diagram to illustrate the data structure.

[4]

Stack (A Last In First Out structure)

Node No.	Data
6
5
4	2108
3	3210
2	2456
1	2617
Top of Stack = 4

Queue (A First In First Out structure)

Node No.	Data
6
5
4	2108
3	3210
2	2456
1
End of Queue = 4 Front of Queue = 2

5. (a)

In a certain computer, two's complement is used to represent negative integers, using 8 bits.

(i) Show how the number -7₁₀is represented.

[1]

11111001

(ii) Showing your working, demonstrate that 13₁₀is the result of the binary addition of -7₁₀to+20_10.

[2]

-7   =     11111001
+20 =     00010100
-------------------
         (1)00001101 = 13 (using 8 bits)

(b)

In another computer, a sign/magnitude approach is used to represent integers using 8 bits. Explain what is meant by the term sign/magnitude, giving a clearly labelled example.

[2]

The first bit (most significant bit) is a sign bit, that shows whether the number is positive (0) or negative (1). The remaining 7 bits represent the size of the number.
Eg -13 would be represented as 10001101 (the blue bit is the sign bit)

(c)

In another computer, the character '1' is stored as 00110001. The character '2' is stored as the next higher binary code (00110010) and so on. How will the character '5' be stored?

[1]

00110101

6. (a)

State two methods of describing algorithms.

[2]

Flowcharts
Pseudocode.

(b)

(i) A recursive algorithm is an algorithm which calls itself. Describe one other key feature of a recursive algorithm.

[1]

There must be a terminating condition so that the recursion resolves itself and ends. Without this condition the recursion would go on for ever.

(ii) Describe one advantage of a recursive algorithm

[1]

Simpler and shorter program code.

(c)

A certain computer program has one main section, and may have a number of procedures. Data used in the main section is often also required and can be passed via a parameter. Parameters can be passed by reference or by value.

(i) Describe what is meant by the term passing by reference and give one benefit of using this method.

[2]

The address of the variable is passed to the procedure.
The variable may be accessed by the procedure and its value may be changed if necessary.

(ii) Describe what is meant by the term passing by value and give one benefit of using this method.

[2]

The value of a variable is passed to the procedure.
The value of a variable may be used but not changed.

7. (a)

J is eight-digit binary number 10011010

K is eight-digit binary number 00111000

(i) Write down the effect of carrying out the logical operation NOT J

[1]

01100101

(ii) Write down the effect of carrying out the logical operation J XOR K

[1]

10100010

(b)

M is the eight-digit binary number number 10000000

M is used in a masking process.

(i) State what logical operation is used during masking.

[1]

(ii) What effect would masking with M have on any eight-digit binary number?

[1]

The first bit of the number would remain unchanged, but all other bits would be changed to 0.

8. (a)

Explain what is meant by the term interpreter.

[1]

A program which translates a high level language program into machine code one instruction at a time, executing each instruction as it does so.

(b)

Lexical analysis is one process involved in compiling a computer program, and an output from this process is a symbol table. Describe what happens during lexical analysis, making clear the role of the symbol table.

[2]

Tables of numbers, text messages, identifiers are created.
Together with a table of the instructions the program is converted into a symbol table of pairs of numbers.

(c)

Explain what is meant by the term linking loader. Give an example of a situation where a linking loader would be used.

[2]

A linking loader is a program that loads in separately compiled segments of code into the appropriate place in a program, and sets up the appropriate links to other subroutines.
Pre-defined and compiled code could be inserted from a library of subroutines.

9. (a)

In a certain computer language, variable names are defined according to the following diagram.

(i) What is name of this type of diagram?

[1]

Syntax diagram

(ii) Give a four character example of a variable name permitted in this language.

[1]

DOG3

(b)

(i) Backus Naur Form (BNF) is often used to describe the syntax of a computer language. Give one reason why BNF might be used in preference to English.

[1]

The definitions are clearer, more concise and easier to understand.

(ii) A definition of a word is necessary for a spell checker within a word processor.

The definition used is as follows:

A word contains one or more characters and must:

begin with a letter
be made up of letters, hyphens (-) and apostrophes (') only

You may assume that all letters have already been converted, if necessary, to lower case.

Produce an appropriate BNF definition for a word.

[4]

letter ::= a|b|c|d|e......|x|y|z
symbol ::= - | '
char ::= <letter> | <symbol>
chain ::= <char> | <char> <chain>
word ::= <letter> | <letter> <chain>

10.

An array Values[1..n] contains a number of integer values. The array elements are not necessarily in ascending or descending order.

Design an algorithm (in pseudo-code or a high-level programming language) which will carry out a linear search of the array for a given search element. If the element is found, it should output the position of the search element. If the element is not found, the algorithm should output zero.

[4]

pos = 1
found = 0
repeat
if Values[pos] = SearchElement then found = pos
pos = pos + 1
until pos = n + 1
output(found)

11.

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

A programming team is attempting to produce a very high quality suite of programs, which are to be used in connection with a safety-critical application in a chemical plant.

Various devices have to be made by the team, including the type of language to be used, for instance whether the language will be :

a procedural language
a non-procedural language
a fourth generation language
a visual programming language

The team has a number of software tools available, for instance

CASE tools
debugging tools

Describe in detail the features of the different programming language types in the above list and explain how they might influence the choice of language.

Also describe in detail the role of the two named software tools in assisting the programming team.

[8+3]

A procedural language program has a sequence of instructions to follow when the program is run. A non-procedural language has a set of facts and a set of rules which allow other facts to be deduced - generally used for artificial intelligence programs.

A fourth generation language is often associated with databases and will allow data to be searched and sorted and reports to be produced.

A visual programming language allows GUI applications to be quickly developed using objects and event-driven programming.

CASE tools provide some utilities, such as menu creators, flow chart graphics programs, and planners which will shorten the length of time needed to design and code the finished program.

Debugging tools such as traces or breakpoints are used to detect and remove any errors that occur when the program is run.