Data Structures Part 1 Flashcards
Serial File
A serial file is one where the records are read in the order in which they are written. New records are added to the end of an existing file.
Sequential file
A sequential file is a serial file where the records are in order of the key field. The key field uniquely identifies a record. An example of a sequential file is a sorted transaction file.
Mask
A mask can be used to select particular bits.
ASCII
A common way of using 7 (or 8) bits to represent characters.
Binary Number
A number in base 2 using just the digits 0 and 1.
Bit
Binary Digit - the smallest unit of storage - a single 1 or 0.
Collision
In a hash file a collision occurs when the hash functions gives the same record position for two records.
Direct Access File
A file where any record can be accessed without having access it’s preceding records.
Exponent
The storage of position of the point in a floating point number.
File
A collection of records stored on backing store (tape/disk).
File processing
performing an operation (e.g. update) on each record in a file.
File update
The process of changing the contents of a file.
Fixed Point
A way of representing a whole number and a faction where the number of bits allocated to each is fixed.
Floating Point
A way of representing a whole number and fraction where the position of the point is stored separately.
Fully indexed file
A direct access file where every record has an entry in the index.
Hash File
A file where a calculation is applied to a key field value in order to give the position of the record in a direct access file. Usually modding by the amount of records.
Hash function
The calculation that is used to convert a key field value into a position in a file.
Hexadecimal
A substitution that replaces a group of 4 bits by a single character 0..9,A,B,C,D,E,F. Used to make binary number easier for humans to understand.
Index File
A direct access file where the key fields and the location of the records are stored in an index (usually held in RAM for fast searching).
Main memory
The fast memory used for holding data that is being processed and programs that are being executed.
Overflow
The attempt to store a number that is too large.
Normalising (numbers)
With floating point numbers making sure the mantissa is between 0.5 and 1 (to ensure the greatest accuracy).
Mantissa
The storage of the digits in a floating point number
Exponent
The storage of position of the point in a floating point number.
Random Access File
A file where a record can be accessed directly using the key which corresponds to the position in the file.
Range
The highest and lowest values that can be represented.
Rehash
The process of restructuring a hash file so that it can hold more records.
Relational files
Two or more files where a field of one file (foreign key) refers to a key field of a record in a different file.
Rounding
Rounding is the process of representing a truncated value by the closest possible value.
Sign and magnitude
The left hand bit can be used to represent the sign of the number (0 for +, 1 for -), the remainder of the bits used represents magnitude (side) of the number.
Signed numbers
Signed numbers can be either positive or negative indicated by a preceding sign.
Terminal Value
A dummy record used to indicate the end of a file.
Transaction file
A file containing all the changes that need to be made to a master file.
Truncation
When the number of bits needed is larger than the number of bits available.
An error introduced by the inability to store some of the fractional bits. In truncation digits are simply cut off.
Two’s complement
A common way of representing signed numbers.
Underflow
An error where the number is too small to be distinguished from 0.
Unicode
A way of representing a character as a pattern of 16 bits. Based on ASCII but allows for 65536 different character
Offset record numbers
Might prefer to use 5 digits instead of starting with 0. E.g. 10000, where you’d have to subtract by 1000.
Offset record number advantage
Prevent people from knowing how big the organisation is
Offset record number disadvantage
Leaves gaps and wastes space.
Hash File: What do you do it it’s occupied?
Go to the one above.
Hash File: Why might it not be stored?
Because the file is full.
Hash File: How might a full file be detected?
Serial search, looping through all positions. If all positions are occupied, then display an error.
Hash File: Why might a record not be found?
Because it doesn’t exist.
Hash File: When is it suitable?
When the key field is not a suitable numeric value or is non-numeric.
Hash File: Best way to create a key
MOD % by amount of record positions
Hash File: File Efficieny
As the file becomes full so the likelihood of clashes increases. The greater chance of a clash, the greater the average time taken to access a record. Best rule is to keep it half full, after it becomes two thirds full, the efficiency is impaired to rehash.
AND
0 | 0 = 0
0 | 1 = 0
1 | 0 = 0
1 | 1 = 1
OR
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
NOT
0 = 1 1 = 0
XOR
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 0
Advantage of Standard Code/ASCII
It’s understood by every software.
Overflow: When can it not occur?
If sign A is different from sign B
Overflow: When has it not occurred?
If sign A = Sign B and result has Sign A
Fixed Point: Disadvantage
Since the position of the point must be agreed in advance, this means a decision must be made as to the number of bits to the left and the number of bits to the right.
Floating Point: Advantages
Can store fractional values
For a given number of bits, stores a greater range of numbers.
Floating Point: Disadvantages
Numbers are stored as approximations
Calculations are slower because of the complex format
Integer: Advantages
Numbers stored with total accuracy.
Fast Calculations
Integer: Disadvantages
For given number stores a lesser range of numbers.
Can only store whole numbers.
Logical Shift Left
Move every digit to the left one place, causing the digit on the left to fall off. Add a 0 on the right.
Logical Shift Right
Move every digit to the right one place, causing the digit on the right to fall off. Add a 0 on the left.
Arithmetic shift left
BOOK
Arithmetic shift right
BOOk
Logical Shift Left: Effect
Times 2x (power of 2 by amount of shifts)
Logical Shift Right: Effect
Divide 2x (power of 2 by the amount of shifts)
Arithmetic shift right: Effect
Times 2x on 2’s compement (power of 2 by amount of shifts)
Arithmetic shift left: Effect
Divide 2x on 2’s compement (power of 2 by the amount of shifts)
Positive Mantisa
http://i.imgur.com/ORf43QH.png
Negative Mantisa
http://i.imgur.com/cqb0pY8.png
Problems with Truncation and Rounding
When truncated numbers are used in calculations then error can accumulate and create large errors.
