CP4 Computing June 2007

[1]

When developing a new computer system, programmers sometimes use a software package rather than a traditional programming language.

(i)

Describe two possible benefits of this package-based approach compared with the use of a programming language.

[2]

many facilities already available so they won't need to be programmed (Eg sorting of data)
resulting software will be more compatible with other programs (Eg. possible to copy and paste data between programs)

(ii)

Describe one possible drawback of this package-based approach compared with the use of a programming language.

[1]

less versatile - complicated routines may be difficult to program.

[2](i)

Explain, using a diagram, the term stack as used in a computer system.

[2]

Your diagram must show a top-of-stack pointer
Last-in-first-out data structure.

(ii)

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

[1]

an error message ('Stack full') should be output.

(iii)

Describe a computer application which would normally use a stack.
Why is a stack appropriate in this case?

[2]

subroutine return addresses should be placed on a stack.
the last address placed on the stack will be the first one removed.

[3](a)

Handwriting recognition is increasingly used as a form of human computer interface (HCI).

(i)

Describe two possible benefits of this type of HCI compared with keyboard input.

[2]

no bulky hardware needed (Eg. keyboard)
can be used on small portable devices

(ii)

Describe two possible drawbacks of this type of HCI compared with keyboard input.

[2]

it may not be able to be used by somebody with bad handwriting
there may be inaccuracies as some letters are similar (l and I)

(b)

Describe how the design of an HCI should be evaluated.

[1]

check that it fulfils the specifications of the original design.

[4](a)

What term is used to describe a group of related data items?

[1]

a record

(b)

The following binary tree has been produced by inserting the names.
Lisa, Osian, Nicola, Javed, David, Fu and Paula, in that order.

In each case, the right pointer indicates the condition: later on in the alphabet

(i)

Write down the name contained in the root node.

[1]

Lisa

(ii)

Write down the order in which the nodes would be accessed to reach the name Nicola.

[1]

Lisa - Osian - Nicola

(iii)

The name Ed is not in the above diagram. Explain the steps that would take place if a search was made for this name.

[1]

The search would start at the root node (Lisa). The nodes accessed would be Javed - David - Fu. A terminal node has been reached without finding Ed so an error message "Record not found" would be output.

(iv)

Copy the diagram then add the name Carys in the correct place on the diagram.
(You may use just the initial letter of all names if you wish).

[1]

(v)

This tree diagram is reasonably well balanced in shape. What would happen to access times if the tree was much less well balanced?

[1]

Access time would increase so search times would on average be slow.

[5](a)

Using eight bits and two's complement form, convert the number -9₁₀ to binary.

[1]

11110111

(b)

Computer systems often truncate numbers. Explain the term truncate giving an example.

[2]

The decimal part of a number is removed.
Eg Truncate 5.75 and get 5

(c)

In many computers, characters are stored using a standard code.

(i)

In one standard code, the character "4" is stored as 0110100. The character "5" is stored as the next higher binary code (0110101) and so on. How will the character "8" be stored?

[1]

0111000

(ii)

What is the advantage of using a standard code of this type?

[1]

computers can exchange data if there is consistency in character representation.

(d)

Write down the effect of carrying out an arithmetic shift left by three places on the positive integer 00001010

[1]

01010000

Explain the effect of this operation on the number.

[1]

it multiples the number by 8

[6](a)

Explain what is meant by the term algorithm.

[2]

a sequence of steps used to complete a task

(b)(i)

Describe two features of a recursive algorithm.

[2]

the algorithm 'calls' itself
there is a terminating condition

(ii)

Describe one advantage of a recursive algorithm.

[1]

simpler algorithms for some complex tasks

(iii)

Give one example of a recursive algorithm.

[1]

Quicksort method of sorting data

[7](a)

Write down the truth table for:

(i)

the AND operation

[2]

AND	0	1
0	0	0
1	0	1

(ii)

the EXCLUSIVE OR (XOR) operation.

[2]

XOR	0	1
0	0	1
1	1	0

(b)(i)

Carry out the XOR operation on the following:

A = 10001101

K = 10101111

[2]

00100010

(ii)

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

[1]

The result is the number A (10001101)

(iii)

State a security application which this operation might be used for.

[1]

data encryption - coding the data (A) with the key(K), and decoding it.

[8](a)(i)

Describe the difference between a compiler and an interpreter.

[2]

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

(ii)

Describe the lexical analysis stage of compilation, ensuring you make the output of this stage clear.

[2]

comments and unnecessary spacing are removed from the program
input stream of characters is broken into tokens Eg. the five characters P, R, I, N, T would be converted into a single token
some simple error checking done
the output is an ordered sequence of tokens

(iii)

Describe the semantic analysis stage of compilation.

[2]

checks that all variables are declared
checks that data is of the correct type
checks that data used in operations are of the correct type Eg. no real numbers are multiplied by strings.

(b)

Explain the term relocatable code.

[1]

program code that can run properly wherever in memory it is stored

(c)

A debugging tool contains a program trace facility and a store dump facility.
Explain each of the two terms:

(i)

a program trace facility

[1]

allows the program to be run through one instruction at a time

(ii)

a store dump facility.

[1]

a printout of the contents of memory store locations and values of data variables.

[9] (a)

What is the purpose of Backus Naur Form (BNF)?

[1]

to define the syntax rules of a high level language

(b)

One way of defining a decimal number is:

no sign or a plus sign or a minus sign
followed by
one or more digits
followed by
a decimal point
followed by
one or more digits

For instance, the following are covered by this definition:

+23.5 23.5 -0.5 0.0 +0.728

Produce an appropriate BNF definition for a decimal number as defined above.

[4]

<digit> ::= 0|1|2|3|4|5|6|7|8|9
<integer> ::= <digit> | <digit><integer>
<signed integer> ::= +<integer> | <integer> | -<integer>
<decimal> ::= <signed integer> . <integer>

[10]

Marks obtained by candidates in an examination are terminated with a rogue value of -99.

An example of a set of examination marks (including the rogue value) is shown below,

62 71 48 35 76 61 54 38 52 -99

For this particular examination:

candidates scoring 70 or more marks are given a Distinction grade.
candidates scoring 40 to 69 marks (inclusive) are given a Pass grade
candidates scoring fewer than 40 marks are given a Fail grade

Design an algorithm which will read in a set of marks of this type and will output the number of candidates being given each of the three grades.

[4]

DistinctionCounter=0
PassCounter=0
FailCounter=0
repeat
    input(ExamMark)
    if (ExamMark <> -99) then
        if (ExamMark >= 70) then DistinctionCounter = DistinctionCounter+1
        if (ExamMark >=40) and (ExamMark <= 69) then
                 PassCounter = PassCounter + 1
        if (ExamMark < 40) then FailCounter = FailCounter + 1
    end if
until (ExamMark = -99)
output(DistinctionCounter)
output(PassCounter)
output(FailCounter)

[11]

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

A programmer is developing a set of programs and needs to make a number of decisions.

One decision relates to the human computer interface (HCI), and whether this should:

be a graphical user interface
be a text-based interface
use speech recognition
use speech synthesis

Another decision is the type of programming language to be used, for instance whether to use:

a visual programming language
a fourth generation language
an object oriented language

Describe in detail the features of the different HCI types in the first list which might influence the choice of HCI type.

Also describe in detail the features of the different programming languages in the second list which might influence the choice of language.

[9+3]

A graphical user interface (GUI) would use icons to represent applications which would be selected by clicking a mouse pointer on them. This would be an instinctive, easy to use interface suitable for users with low IT skills. This type of interface would however use a lot of computer resource such as memory.

A text-based interface would use less memory and operate faster, but would only be suitable for expert users as the commands need to be learned.

Speech recognition systems are useful for situations where the user is either handicapped or unable to use their hands such as a fighter pilot or surgeon. There may be problems with recognising some people's voices due to regional accents or voice problems such as heavy colds.

Speech synthesis allows the user to continue with their task such as driving a car, without needing to look at a monitor screen, and it is also useful for those with a visual handicap.

Visual programming languages allow programmers to create programs quickly without much coding. Useful for developing applications in a WIMP environment.

Fourth generation languages have many powerful built-in features such as searching and sorting so program coding is less burdensome.

Object oriented languages use objects that have properties and methods. Each object reacts to certain events (such as clicking the mouse) according to subroutines (event handlers) written by the programmer. These are useful for event-driven programs.