CP4 Computing June 2009

[1]

Companies often use software packages to solve a problem rather than asking their programmers to develop new programs. Describe three benefits of this approach.

[3]

faster development of a solution. It is faster to buy a software package than wait for programmers to write software.
it will generally be less expensive to buy a software package.
there should be greater compatibility between software packages that would allow, for example, exchange of data between them.

[2]

A certain computer character code represents alphabetical characters in ascending binary order. For instance, the character "E" is represented by 01110101, "F" by 01110110, etc.

Write down the code for:

(a)

"G"

[1]

01110111

(b)

"D"

[1]

01110100

[3]

Stacks and linked lists are two types of data structure.

(a)

Explain what is meant by the term data structure and explain why data structures are useful in computing.

[2]

an organised collection of related data
algorithms can be used to efficiently process the data in a data structure

(b)

Name a computer application where a stack is the most appropriate data structure and explain why it is the most appropriate data structure in this case.

[2]

when a program is run, return addresses for subroutines are placed on a stack.
the last address placed on the stack is the first one needed to return to (a stack is a Last-In-First-Out data structure)

(c)(i)

Explain what is meant by the term linked list.

[2]

an ordered sequence of records where each record in a linked list consists of the data and a pointer to the next record in the list.
there is also a start pointer to tell the computer which is the first record in the linked list. The final record has a null pointer.

(ii)

In a certain implementation, a linked list of names is actually stored in a table form as shown below. The names are to be accessed in ascending alphabetical order. A variable points to the first name in the alphabet, Bennett.

Address	Name	Pointer
501	Goldstein
502	Tomkins
503	Huang
504	Bennett
505	Kareem
506	Davies
....	....	....

Copy the table and complete the pointer column.

[3]

Address	Name	Pointer
501	Goldstein	503
502	Tomkins	0
503	Huang	505
504	Bennett	506
505	Kareem	502
506	Davies	501
....	....	....

[4](i)

Convert the eight-digit binary number 00011110 to

(a)

hexadecimal

[1]

(b)

denary (decimal)

[1]

(ii)(a)

Show how the number -5₁₀ is represented in two's complement form using 8 bits.

[1]

11111011

(b)

Showing your working, demonstrate that 9₁₀ is the result of the binary addition of -5₁₀ and 14₁₀.

[2]

-5 = 11111011
14 = 00001110
---------
(1)00001001 = 9

[5](a)

Explain what is meant by the term algorithm.

[2]

a sequence of instructions needed to complete a task
the steps must be completed in a defined order

(b)

A recursive algorithm must have a terminating condition.

(i)

What other feature does a recursive algorithm need to have?

[1]

the algorithm must call itself

(ii)

Describe one benefit of using a recursive algorithm.

[1]

simplified and smaller programming code needed

(iii)

Name one example of a recursive algorithm.

[1]

Quicksort - to sort data into order

[6]

P is the eight-digit binary number 11011011

Q is the eight-digit binary number 01110101

(a)

Two logical operations that can be carried out on a pair of binary numbers are OR and XOR.

One of these logical operations has been carried out on P and Q giving the result 10101110. Which logical operation has been carried out in this case?

[1]

(b)

Write down the eight-digit binary number which results from carrying out the logical operation NOT Q.

[1]

10001010

(c)

Write down the eight-digit binary number which results from carrying out an arithmetic shift right by one place on Q.

[1]

00111010

(d)

M is the eight-digit binary number 00000001

M is used for masking.

(i)

State what logical operation is used during masking.

[1]

(ii)

What effect will masking with M have on any eight-digit binary number?

[1]

The first 7 bits will become 0, the eighth bit will remain unchanged.

[7]

The following incomplete algorithm is intended to perform a sort on the n elements of the array Customer.

The asterisks below indicate four lines which are incomplete.

1		repeat
2	*		set Swap :=
3	*		for Count := 1 to
4				if Customer[Count] > Customer[Count+1] then
5					Temp := Customer[Count]
6	*				Customer[Count] :=
7	*				Customer[Count+1] :=
8					Swap := TRUE
9				endif
10			endfor
11		until Swap = FALSE

Copy and complete the four lines indicated by asterisks.

[4]

set Swap := FALSE
for Count := 1 to n-1
Customer[Count] := Customer[Count+1]
Customer[Count+1] := Temp

[8](a)(i)

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

[1]

defines the syntax of a programming language

(ii)

Why is a natural language (such as English or Welsh) not suitable for this purpose?

[1]

ambiguous - some words have several different meanings

(b)

In a certain programming language a variable name is made up of letters (which can be upper case or lower case) and digits. The first character must be an upper case letter. The name may be of any length.

For instance, the following are permitted as variable names in this language:

T Total TOTAL TotalValue3 Value2009 XYZ

Produce a BNF definition for a variable name in this language.

[4]

<UpperCase> ::= A|B|C|D...|X|Y|Z
<LowerCase> ::= a|b|c|d...|x|y|z
<Digit> ::= 0|1|2|3|...|8|9
<Character> ::= <UpperCase> | <LowerCase> | <Digit>
<Word> ::= <Character> | <Character><Word>
<Variable> ::= <UpperCase><Word>

(c)

Name a type of diagram which could have been used instead to show the definition of a variable in this language. (There is no need to draw the diagram)

[1]

syntax diagram

[9](a)

Many computer programs pass variables to a procedure.

(i)

What is the name for the variable passed in this way?

[1]

parameter

(ii)

During this operation, data is sometimes passed by reference. Variables can be passed by another method. Name the other method and explain how it operates. Explain one advantage of this method over passing by reference.

[3]

by value
a copy of the value of the parameter is used by the procedure
the original value of the parameter is not changed by the procedure

(b)(i)

Describe what is meant by a local variable in a computer program.

[1]

only usable in the procedure where it is defined

(ii)

Describe what is meant by a global variable in a computer program.

[1]

usable anywhere in the program

(iii)

Describe one benefit of using global rather than local variables.

[1]

the same data can be used in a number of different procedures

[10]

There are many different types of programming language.

(a)

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

[2]

the language has a number of facts and rules defined
artificial intelligence programs

(b)

Describe circumstances under which a visual programming language will be particularly useful and give an example of a human computer interface (HCI) feature which could be produced easily in this type of language.

[2]

useful for developing applications that run in a GUI (Windows) environment
a drop-down menu

(c)

Describe what is meant by an application generator.

[1]

a program that creates code for an application from a set of pre-defined options.

[11](a)

A compiler is often used to translate a source program to make it ready for execution. One stage of compilation is syntax analysis. Explain what happens during the syntax analysis stage.

[2]

the source program is converted into a Symbol table of numerical tokens
the tokens are checked to make sure they obey the syntax rules of the language

(b)

In other cases, an interpreter is used instead of a compiler. Briefly explain how an interpreter works.

[1]

each line of a program is converted in turn into executable machine code and executed.

(c)

A debugging tool is often used while developing a computer program. Facilities available in the debugging tool may include:

program trace
break point
store dump

Explain each of these facilities.

[3]

program trace - allows the program to be run through one line at a time. The programmer can check the order in which the lines are executed.
break point - a point in a program where execution can be stopped. The programmer can then check the values of variables at that point.
store dump - values of memory store locations can be output, as well as values of stored variables.

[12]

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

When a new computer system is being developed, considerable care is taken over the design of the human computer interface (HCI). Modern HCIs often make use of speech recognition, handwriting recognition and speech synthesis.

Describe in detail the features of the three types of HCI named above, including their suitability for novice and handicapped users.

[9+3]

Speech recognition interfaces use microphone input. The user speaks an instruction, and the computer matches the sound pattern to a database of stored patterns and executes the instruction with the closest match.
Faster input than typing, but may be affected by background noise.
Useful for handicapped users who are unable to use hands to type at keyboards or use other types of input device.
Novice users will need to know what commands the computer will recognise, but they do not need typing skills.
Handwriting recognition interfaces match user writing to stored patterns of characters. The user will write on a screen using a stylus. Useful on small devices that cannot have keyboards. May not be accurate if writing quality is poor.
Not really suitable for some handicapped users as they need to write instructions.
Novice users may find it faster to write if they are not used to using keyboards.
Speech synthesis interfaces use speakers or headphones to produce spoken output. Useful in situations where the user's hands are occupied, such as pilots, drivers, surgeons etc. They would be able to interact with the computer without stopping what they are doing with their hands.
Visually handicapped users will find speech synthesis interfaces useful as they would be unable to see output on monitors.