1.4 Data types, structures and algorithms Flashcards
What is a primitive data type
Basic type is a data type provided by a programming language as a basic building block
What are the common primitive data types (5)
Integer
Floating point/ real
Character
String
Boolean
What do integers hold
Whole numbers
What do floating points/ reals hold
A number with a fractional part
What do characters hold
A single alphanumeric character or special symbol
What do strings hold
Multiple alphanumeric or special symbols
What do booleans hold
The value 0 or 1 sometimes represented by False or True
Why do we use binary
Because computers can only represent values as on or off; because they are reliant on electricity. It is also very reliable ; the computer always receives the correct data.
Why doe we use hexadecimal(4)
Much easier to read than a long string of binary
Quicker to write and take up less space
Less chance of making an error while typing
Very easy to convert to and from binary
What is hexadecimal used for (4)
Colours
MAC addresses
Assembly languages
Machine Code
Define Bit
the smallest unit of data in a computer, holds either a 0 or a 1
Define nibble
A sequence of 4 bits
Define Byte
A sequence of 8 bits
How many bits are required to hold a value of 2^n or below
n
What are the prefixes for bytes
Kilobyte - kB - 10^3
Megabyte - MB - 10^6
Gigabyte - GB - 10^9
Terabyte - TB - 10^9
Kibibyte - kiB - 2^10
Mebibyte - Mib
How do character sets work
Each single alphanumeric and special character is represented by an individual binary value
What is ASCII?
7 bit character set that can hold 128 characters used mostly for english
What is extended ASCII
8 bit character set that can hold 256 characters with extra characters for different langauages
What is Unicode?
16 or 32 bit character set that can hold characters for many languages
What is the comparison operator for equal
==
What is the comparison operator for not equal
<> or !=
What is the comparison operator for greater than
>
What is the comparison operator for less than
<
What is the comparison operator for greater than or equal
> =
What is the comparison operator for less than or equal
<=
What happens when the result of a binary cacluation is greater than the assigned number of bits can hold
Binary overflow error
What is the range of values a binary number can hold with n digits
0 - 2^n -1
What is the most significant bit of a binary number
The first bit
What is sign and magnitude
Method where the most significant bit represents either + (0) or - (1)
Why is sign and magnitude not used
Normal arithmetic does not work properly when using it, meaning more complicated circuits would have to be designed
What is two’s complement?
Method by which the most significant bit is changed from positive to negative
How to convert a number to negative using twos complement
Traverse from right to left until you find the first 1, after this one flip the remaining bits
What is the range of a twos complement number with n bits
-(2^(n-1)) <-> 2^(n-1) -1
What is fixed point binary
Method of storing reals which uses a specified number of bits where the decimal point is fixed
Advantage of fixed point binary
Easier to process
Disadvantage of fixed point binary
Cannot represent the range or accuracy of numbers that may be required
How does the accuracy of a fixed point binary number vary with range
Inversely
What is floating point representation
A method where the decimal place in a number can vary based on the exponent.
What is the mantissa?
The part of a floating point number that holds the actual number
What is the exponent
The part of a floating point number that sets the position of the floating pint
How does floating point work
Floating point starts in between 1st and 2nd bit and exponent moves point to the right x times when the exponent is equal to x. If x is negative then to the left
What is normalisation
The process of moving the floating point to achieve the maximum level of precision for a given number of bits
How do we normalise
Make the first digit after the binary point a significant digit (e.g. 1 id msb is 0 and 0 if msb 1) and changing the exponent accordingly
What is bit manipulation
The changing of the values in a binary value using some sort of operation
Why are bits manipulated
Error detection and correction algorithms
Data encryption
Data compression
How can we manipulate bits
Shifts
Bitwise operations
What is a logical shift right
The shifting of bits to the right by one place, putting the least significant bit into the carry bit
What is a logical shift left
The shifting of bits to the right by one place, putting the most significant bit into the carry bit
What is the purpose of logical shifts
Right can be used to examine least significant bit
Right divides by 2 left multiplies by 2
What is the problem with logical shifts
Will not work with twos complement numbers as number may lose its negative nature
What is an arithmetic shift right
The shifting of bits to the right by one place, putting the least significant bit into the carry bit. The new msb is the value of the old msb
What is an arithmetic shift left
The shifting of bits to the left by one place, putting the second most significant bit into the carry bit to preserve the sign bit. A 0 fills on the left
What is a circular shift right
LSB moved into carry bit, carry bit moved into MSB
What is a circular shift left
MSB moved into carry bit, carry bit moved into LSB
When does and AND return true
when both inputs are true
When does an OR return true
When either or both inputs are true
When does a XOR return true
When either but not both inputs are true
When does a NOT return true
When the input is false
When does a NOT return false
When the input is true
What is a boolean mask
A set of numbers that is used with an original number and a boolean operator to set, clear or toggle the input of bits
What is an AND bitwise used for
Clear a particular bit, leaving others unchanged
What is an OR birwise used for
Set a particular bit leaving others unchanged
What is a XOR bitwise used for
Toggle a particular bit leaving others unchanged
What is an elementary data type
Data type that holds a single data value
What is a composite data type
Data type that can be constructed by compounding other data types
What is an abstract data type
A data type created by the programmer which is a logical description of how we view the data and possible operations
What is a queue
A First In First Out Data Structure. (FIFO)
Example uses of a queue
Output waiting to be printed
Characters typed on a keyboard are held in a queue on a keyboard buffer
What are the psuedocode methods of a queue
enqueue (item)
dequeue
isEmpty
isFull
size
What is the problem with non circular queues
Once the back of the queue is reached no more data can be added even if there are free spaces at the front of the queue
How does a circular queue work
Has a pointer to the start and end of the queue. When space is freed up at front of queue it becomes the back so more data can be added. Pointer is modded by maxsize such that it loops
What is a priority queue
A queue in which some items are allowed to jump the queue if they are determined to have a higher priority
What is a static data structure
One that is fixed in size e.g. array
What is a dynamic data structure
One that can grow and shrink by allocating or deallocating memory from the heap e.g. python list
What are the advantages of a queue
Simple to program
Predictable memory usage
What are the disadvantages of a queue
Fixed length
Single pass
Can’t reuse spaces
What are the advantages of a circular queue
Can reuse free spaces
What are the disadvantages of a circular queue
Slightly more complex to program
What are the advantages of a priority queue
Gives preference to more important items
What are the disadvantages of a priority queue
Additional processing required to keep order
When might a priority queue be used
Accident and emergency
What is the purpose of abstract data types
To be able to deal with more complex problems with more efficient problem solving methods
List psuedocode operations
isEmpty()
append(item)
remove(item)
count(item)
len(item)
index(item)
insert(pos, item)
pop()
pop(pos)
What is a linked list
A list of nodes or elements of a data connected by pointers with a starting point and a next free pointer at the front/back respectively
What is a stack
A stack is a Last in First out (LIFO) abstract data structure
Stack psuedocode methods
push(item)
pop()
isFull()
isEmpty()
peek()
size()
What is stack overflow?
Attempting to push to a stack that’s full
What is a call stack?
A system level data structure that provides the mechanism for passing parameters and return addresses to subroutines
What is stack underflow?
Attempting to pop from a stack that is empty
What is a hash table
A data structure that offers very fast insertion and searching.
how does a hash table work?
Stores items in it using a hashing algoritm to decide its address. This algorithm can then be used again on search data to find where it is stored
What is a collision in a hash table
When two pieces of data (primary keys) are assigned to the same address
How are collisions dealt with in a hash table
An address for the colliding data is found in reference to the original location, e.g. go right till there is a free space
What must be done in a hash table when an item is deleted
Item must be replaced by a dummy item or marker that will later be treated as a free space
What is a dictionary
An abstract data type made up of associated pairs, each pair has a key and value. Value is accessed via the key
How might a dictionary be used
A translation program
Other data structures maybe be implemented a s dictionary, e.g. trees
Ascii or unicode tables
What is a graph?
An abstract data structure representing complex relationships. A set of vertices or nodes connected by edges or arcs
What is an directed graph
One that does not have arrows on edges indicating direction
What is a weighted graph
A weighted graph is a graph that has a numerical value associated with each edge.
What is a directed graph
One that has arrows on its edges representing direction
How can a graph be represented
An agency matrix
An agency list
What is an adjacency matrix?
A table where each row and column represents a node. An item at [row,column] indicates a connection
What is an agency list
A list which stores nodes paired with a list of nodes they are connected to
What are the advantages of an adjacency matrix
Continent to work with
Adding edge is simple
What is the disadvantage of an adjacency matrix
A sparse graph with not many edges will leave most of the cells empty, wasting a lot of memory space
