Chapter 13

Question 1

user-defined types

Answer 1

derived from one or more existing datatypes
used to extend the built-in datatypes
programmer’s requirement

Question 2

why are user-defined types necessary

Answer 2

if no suitable datatype is provided by the language used
to provide more flexibility
if a programmer needs a specific datatype/needs to create a new data type
that meets program requirements

Question 3

composite data types

Answer 3

data types constructed from other types
e.g: record, list, set, array, class, queue, linked list, dictionary

Question 4

non-composite

Answer 4

datatype that does not refer to another datatype
e.g: enumerated, pointer, real, string, char, boolean

Question 5

enumerated

Answer 5

non-composite
defines an ordered list of all possible values

Question 6

enumerated TYPE pseudocode declaration

Answer 6

the values do not need any speech marks etc.

TYPE identifier = (value1, value2, …)

Question 7

pointer

Answer 7

non-composite
used to reference a memory location

Question 8

pointer TYPE pseudocode declaration

Answer 8

this is a declaration of the TYPE, not of the variable. if you wish to declare a variable of this pointer type:

TYPE pointerTypeName = ^DATATYPE

DECLARE variableName : pointerTypeName

Question 9

set

Answer 9

stores groups of values and supports mathematical operations

Question 10

record

Answer 10

composite
collection of related items with multiple datatypes
a fixed number of components
allows the user to collect values with different data types together.

Question 11

list

Answer 11

indexed collection that can contain different datatypes

Question 12

array

Answer 12

indexed collection of items of the same datatype

Question 13

serial file organization

Answer 13

• data is stored in chronological order (no predefined order)
• data is appended to the end of the file - into the next available space
• (easy to add)
• records need to be accessed one after the other
• allows the data to be read in order of when they were taken
  no KEY FIELDS need to be added

Question 14

when is serial used?

Answer 14

• when chronological order matters
• when wanting to append records
• small file, so easy to search
• when re-organizing as re-sorting is not required

Question 15

sequential file organization

Answer 15

• records are stored in a predefined order (particular order), stored in the order of the value in the key field
• new records are inserted in the correct position
• a new version of the file has to be created to update the file
• records need to be accessed one after the other
• records can be found by searching from the beginning of the file,
• record by record, until the required record is found or key field value is exceeded.

Question 16

when is sequential used?

Answer 16

• when there are unique fields, so it can be used for indexing
• when it needs to be sorted in an order

Question 17

random/direct file organization

Answer 17

• records are stored in no particular order
• record location is calculated
• using a hashing algorithm on a key field
• speed of data access is increased
• can be used as lookup file
• ** updates to the file can be carried out directly**

Question 18

what happens if a collision occurs in direct access

Answer 18

A collision occurs when the record location is taken.
the location from the hashed key field is in use for another record.

If the record is to be stored
* Search the file linearly
* … to find the next available storage space (closed hash)
* Search the overflow area linearly
* … to find next available storage space (open hash)

If the record is to be found
* … search the overflow area linearly
* … search linearly from where you are
* If not found record is not in file

Question 19

hashing algorithm

Answer 19

a mathematical function to find a hash key to access data

Question 20

sequential access

Answer 20

• searches from the beginning of the file
• checks records linearly (record by record)
• until the record is found or its the end of the file (key field value is exceeded)

Question 21

direct access

Answer 21

value in key field is submitted to hashing algorithm which provides position used at data input

Question 22

twos complement

Answer 22

start from the right side and copy down every digit until you encounter a 1
copy down the 1, and then flip all the rest of the bits after the 1

Question 23

format of binary floating point

Answer 23

plus or minus M x 2^E
M = mantissa
E = exponent

more bits in mantissa = more accurate
more bits in exponent = larger range

Question 24

normalisation rules

Answer 24

for positives, shift left until it starts with a 01
for negatives, shift left until it starts with a 10

Question 25

normalisation advantages

Answer 25

* **unique representation for each number** * minimise leading zeroes/ones * ensures number is as accurate as possible * **store max. range in min. bits** * maximises number of significant bits - can store very large or small numbers accurately * multiplication is more accurate and precise

Question 26

*example q from past paper, answer generically*: explain the reason why the normalised form of this binary number cannot be represented accurately using this system

Answer 26

* **The least significant digits would be truncated** * **...causing a loss of precision/accuracy** * the mantissa of the number would need to be X bits / digits * ...however it can only store X bits / digits * **BE SPECIFIC**

Question 27

convert floating point to denary

Answer 27

* if negative (starts with a 1), apply twos complement * move the mantissa decimal point (from between the first two bits) to the right, by the exponent value * convert by labelling integer digits with 1,2,4,8 etc and the decimal parts with 1/2, 1/4, 1/8, etc show the working out of the exponent e.g. exponent = X show the working out of the mantissa e.g. the moving of the decimal, the adding of numbers, etc. the final answer only gets one mark - SHOW WORKING OUT

Question 28

convert denary to floating point

Answer 28

* split the number into its whole part and its decimal section. * convert each corresponding side into binary * fill it into the mantissa (e.g. add extra zeroes to the front if necessary) * if the denary number is negative, apply twos complement * now move the binary point as far as possible until 1.0 or 0.1 (depending on positive or negative) can be formed (normalise it) * however many places it moved up is the exponent remember to show working out: of exponent - show the moving of the binary point of mantissa - show the conversion to binary

Question 29

overflow error

Answer 29

answer requires more bits than is available. number is shortened - less precise/accurate (remember to be SPECIFIC when questions ask - refer directly to the question)

Question 30

underflow error

Answer 30

trying to store a very small number, which is smaller than what you can store with the available bits. occurs after an arithmetic/logic operation

Question 31

rounding error in floating point

Answer 31

no exact binary conversion for some numbers/more bits needed to represent a number than available