Data: Its Representation, Structure and
1.4.1 Number Systems
Counting is one of the first skills that a young child masters, and none of us consider
counting from 1 to 100 difficult. However, to count, we have to learn, by heart, the
meanings of the symbols 0,1,2…9 and also to understand that two identical symbols mean
totally different things according to their ‘place’ in the number. For instance, in 23 the 2
actually means 2 * 10. But why multiply by 10? Why not multiply by 6? The answer is
simply that we were taught to do that because we have 10 fingers, so we can count on our
fingers until we get to the last one, which we remember in the next column and then start
We don’t need to count in tens. The ancient Babylonians counted in a system, which is
similar to counting in sixties. This is very difficult to learn because of all the symbols
needed, but we still use a system based on sixties today: 60 minutes = 1 hour; 60 seconds
= 1 minute; 6 * 60 degrees = 1 revolution.
Instead of increasing the number of symbols in a system, which makes the system more
difficult, it seems reasonable that if we decrease the number of symbols the system will be
easier to use.
A computer is an electronic machine. Electricity can be either on or off. If electricity is not
flowing through a wire that can stand for 0. If electricity is flowing, then it stands for 1. The
difficulty is what to do for the number 2. We can’t just pump through twice as much
electricity, what we need is a carry system, just like what happens when we run out of
fingers. What we need is another wire.
The ‘units’ wire no electricity 0
The ‘twos’ wire no electricity 0
no electricity 0
no electricity 0
Carry electricity 1
no electricity 0
no electricity 0 =4
Carry electricity 1
The computer can continue like this for ever, just adding more wires when it gets bigger
This system, where there are only two digits, 0 and 1, is known as the binary system. Each
wire, or digit, is known as a binary digit. This name is normally shortened to BIT. So each
digit, 0 or 1, is one bit. A single bit has very few uses so they are grouped together. A
group of bits is called a BYTE. Usually a byte has 8 bits in it. In section 4 of this chapter we
will see that bytes can be of different sizes, but for now we will say that there are 8 bits in
The first thing we must be able to do with the binary system is to change numbers from
our system of 10 numbers (the denary system) into binary, and back again. There are a
number of methods for doing this, the simplest being to use the sort of column diagrams,
which were used in primary school to do simple arithmetic
Thousands Hundreds Tens Units
except, this time we are using binary, so the column headings go up in twos instead of tens
32s 16s 8s 4s 2s units
To turn a denary number into a binary number simply put the column headings, start at the
left hand side and follow the steps:
If the column heading is less than the number, put a 1 in the column and then subtract the
column heading from the number. Then start again with the next column on the right.
If the column heading is greater than the number, put a 0 in the column and start again
with the next column on the right.
Note: You will be expected to be able to do this with numbers up to 255, because that is
the biggest number that can be stored in one byte of eight bits.
e.g. Change 117 (in denary) into a binary number.
Answer: Always use the column headings for a byte (8 bits)
128 64 32 16 8 4 2 1
Follow the algorithm.
128 is greater than 117 so put a 0 and repeat.
128 64 32 16 8 4 2 1
64 is less than 117 so put a 1.
128 64 32 16 8 4 2 1
Take 64 from 117 = 53, and repeat.
32 is less than 53, so put a 1.
128 64 32 16 8 4 2 1
0 1 1
Take 32 from 53 = 21, and repeat.
If you continue this the result (try it) is
128 64 32 16 8 4 2 1
0 1 1 1 0 1 0 1
So 117 (in denary) = 01110101 (in binary).
To turn a binary number into denary, simply put the column headings above the binary
number and add up all the columns with a 1 in them.
e.g. Change 10110110 into denary.
128 64 32 16 8 4 2 1
1 0 1 1 0 1 1 0
So 10110110 = 128 + 32 + 16 + 4 + 2 = 182 (in denary).
This principle can be used for any number system, even the Babylonians’ sixties if you can
learn the symbols.
e.g. If we count in eights (called the OCTAL system) the column headings go up in 8’s.
512 64 8 1
So 117 (in denary) is 1 lot of 64, leaving another 53.
53 is 6 lots of 8 with 5 left over. Fitting this in the columns gives
512 64 8 1
0 1 6 5
So 117 in denary is 165 in octal.
Why bother with octal?
Octal and binary are related. If we take the three digits of the octal number 165 and turn
each one into binary using three bits each we get
1 = 001 6 = 110 5 = 101
Put them together and we get 001110101 which is the binary value of 117 which we got
The value of this relationship is not important now, but it is the reason why octal is in the
Another system is called HEXADECIMAL (counting in 16’s). This sounds awful, but just use
the same principles.
256 16 1
So 117 (in denary) is 7 lots of 16 (112) plus an extra 5. Fitting this in the columns gives
256 16 1
0 7 5
Notice that 7 in binary is 0111 and that 5 is 0101, put them together and we get 01110101
which is the binary value of 117 again. So binary, octal and hexadecimal are all related in
There is a problem with counting in 16’s instead of the other systems. We need symbols
going further than 0 to 9 (only 10 symbols and we need 16!).
We could invent 6 more symbols but we would have to learn them, so we use 6 that we
already know, the letters A to F. In hexadecimal A stands for 10, B stands for 11 and so on
to F stands for 15.
So a hexadecimal number BD stands for 11 lots of 16 and 13 units
= 176 + 13
= 189 ( in denary)
Note: B = 11, which in binary = 1011
D = 13, which in binary = 1101
Put them together to get 10111101 = the binary value of 189.
Binary Coded Decimal
Some numbers are not proper numbers because they don’t behave like numbers. A
barcode for chocolate looks like a number, and a barcode for sponge cake looks like a
number, but if the barcodes are added together the result is not the barcode for chocolate
cake. The arithmetic does not give a sensible answer. Values like this that look like
numbers but do not behave like them are often stored in binary coded decimal (BCD).
Each digit is simply changed into a four bit binary number which are then placed after one
another in order.
e.g. 398602 in BCD
Answer: 3 = 0011 9 = 1001
8 = 1000 6 = 0110
0 = 0000 2 = 0010
So 398602 = 001110011000011000000010 (in BCD)
Note: All the zeros are essential otherwise you can’t read it back.
1.4.2 Negative Integers
If a computer system uses a byte to store a number in the way that was suggested in 1.4.1
there are three problems that arise. The first is that the biggest number that can be
represented is 255 because there aren’t enough bits to store bigger numbers. This is easily
solved by using more than one byte to represent a number. Most computer systems use
either two or four bytes to store a number. There is still a limit on the size that can be
represented, but it is now much larger. The second problem is not so easy to solve, how to
represent fractions. This will be looked at later in this chapter. The third problem is how to
store negative numbers.
The example we used for binary storage was 117 which becomes 01110101 in binary. If
we want to store +117 or –117, these numbers need a second piece of data to be stored,
namely the sign. There are two simple ways to store negative numbers.
Sign and Magnitude.
Use the first bit in the byte (the most significant bit (MSB)) to represent the sign (0 for +
and 1 for -) instead of representing 128. This means that
+117 = 01110101 and -117 = 11110101
Notes: The range of numbers possible is now –127 to +127.
The byte does not represent just a number but also a sign, this makes arithmetic difficult.
The MSB stays as a number, but is made negative. This means that the column headings
-128 64 32 16 8 4 2 1
+117 does not need to use the MSB, so it stays as 01110101.
-117 = -128 + 11
= -128 + (8 + 2 + 1) fitting this in the columns gives 10001011
Two’s complement seems to make everything more complicated for little reason at the
moment, but later it becomes essential for making the arithmetic easier.
1.4.3 Binary Arithmetic
The syllabus requires the addition of two binary integers, and the ability to take one away
from another. The numbers and the answers will be limited to one byte.
There are four simple rules 0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
and the difficult one 1 + 1 = 0 (Carry 1)
e.g. Add together the binary equivalents of 91 and 18
Answer: 91 = 0 1 0 1 1 0 1 1
18 = 0 0 0 1 0 0 1 0 +
0 1 1 0 1 1 0 1 = 109
This is where two’s complement is useful. To take one number away from another, simply
write the number to be subtracted as a two’s complement negative number and then add
e.g. Work out 91 – 18 using their binary equivalents.
Answer: 91 = 01011011
-18 as a two’s complement number is –128 + 110
= -128 +(+64 +32 +8 +4 +2)
Now add them 0 1 0 1 1 0 1 1
1 1 1 0 1 1 1 0 +
1 0 1 0 0 1 0 0 1
1 1 1 1 1 1 1
But the answer can only be 8 bits, so cross out the 9th bit giving
01001001 = 64 + 8 + 1 = 73.
Notes: Lots of carrying here makes the sum more difficult, but the same rules are used.
One rule is extended slightly because of the carries, 1+1+1 = 1 (carry 1)
Things can get harder but this is as far as the syllabus goes.
1.4.4 Character Sets.
There are other types of data that have to be stored in computers besides numbers, for
instance, the letters of the alphabet. These are stored as codes which look like binary
numbers. For instance A could be stored as 000, B as 001 and so on. Unfortunately, there
are only 8 possible codes using 3 bits, so we could store the letters A to H but not the rest,
and what about the lower case letters and punctuation and…? The computer can store as
many characters as necessary simply by using more and more bits for the code. Some
systems don’t need to be able to recognise a lot of characters so they only use a few bits
for each character. The number of bits needed to store one character is called a byte which
is usually said to have 8 bits because most systems use 8 bits to store the code for each
We now have enough codes, but another problem arises. If my computer stores A as
01000001 and your computer stores A as 01000010 then the computers cannot
communicate because they cannot understand each other’s codes. In the 1960’s a meeting
in America agreed a standard set of codes so that computers could communicate with each
other. This standard set of codes is known as the ASCII set. Most systems use ASCII so
you can be fairly sure that when you type in A it is stored in the computer’s memory as
01000001. However, you can’t be sure because some systems use other codes. A less
common code is called EBCDIC, it was developed for use by larger scale computer
systems and differs in that the code for each character is different than that used in ASCII.
Notes: All the characters that a system can recognise are called its character set.
ASCII uses 8 bits so there are 256 different codes that can be used and hence 256
different characters. (This is not quite true, we will see why in chapter 1.6.)
A problem arises when the computer retrieves a piece of data from its memory. Imagine
that the data is 01000001. Is this the number 65, or is it A?
They are both stored in the same way, so how can it tell the difference?
The answer is that characters and numbers are stored in different parts of the memory, so
it knows which one it is by knowing whereabouts it was stored.
1.4.5 Data Types
The computer needs to use different types of data in the operation of the system. All of
these different types of data will look the same because they all have to be stored as
binary numbers. The computer can distinguish one type of data from another by seeing
whereabouts in memory it is stored.
There are different types of numbers that the computer must be able to recognise.
Numbers can be restricted to whole numbers, these are called INTEGERS and are stored
by the computer as binary numbers using a whole number of bytes. It is usual to use
either 2 bytes (called short integers) or 4 bytes (called long integers), the difference being
simply that long integers can store larger numbers. Section 1.4.2 described how negative
integers could be stored, these have to be treated as different types of data by the
computer because the MSB of the data stands for something different than in an ordinary
Another type of number is a fraction (or decimal). This is stored by changing the position of
the point so that it is always at the front of the number and then storing the fraction that is
left (there is no whole part because the point comes first). However, 2.3 and .23 will now
both be stored as .23 so we need an extra piece of data to be stored, the number of places
the point has had to move. Fractions, then, are stored in two parts: the fraction part (called
the mantissa) and the number of places the point has had to move (called the exponent).
Because the first stage is always to move the point to the front of the number, and it is like
the point “floating to the top”, fractions are stored in FLOATING POINT form. Obviously
there is a lot missing from this explanation, but that is more than enough for this part of
the course. Simply remember that fractions are stored in binary with the point at the front,
and then a separate part is the number of places the point has had to move to get it to the
Sometimes the answer to a question is either yes or no, true or false. There are only two
options. The computer uses binary data which consists of bits of information that can be
either 0 or 1, so it seems reasonable that the answer to such questions can be stored as a
single bit with 1 standing for true and 0 standing for false. Data which can only have two
states like this is known as BOOLEAN data.
A simple example of its use would be in the control program for an automatic washing
machine. One of the important pieces of information for the processor would be to know
whether the door was shut. A boolean variable could be set to 0 if it was open and to 1 if it
was shut. A simple check of that value would tell the processor whether it was safe to fill
the machine with water.
A character can be anything, which is represented in the character set of the computer by
a character code in a single byte.
Data stored in a computer is stored at any location in memory that the computer decides
to use. This means that similar pieces of data can be scattered all over memory. This, in
itself, doesn’t matter to the user, except that to find each piece of data it has to be referred
to by a variable name.
e.g. If it is necessary to store the 20 names of students in a group then each location
would have to be given a different variable name. The first, Jane, might be stored in
location NAME, the second, John, might be stored in FORENAME, the third, Penny, could be
stored in CHRINAME, but I’m now struggling, and certainly 20 different variable names that
made sense will be very taxing to come up with. Apart from anything else, the variable
names are all going to have to be remembered.
Far more sensible would be to force the computer to store them all together using the
variable name NAME. However, this doesn’t let me identify individual names, so if I call the
first one NAME(1) and the second NAME(2) and so on, it is obvious that they are all
peoples’ names and that they are distinguishable by their position in the list. Lists like this
are called ARRAYS.
Because the computer is being forced to store all the data in an array together, it is
important to tell the computer about it before it does anything else so that it can reserve
that amount of space in its memory, otherwise there may not be enough space left when
you want to use it. This warning of the computer that an array is going to be used is called
INITIALISING the array. Initialising should be done before anything else so that the
computer knows what is coming.
Initialising consists of telling the computer
what sort of data is going to be stored in the array so that the computer knows what part
of memory it will have to be stored in
how many items of data are going to be stored, so that it knows how much space to
the name of the array so that it can find it again.
Different programming languages have different commands for doing this but they all do
the same sort of thing, a typical command would be
DIM is a command telling the computer that an array is going to be used
NAME is the name of the array
$ tells the computer that the data is going to be characters
(20) tells it that there are going to be up to 20 pieces of data.
Notes: Just because the computer was told 20 does not mean that we have to fill the array,
the 20 simply tells the computer the maximum size at any one time.
The array that has been described so far is really only a list of single data items. It would
be far more useful if each student had a number of pieces of information about them,
perhaps their name, address, date of birth. The array would now have 20 students and
more than one thing about each, this is called a two dimensional array. Obviously
everything gets more complicated now, but don’t worry as use of multi-dimensional arrays
is for later in the course.
We should now have a picture of a part of memory which has been reserved for the array
NAME$ - -
To read data into the array simply tell the computer what the data is and tell it the position
to place it in e.g. NAME$(11) = Thomas will place Thomas in position 11 in the array
(incidentally, erasing any other data that happened to be in there first.
To read data from the array is equally simple, tell the computer which position in the array
and assign the data to another value
e.g. RESULT = NAME$(2) will place John into a variable called RESULT.
Searching for a particular person in the array involves a simple loop and a question
e.g. search for Vera in the array NAME$
Counter = 1
While Counter is less than 21, Do
If NAME$(Counter) = Vera Then Print “Found” and End.
Else Add 1 to Counter
Print “Name not in array”
Try to follow the logic of the steps above.
1.4.7 Linked Lists
When data is stored in a computer the processor can store it in any location provided it can
get the data back. In order to get the data back, each of the locations where the data is
stored is given an address so that if the computer can remember the address of where it
put some information it can easily retrieve it. If everything has to be in the index then the
index can get very large, it seems reasonable to try to cut down the size of the index by
grouping things together under one index entry. One method for doing this is by using an
array, the twenty people in the set could all be found by the one reference to NAME which
pointed to the location of the array. There are two major problems with arrays. The first is
that if the size of the set grows because a new student joins there is no room in the array
to store the information. This is because the array size has to be predetermined. The array
could be made much bigger, say size 50, so that we are sure it will never be too small, but
this leads to the second problem, that most of this space will never be used, consequently
wasting valuable memory. These problems can be overcome by using a linked list.
A linked list of data items tells the computer to store the data in any location and to link it
to the previous data item by giving the previous data item the address of the new one.
That sounds very complex, the idea is simple if we look at it in diagram form.
Imagine the list of names used in the example for the array.
Address Data Next address
Start address 60 Penny 75
61 61 Jane 86
63 Zaid XX
86 John 60
The diagram is intended to show a portion of memory. Each of the locations that can hold
data are given an address, and the address of the first data in the list is stored separately.
This tells the computer where the first piece of data is. If the first data item is not the one
that is wanted, the computer goes to the next piece of data by using the address that is
stored with the data. These addresses are called pointers, the last one of which has to be
one that cannot possibly exist so that the computer knows it has reached the end of the
list. Notice that the two problems associated with arrays no longer exist.
Linked lists are often drawn showing the data in boxes and the linking addresses as
pointers. This is the better method for describing a list, just don’t lose sight of the fact that
the arrows are really address references.
Start Jane Penny
John Zaid XX
Note: The jagged line signifies that there are a number of others which would fit in there,
but they are not shown.
To initialise a list, all that needs to be done is to create a new start pointer for this list and
add it to the index of start pointers for all the other lists.
To search through the list for a particular piece of data follow these rules
1. Find the correct list in the index of lists
2. Follow the pointer to the next item
3. If the item is the one being searched for, report that it is found and end.
4. If the pointer shows that the end of the list has been reached, report that the item is not
there and end.
5. Go to step 2.
To remove a value from a list, simply change the pointer that points to it into one that
points to the next value after it. E.g. to remove John from the example
Start Jane Penny
John Zaid XX
Note that John’s data is still there, its just that there is no way of getting to it so it might
just as well not be. 1.4.8 Stacks and Queues
Information arrives at a computer in a particular order, it may not be numeric, or
alphabetic, but there is an order dependent on the time that it arrives. Imagine Zaid, Jane,
John and Penny send jobs for printing, in that order. When these jobs arrive they are put in
a queue awaiting their turn to be dealt with. It is only fair that when a job is called for by
the printer that Zaid’s job is sent first because his has been waiting longest. These jobs are
held, just like the other data we have been talking about, in an array. The jobs are put in
at one end and taken out of the other. All the computer needs is a pointer showing it which
one is next to be done (start pointer(SP)) and another pointer showing where the next job
to come along will be put (end pointer(EP))
1. Zaid is in the queue for printing, the end pointer is pointing at where the next job will go.
2. Jane’s job is input and goes as the next in the queue, the end pointer moves to the next
3. Zaid’s job goes for printing so the start pointer moves to the next job, also John’s job
has been input so the end pointer has to move.
EP Jane SP Jane
SP Zaid SP Zaid
1. 2. 3.
Notes: The array is limited in size, and the effect of this seems to be that the contents of
the array are gradually moving up. Sooner or later the queue will reach the end of the
array. The queue does not have to be held in an array, it could be stored in a linked list.
This would solve the problem of running out of space for the queue, but does not feature in
this course until the second year.
Imagine a queue where the data was taken off the array at the same end that it was put
on. This would be a grossly unfair queue because the first one there would be the last one
dealt with. This type of unfair queue is called a stack.
A stack will only need one pointer because adding things to it and taking things off it are
only done at one end
1. Zaid and Jane are in the stack. Notice that the pointer is pointing to the next space.
2. A job has been taken off the stack. It is found by the computer at the space under the
pointer (Jane’s job), and the pointer moves down one.
3. John’s job has been placed on the stack in the position signified by the pointer, the
pointer then moves up one. This seems to be wrong, but there are reasons for this being
appropriate in some circumstances which we will see later in the course.
Jane Pointer John
Zaid Zaid Zaid
1. 2. 3.
In a queue, the Last one to come In is the Last one to come Out. This gives the acronym
LILO, or FIFO (First in is the first out).
In a stack, the Last one In is the First one Out. This gives the acronym LIFO, or FILO (First
in is the last out).
1.4.9 Files, Records, Items, Fields.
Data stored in computers is normally connected in some way. For example, the data about
the 20 students in the set that has been the example over the last three sections has a
connection because it all refers to the same set of people. Each person will have their own
information stored, but it seems sensible that each person will have the same information
stored about them, for instance their name, address, telephone number, exam grades…
All the information stored has an identity because it is all about the set of students, this
large quantity of data is called a FILE.
Each student has their own information stored. This information refers to a particular
student, it is called their RECORD of information. A number of records make up a file.
Each record of information contains the same type of information, name, address and so
on. Each type of information is called a FIELD. A number of fields make up a record and all
records from the same file must contain the same fields.
The data that goes into each field, for example “Jane Smith”, “3 Canal St.” will be different
in most of the records. The data that goes in a field is called an ITEM of data.
Note: Some fields may contain the same items of data in more than one record. For
example, there may be two people in the set who happen to be called Jane Smith. If Jane
Smith’s brother Tom is in this set he will presumably have the same address as Jane. It is
important that the computer can identify individual records, and it can only do this if it can
be sure that one of the fields will always contain different data in all the records. Because
of this quality, that particular field in the record is different from all the others and is known
as the KEY FIELD. The key field is unique and is used to identify the record. In our example
the records would contain a field called school number which would be different for each
Note: Jane Smith is 10 characters (1 for the space), Christopher Patterson is 21
characters. It makes it easier for the computer to store things if the same amount of space
is allocated to the name field in each record. It might waste some space, but the searching
for information can be done more quickly. When each of the records is assigned a certain
amount of space the records are said to be FIXED LENGTH. Sometimes a lot of space is
wasted and sometimes data has to be abbreviated to make it fit. The alternative is to be
able to change the field size in every record, this comes later in the course.
1.4.10 Record Formats.
To design a record format, the first thing to do is to decide what information would be
sensible to be stored in that situation.
e.g. A teacher is taking 50 students on a rock-climbing trip. The students are being
charged 20 pounds each and, because of the nature of the exercise, their parents may
need to be contacted if there is an accident. The teacher decides to store the information
as a file on a computer. Design the record format for the file.
The fields necessary will be Student name, Amount paid, Emergency telephone number,
Form (so that contact can be made in school). There are other fields that could be included
but we will add just one more, the school number (to act as the key field).
For each one of these fields it is necessary to decide what type of data they will be and
also to decide how many characters will be allowed for the data in that field, remember
these are fixed length records.
The easiest way is to write them in a table
Student number Integer 1 byte
Student name Character 20 bytes
Amount paid Integer 1 byte
Emergency number Character 12 bytes
Form (e.g.3RJ) Character 3 bytes
Notes: It would be perfectly reasonable to say that the school number was not a proper
number so it should be stored as characters (probably 4 bytes) or in BCD (2 bytes).
The student name is quite arbitrary. 15 bytes would be perfectly reasonable, as would 25
bytes, but 5 bytes would not. In other words there is no single right answer, but there are
The amount paid is listed as an integer as the teacher will store the number of whole
pounds so far paid. This is not the best data type for an amount of money but it is the only
one that fits so far. When you have learned about other data types use them if they are
Many students expect that the emergency number should be an integer, but phone
numbers start with a 0, and integers are not allowed to. As most numbers do start with 0,
the computer can be programmed to put them in at the start of the rest of the number, but
you would have to say this in your answer. As we are not going to do any arithmetic with
these numbers, why make life more complicated than necessary.
3 characters were allowed for form. If in doubt, give an example of what you mean by the
data, it can’t hurt and it may save you a mark in the question.
1.4.11 Sizing a File
We have just designed the record format for a given situation. It may be necessary to
calculate how large the file is going to be.
Having decided on the size of each field, it is a simple matter of adding up the individual
field sizes to get the size of a record, in this case 37 bytes.
There are 50 students going on the trip, each of them having their own record, so the size
of the data in the file will be 50 * 37 = 1,850 bytes.
All files need a few extra pieces of information that the user may not see such as
information at the start of the file saying when it was last updated, which file it is, is it
protected in any way? These sort of extra pieces of information are known as overheads,
and it is usual to add 10% to the size of a file because of the need for overheads.
Therefore the size of the file is 1,850 bytes + (10% of 1,850 bytes) =2,035 bytes.
The final stage is to ensure that the units are sensible for the size of the file.
There are 1024 bytes in 1 Kbyte, so the size of this file is 2,035/1024 =
Note: Don’t worry about dividing by 1024, because, after all, this is only an approximation
anyway. If you gave the final answer as 2 (approx) then that is just as acceptable. Just
make sure that you write down somewhere that you know that there are 1024 bytes in a
Kbyte, otherwise you can’t be given the mark for knowing that.
1.4.12 Access Methods to Data
Computers can store large volumes of data. The difficulty is to be able to get it back. In
order to be able to retrieve data it must be stored in some sort of order. Imagine the
phone book. It contains large volumes of data which can be used, fairly easily, to look up a
particular telephone number because they are stored in alphabetic order of the
subscriber’s name. Imagine how difficult it would be to find a number if they had just been
placed in the book at random. The value of the book is not just that it contains all the data
that may be needed, but that it has a structure that makes it accessible. Similarly, the
structure of the data in a computer file is just as important as the data that it contains.
There are a number of ways of arranging the data that will aid access under different
Data is stored in the computer in the order in which it arrives. This is the simplest form of
storage, but the data is effectively unstructured, so finding it again can be very difficult.
This sort of data storage is only used when it is unlikely that the data will be needed again,
or when the order of the data should be determined by when it is input. A good example of
a serial file is what you are reading now. The characters were all typed in, in order, and
that is how they should be read. Reading this book would be impossible if all the words
were in alphabetic order. Another example of the use of a serial file will be seen in section
In previous sections of this chapter we used the example of a set of students whose data
was stored in a computer. The data was stored in alphabetic order of their name. It could
have been stored in the order that they came in a Computing exam, or by age with the
oldest first. However it is done the data has been arranged so that it is easier to find a
particular record. If the data is in alphabetic order of name and the computer is asked for
Zaid’s record it won’t start looking at the beginning of the file, but at the end, and
consequently it should find the data faster.
A file of data that is held in sequence like this is known as a sequential file.
Imagine a large amount of data, like the names and numbers in a phone book. To look up
a particular name will still take a long time even though it is being held in sequence.
Perhaps it would be more sensible to have a table at the front of the file listing the first
letters of peoples’ names and giving a page reference to where those letters start. So to
look up Jones, a J is found in the table which gives the page number 232, the search is
then started at page 232 (where all the Js will be stored). This method of access involves
looking up the first piece of information in an index which narrows the search to a smaller
area, having done this, the data is then searched alphabetically in sequence. This type of
data storage is called Index Sequential.
A file that stores data in no order is very useful because it makes adding new data or
taking data away very simple. In any form of sequential file an individual item of data is
very dependent on other items of data. Jones cannot be placed after Monks because that is
the wrong ‘order’. However, it is necessary to have some form of order because otherwise
the file cannot be read easily. What would be wonderful is if, by looking at the data that is
to be retrieved, the computer can work out where that data is stored. In other words, the
user asks for Jones’ record and the computer can go straight to it because the word Jones
tells it where it is being stored. How this can be done is explained in section 1.4.13.
1.4.13 Implementation of File Access Methods
This section is about how the different access methods to data in files can be put into
practice. There will not be a lot of detail, and some questions will remain unanswered, don’t
worry because those will appear in further work.
Serial files have no order, no aids to searching, and no complicated methods for adding
new data. The data is simply placed on the end of the existing file and searches for data
require a search of the whole file, starting with the first record and ending, either with
finding the data being searched for, or getting to the end of the file without finding the
Because sequential files are held in order, adding a new record is more complex, because
it has to be placed in the correct position in the file. To do this, all the records that come
after it have to be moved in order to make space for the new one.
e.g. A section of a school pupil file might look like this
James, Amanda, 21 Church St, F, 21/03/……..
Jones, David, 134 New Gardens, M, ………
Marsden, Thomas, ………..
Newsome, Claire, ………..
If a new pupil arrives whose name is Johnson, space must be found between James and
Jones. To do this all the other records have to be moved down one place, starting with
Newsome, then Marsden, and then Jones.
James, Amanda, 21 Chur…………
Jones, David, 134 Ne……….
Marsden, Thomas, …….
Newsome, Claire, ……..
This leaves a space into which Johnson’s record can be inserted and the order of the
records in the file can be maintained.
Having to manipulate the file in this way is very time consuming and consequently this type
of file structure is only used on files that have a small number of records or files that
change very rarely.
Larger files might use this principle, but would be split up by using indexing into what
amounts to a number of smaller sequential files.
e.g. the account numbers for a bank’s customers are used as the key to access the
customer accounts. The accounts are held sequentially and there are approximately 1
million accounts. There are 7 digits in an account number.
Indexes could be set up which identify the first two digits in an account number. Dependent
on the result of this first index search, there is a new index for the next two digits, which
then points to all the account numbers, held in order, that have those first four digits.
There will be one index at the first level, but each entry in there will have its own index at
the second level, so there will be 100 indexes at the second level. Each of these indexes
will have 100 options to point to, so there will be 10,000 blocks of data records. But each
block of records will only have a maximum of 1000 records in it, so adding a new record in
the right place is now manageable which it would not have been if the 1million records
were all stored together.
… 00 0102000 DATA
99 01 0102001
One … 0102003
First level index 99 ……….
(first two digits 0102999
in account number)
Second level indexes Final index blocks
(third and fourth digits each containing up to
in account number) 1000 account numbers
To access a random file, the data itself is used to give the address of where it is stored.
This is done by carrying out some arithmetic (known as pseudo arithmetic because it
doesn’t make much sense) on the data that is being searched for.
E.g. imagine that you are searching for Jones’ data.
The rules that we shall use are that the alphabetic position of the first and last letters in the
name should be multiplied together, this will give the address of the student’s data.
So Jones = 10 * 19 = 190. Therefore Jones’ data is being held at address 190 in memory.
This algorithm is particularly simplistic, and does not give good results, as we shall soon
see, but it illustrates the principle. Any algorithm can be used as long as it remains the
same for all the data.
This type of algorithm is known as a HASHING algorithm.
The problem with this example can be seen if we try to find James’s data.
James = 10 * 19 = 190. The data for James cannot be here because Jones’s data is here.
This is called a CLASH. When a clash occurs, the simple solution is to work down
sequentially until there is a free space. So the computer would inspect address 191, and if
that was being used, 192, and so on until a blank space. The algorithm suggested here will
result in a lot of clashes which will slow access to the data. A simple change in the
algorithm will eliminate all clashes. If the algorithm is to write down the alphabetic position
of all the letters in the name as 2 digit numbers and then join them together there could be
no clashes unless two people had the same name.
e.g. Jones = 10, 15, 14, 05, 19 giving an address 1015140519
James = 10, 01, 13, 05, 19 giving an address 1001130519
The problem of clashes has been solved, but at the expense of using up vast amounts of
memory (in fact more memory than the computer will have at its disposal). This is known
as REDUNDANCY. Having so much redundancy in the algorithm is obviously not acceptable.
The trick in producing a sensible hashing algorithm is to come up with a compromise that
minimizes redundancy without producing too many clashes.
1.4.14 Selection of Data Types and Structures
When the computer is expected to store data, it has to be told what type of data it is going
to be because different types of data are stored in different areas of memory. In addition
to the types of data that we have already described, there are other, more specialised,
data types. Most can be covered by calling them characters (or string data, which is just a
set of characters one after the other), but there are two others that are useful. Currency
data is, as the name suggests, set up to deal with money. It automatically places two digits
after the point and the currency symbol in. The other is date, this stores the date in either
6 or 8 bytes dependent on whether it is to use 2 or 4 digits for the year. Care should be
taken with the date because different cultures write the three elements of a date in
different orders, for example, Americans put the month first and then the day.
Students should be able to justify the use of a particular type of structure for storing data
in given circumstances. Questions based on this will be restricted to the particular
structures mentioned in 1.4.7 and 1.4.8 and will be non-contentious. E.g. Jobs are sent to a
printer from a number of sources on a network. State a suitable data structure for storing
the jobs that are waiting to be printed giving a reason for your answer.
Answer: A queue, because the next one to be printed should be the one that has been
1.4.15 Backing up and Archiving Data
Backing up data.
Data stored in files is very valuable. It has taken a long time to input to the system, and
often, is irreplaceable. If a bank loses the file of customer accounts because the hard disk
crashes, then the bank is out of business.
It makes sense to take precautions against a major disaster. The simplest solution is to
make a copy of the data in the file, so that if the disk is destroyed, the data can be
recovered. This copy is known as a BACK-UP. In most applications the data is so valuable
that it makes sense to produce more than one back-up copy of a file, some of these copies
will be stored away from the computer system in case of something like a fire which would
destroy everything in the building.
The first problem with backing up files is how often to do it. There are no right answers, but
there are wrong ones. It all depends on the application. An application that involves the file
being altered on a regular basis will need to be backed up more often than one that is very
rarely changed (what is the point of making another copy if it hasn’t changed since the
previous copy was made?). A school pupil file may be backed up once a week, whereas a
bank customer file may be backed up hourly.
The second problem is that the back-up copy will rarely be the same as the original file
because the original file keeps changing. If a back up is made at 9.00am and an alteration
is made to the file at 9.05am, if the file now crashes, the back up will not include the
change that has been made. It is very nearly the same, but not quite. Because of this, a
separate file of all the changes that have been made since the last back up is kept. This file
is called the transaction log and it can be used to update the copy if the original is
destroyed. This transaction log is very rarely used. Once a new back up is made the old
transaction log can be destroyed. Speed of access to the data on the transaction log is not
important because it is rarely used, so a transaction log tends to use serial storage of the
data and is the best example of a serial file if an examination question asks for one.
Data sometimes is no longer being used. A good example would be in a school when pupils
leave at the end of the sixth form. All their data is still on the computer file of pupils taking
up valuable space. It is not sensible to just delete it, there are all sorts of reasons why the
data may still be important, for instance a past pupil may ask for a reference. If all the
data has been erased it may make it impossible to write a sensible reference. Data that is
no longer needed on the file but may be needed in the future should be copied onto long
term storage medium and stored away in case it is needed. This is known as producing an
ARCHIVE of the data. (Schools normally archive data for 7 years before destroying it).
Note: Archived data is NOT used for retrieving the file if something goes wrong, it is used
for storing little used or redundant data in case it is ever needed again, so that space on
the hard drive can be freed up.
1. a) Express the number 113 (denary) in
(ii) in BCD
using an appropriate number of bytes in each case. (4)
b) Using the answer obtained in part (a) show how 113 (denary) can be expressed in
(ii) hexadecimal. (4)
A. a) (i) 128 64 32 16 8 4 2 1
0 1 1 1 0 0 0 1 =01110001.
(ii) 1 = 0001
1 = 0001
3 = 0011
Therefore 113 = 0000000100010011
b) (i) 113 = 001 110 001 in binary
= 1 6 1 in octal.
(ii) 113 = 0111 0001 in binary
= 7 1 in hexadecimal.
Notice: (i) and (ii) It was necessary to show a method of working out. Many students have
calculators that will automatically change from one number system to another, so it is
necessary to show that you know what you are doing, even if you use a calculator to check
the results. Also, the question stated that the appropriate number of bytes be used, in part
(i) this is obviously 8 bits and is an easy mark, but in part (ii) it is necessary to add a set of
zeros to the front of the answer to make it a whole number of bytes.
(iii) and (iv) The question stated that the first answer had to be used, so one of the two
marks is going to be given for showing the relationship between binary and each of these
two representations. Notice that for the octal answer it was necessary to add a 0 to the
front of the binary number to give 9 bits (3 lots of 3).
2. Explain how the denary number –27 can be represented in binary in
(i) sign and magnitude
(ii) two’s complement
notation, using a single byte for each answer. (4)
A. (i) +/- 64 32 16 8 4 2 1
1 0 0 1 1 0 1 1 = 10011011
(ii) –27 = -128 + 101
= -128 + (+64 +32 +4 +1)
-128 64 32 16 8 4 2 1
1 1 1 0 0 1 0 1 = 11100101
Notice that the question asked “Explain…”, so just writing the answer down is not
acceptable. There will be a mark for showing the column headings, particularly the value of
the MSB in each case.
3. Add together the binary equivalents of 34 and 83, using single byte arithmetic, showing
you working. (3)
A. 34 = 0 0 1 0 0 0 1 0
83 = 0 1 0 1 0 0 1 1 +
0 1 1 1 0 1 0 1 = 117
Note that the question asked for the working. The part that shows that you are capable of
doing the arithmetic is the carry, don’t miss it out. In a question like this try to ask yourself
what evidence the examiner is expecting for the mark. The other marks are for using 8
bits for each value, and for the answer.
4. Describe how characters are stored in a computer. (3)
A. -Each character is given a code…
-as a binary number
-Each character code occupies one byte of data
-Typically one byte is eight bits
-Most computers use a standard set of characters like the ASCII set.
There are lots of marks available here. The question has been left deliberately open so
that there are plenty of mark points available.
5.a) Explain the difference between integer and floating point data types. (2)
b) State what is meant by Boolean data. (1)
A. a)-Integers are whole numbers
-Floating point numbers allow for the storage of fractions.
b)-Boolean data is data that can exist in two states, e.g. true or false.
Note that in part (a) there may be lots of other differences that you know, but they are not
really part of this syllabus. If your answer is valid though, it will be given the marks. In
part (b), this is another standard definition, don’t try to elaborate too much or you may
wander too far from the answer.
6. An array is to be used to store information.
State three parameters that need to be given about the array before it can be used,
explaining the reason why each is necessary. (6)
A. -The size of the array (how many data items it will hold)…
-so that this amount of space can be reserved in memory.
-The type of data to be stored in the array…
-so that it can be set up in the correct area of memory.
-The name of the array…
-so that it can be identified when it needs to be used.
-The number of dimensions of the array…
-so that the computer knows what form the data is going to be stored in.
Note: these marks go in pairs. Don’t worry if you are not happy with the last point, this is
a more advanced feature of arrays – look at the notes on section 1.4.6.
7. A garden centre stores details of each of the types of plant that it has for sale on a
computer system. The details of the plants are stored in alphabetical order in a linked list.
a)By drawing a diagram show how the plants are arranged in the list. You may use the
following plants to illustrate your answer
Pansy, Dahlia, Clematis, Sweet pea. (4)
b)Describe how a new linked list, of plants that like shaded conditions, can be created
from the original one. (4)
Head of list table Dahlia
(Start Pointer) Clematis
Sweet pea XX
-Some start position for list
-List in alphabetic order
-Use of pointers
-Use of null pointer to finish list.
b)-Create new linked list by creating a new start point.
-Read values from old list in turn
-If plant in old linked list likes shade then…
-add to new list and put in pointer.
-Repeat until null pointer (end of list)
-Place null pointer after last entry in new list
Note: The first part is fairly simple. Stick to the simple type of diagram and don’t forget
how to start and end the list. The second part is more difficult because it means a certain
degree of analysis of the problem to be able to solve it. This is why there are rather more
mark points available. When dealing with linked lists, if you draw a diagram and remember
to start and finish it, you won’t go far wrong.
8. A stack is being held in an array. Items may be read from the stack or added to the
a) State a problem that may arise when
(i) adding a new value to the stack
(ii) reading a value from the stack. (2)
b) Explain how the stack pointer can be used by the computer to recognise when such
problems may occur. (2)
A. a)(i) The array may be full, consequently no new value can be entered.
(ii) The array may be empty, there is no value to be read.
b)(i) The stack pointer will be pointing outside the array.
(ii) The stack pointer will be pointing at the first location in the array.
Notes. When discussing stacks and queues it is important to have a picture in your mind of
what it looks like. The simplest picture is to imagine them being held in an array. This is
not the only way to store them and you may have been shown other methods, but the
array is perfectly adequate for this course.
9. A library stores details of the books that are available.
a) Apart from title and author, state 3 other fields that it would be sensible for the library
to store in this file, giving a reason why each of your chosen fields would be necessary. (6)
b) State which field would be used as the key field of the record and explain why a key
field is necessary. (2)
c) State the size of each of the fields in your record. (2)
d) If the library stores approximately 20,000 books, estimate the size the book file. (3)
A. a)One mark for each of three sensible fields with an extra mark for an explanation of
the need for that field.
E.g. ISBN/to identify book
Shelf number/ to allow for ease of search for book
Fiction or reference or childrens’ (some form of category)/ to decide whereabouts in
library it should go
b)-Book number (ISBN)
-because it is unique to that record and hence can be used as an identifier.
c) Title 40 bytes
Author 20 bytes
ISBN 10 bytes
Shelf 3 bytes
Category 1 byte
-Use of bytes
-Sensible field sizes.
d)Total size of one record = 74 bytes
-Size of file = 74 * 20000 = 1480000 bytes
-+ Overheads of 10% = 1,480,000 + 148,000 = 1,628,000 bytes.
- (Divide by 1024 until sensible units) = 1.55 Mbytes.
Notes: In part (a), any sensible fields (can you justify it?) are acceptable. For instance,
Publisher/so that more copies may be ordered, would be a sensible field. In part (b) you
would be expected to provide the answer ISBN, although an explanation would be accepted
if it was clear what was meant. Try to be aware of the standard key fields (account
numbers, ISBN, barcodes, school numbers). The sizes of the fields are only given as
guidance. If you suggested 100 bytes for the title it would be accepted as being
reasonable. On the other hand 1000 bytes would be way over the top and 10 bytes would
be unreasonably small. Don’t worry about trying to get the ‘correct’ answer, there isn’t
one, just make it sensible. There is a correct answer for the ISBN, it is 10 characters long,
but it is not part of your syllabus to learn things like that off by heart, so as long as you
don’t say something silly like 30 bytes, which demonstrates that you don’t know what an
ISBN is, you will get the mark. In part (d) make sure that you convert your answer to
sensible units. Don’t worry about using a calculator, as long as you show that you did know
the correct method is to divide by 1024, an approximate answer is all that is necessary. In
this case it would be quite acceptable to write “Keep dividing by 1024, this gives
approximately 1.6 Mbytes”. When you answer this question your answer is highly unlikely
to be the same as this, don’t worry, the examiner will mark your answer and not expect it
to be the same as a model answer.
10. a)Explain the difference between a serial file and a sequential file. (2)
b)Describe what is meant by a hashing algorithm and explain why such an algorithm can
lead to clashes. (3)
A. a)-Serial file holds data in the order in which it was received.
-Sequential file holds the data according to some order defined on the data.
b)-A hashing algorithm is pseudo arithmetic…
-carried out on the data…
-in order to determine the location of the data in the memory.
-A clash occurs when the answer to the pseudo arithmetic is the same despite the data
used in the calculation being different.
Note: This is a question where it is very easy to try to answer too much. Restrict yourself
to what the question is asking. Many candidates faced with part (b) will go into great detail
about what to do after clashes have occurred, this is not required and will earn no marks.
11. A library keeps both a book file and a member file. The library does a stock take twice
a year and orders new books only once a year. Members can join or cancel their
membership at any time.
a) Describe how the library can implement a sensible system of backing up their files. (4)
b) Explain the part that would be played by archiving in the management of the files. (4)
A. a)-Book file needs to backed up twice (or three) times a year…
-when the stock take or book purchasing has made the file alter.
-Member file needs backing up daily(at least weekly) because of constant changes…
-would also need to keep a transaction log for the member file.
-Back up copies would be stored away from the building with the computer system in it to
ensure that a copy of files survived in case of fire.
-Multiple copies of the book file would be made
-Member file copies and transaction logs may be kept for a number of back up periods.
b)-When books are discovered to be missing, or if a book is replaced by a more
up-to-date edition, the old records should be kept…
-but they are no longer live so are taken from the hard disk…
-after a copy (archive) has been made.
-When members leave the library the data should be archived…
-also when they have not taken a book out for a long period of time their record can be
considered to be dormant.
Notes: Backing up and archiving are topics which cause confusion among candidates.
There really is no need for such confusion if you remember that archiving has nothing to
do with recovery after a disk failure. Note that there are plenty of mark points available in
Note: This chapter, or section of the syllabus, is by far the largest portion of module 1,
and consequently, candidates should expect a higher proportion of marks on the exam
paper to relate to this work than to the other sections.