Flowchart diagrams

(a) 4 = u
13= n
3 = i
8 = v
2 = a
10= c

(b) h = 1

Trees

1. Explain what is ment by a data structure?
A data structure is an abstract set of data, organised in an efficient way so that the data
contained in it can be manipulated to process or extract information.

2. A linear list may be inplimented by the use of pointers, what is a linear list and how
do pointers help to impliment it?
an ordered set of elements
The pointers tell the computer which piece of data to take mext or to which location
to add the mext piece of data.

3. What is a tree structure? why are tree structures important in computer science?
A tree structure is a hierarchial data structure. They allow searching to be completed faster,
data can be organised aphabetically and will allow the computer to run smother.

4.

5. What is the main difference between a tree and a binary tree?
the main difference is the fact that a tree can have several child nodes whereas a binary tree
can only have 2 child nodes.

6. (a) What is an ordered binary tree?
this is a tree that is put into a specific order in that information can be systematically
recieved or added.
(b) Why are ordered binary trees important?
They are important because infomation can easily be stored and recieved in a specific order
for example

7. Explain how a binary tree may be used to store data in alphabetical order.
A binary tree may be used easily to store data in alphabetical order. This is done by comparison
in that one piece od data is compared to the last. eg. if ur first letter starts with a letters
lower than the root, then it moves to the left of it and if it is grater than the root then it moves
to the right.


8.What is ment by the terms FIFO and LIFO
First In First Out.
Last In First Out.

9 (a) What is an alternative name for an LIFO data structure?
(b) What is an alternative name for an FIFO data structure?
An alternative name for an LIFO data structure is a stack
An alternative name for an FIFO data structure is a Que

10. Pointers play an important role when implementing queues and stacks. Explain the role of these
pointers when implementing each of these data structures.
In FIFO systems, pointers are used to indicate the start, or the head, of the que, and are also used
to indicate the end, or the footer, of the que. Queues are simple to use, but they must also be implemented
to work with data changes, so circular queues must be used. This simply means that the pointer must
move with the changes.
A LIFO works in the same way only that the pointer is chaged to the top of the stack so that the lsat one
in is always the first one out.

Self-Test Questions

Most low-level programming is carried out using assembly language. What typical scenario might mean that a program has to be written in the machine code?

When you are writing a program for a specific coomputer or a specific group of computers that are of the same make. An example could be for a super computer where the computer will be programed to do a unique job and therefor will be one of a kind. Also as it is coded in machine code, the program will run alot quicker as it does not need to be decoded.

Why do assembly language instructions written for one type of machine not run in another?

Because the instructions will be written for the specific processor installed which may not be the same in any other computer. The registers will be named differnetly and will therefor not run properly

What is the purpose of the following part of a typical assembly language instruction?:

Label - To name the instruction involved

Operation code - To carry out the job required

Operands - To define the registers used

Comments - To let a reader know what is going on.

Why are different modes of addressing encountered when programming in assembly language? Explain what is meant by immediate, direct, indirect and indexed addressing.
So that you can load different registers into the ALU for example and do different things with them.
Immediate Addressing where the data appears immediatly after the operation code
Direct Addressing where the address is referring to a specific location
Indirect Addressing The use on a number inside the register as a memory location.
Indexed Addressing where the number in one address is used in combination with an other address to get the memory location.


An assembly language instruction set may be broken down into subsets like logical and arithmetical and control. Show how 2 simple one-byte integer binary numbers may be added together.

op code	operands
add	al, bx

Explain how a mask may be used to prevent alteration of top(most significant) three bits and the bottom (least significant) two bits but set the rest of the bits in the register to 1

Not sure how to do this question. Ideas are that you must use the AND and OR op codes but i don't know how.

Assembly Language

Assembly language is a Second-Generation low level language made up form mnemonics which can be used instead of machine code.
The formate for this language generally consist in 4 parts:

1. Label eg Start:
2. Op Code eg mov
3. Operands eg bx.8Oh
4. Comments eg ;load character count.

Addressing Modes

Understanding assemlby language is intimitly ties up with addressing modes. These are related to physical attributes like the registers available and the word length, if, for example you have a single byte register in which to store information for a jump instruction, then you can jump a maximum of 2525 memory locations. Double the length of the location and you could jump 65636 locations or from +32767 to -32768 of you are using a 2's compliment system.

Register Addressing

When data is transferred from a source register to a destination register

Immediate Addressing

This is when the data appears immediately after the op code, as part of the instruction. Immediate addressing is a very convenient way of putting numbers into registers by specifying the number as one of the operands.

Direct Addressing

Direct addressing refers directly to a specific memory location.

label	op code	operands	comments
	mov	ax, [myData]	;an example of direct addressing

Here the contents of the memory location, in the case specified by a label named myData, is copied into the ax register.

Indirect Addressing.

Indirect addressing uses a number inside the register(usually an index register to point to the memory loaction of interest where the actual data can be found.

label	op code	operands	comments
	mov	ax, [bx]	;an example of indirect addressing

In this example the brackets around the bx register indicate that the memory location pointed to by the bx register, and not the actual number inside the bx register, will be used. In this case the data in the memory location pointed to by the bx register is copied to the bx register.

Indexed Addressing

For indexed addressing a number contained in one register is usually uded in combination with the number in another register to point to the actual memory location where the data can be obtained.

label	op code	operands	comments
	mov	ax, [bx + di]	;an example of direct addressing

In this example the number in the bx register is combined with the number in the di register. As with indirect addressing, the square brackets indicate that this points to the memory location from where the actual data to be put into the cx register can be obtained.

Base Register and Base Indexed Addressing.

label	op code	operands	comments
	ld	&10[ax]	;an example of base register addressing
	mov	cx,[bx+di]	;an example of based indexed addressing

In the first entry an address is held in the base register, in this case the ax register, and an offset (the hex number 10) is added to it. The second entry is useful for handling arrays.

Example

By means of an example, show a typical use for a base indexed addresing mode

Solution

A classic example of indxed addressing is setting up an array un memory. Consider the two - dimentional array, as shown in thne following examaple.

This could be mapped onto the memory lacations as shown below.
A linear sequence of memory locations is mapped onto a 2 dimentional array by using 2 index registers, namly the base-index and destination-index registers
One register is used fr each dimention of the array. The example shows how th efith element of the array, ie. 22, is accessed by putting the base index register
to a value of 3, and the destination index register of value of 1. In this case the fith element(not to forget we start at 0) and the number 22 is placed in the
cx register.

Actual Address  MEMORY  Indexed Address
address + 0  10  Address + 0 + 0
address + 1  11  Address + 0 + 1
address + 2  12  Address + 0 + 2
address + 3  21  Address + 3 + 0
address + 4  22  Address + 3 + 1
address + 5  23  Address + 3 + 2
address + 6  31  Address + 6 + 0
address + 7  32  Address + 6 + 1
address + 8  33  Address + 6 + 2

Typical Assembly Language Instructions.

Instructions are made of:

Logical Operations - "And", "Or" and "Not"

Rotate Instructions - Shift left and Right

Arithmetical Instructions

Bit SET and bit RESET instructions

Program control instructions - like "jump"

Arithmatical Operations

Typical of the operations are addition, subtraction, multiplication and divsion. The complexity of each operation depends
on what is being done. For example, when dividing two numbers there will probably be an integer answer(called thequotient)
and a remainder. When multiplying two numbers the register for holding the the two numbers to be multiplied will be held in smaller
than the register needed of the answer.

Logical Operations

The logical operations include and, or, not and xor etc. These instructions operate in what is called BITWISE MODE,
where each bit of a register is matched against the equivalent bit in another register. The and operation is particularly useful for
MASKING.

Masking

When using the logical functions we can create a mask which wither lets a pattern of bits through, or blocks them.Masking is used
extensively in assembly language to set or reset some of the bits without altering the patterns of other bits.