1.4 Data types, structures and algorithms Flashcards
1
Q
What is a primitive data type
A
Basic type is a data type provided by a programming language as a basic building block
2
Q
What are the common primitive data types (5)
A
Integer
Floating point/ real
Character
String
Boolean
3
Q
What do integers hold
A
Whole numbers
4
Q
What do floating points/ reals hold
A
A number with a fractional part
5
Q
What do characters hold
A
A single alphanumeric character or special symbol
6
Q
What do strings hold
A
Multiple alphanumeric or special symbols
7
Q
What do booleans hold
A
The value 0 or 1 sometimes represented by False or True
8
Q
Why do we use binary
A
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.
9
Q
Why doe we use hexadecimal(4)
A
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
10
Q
What is hexadecimal used for (4)
A
Colours
MAC addresses
Assembly languages
Machine Code
11
Q
Define Bit
A
the smallest unit of data in a computer, holds either a 0 or a 1
12
Q
Define nibble
A
A sequence of 4 bits
13
Q
Define Byte
A
A sequence of 8 bits
14
Q
How many bits are required to hold a value of 2^n or below
A
n
15
Q
What are the prefixes for bytes
A
Kilobyte - kB - 10^3
Megabyte - MB - 10^6
Gigabyte - GB - 10^9
Terabyte - TB - 10^9
Kibibyte - kiB - 2^10
Mebibyte - Mib
16
Q
How do character sets work
A
Each single alphanumeric and special character is represented by an individual binary value
17
Q
What is ASCII?
A
7 bit character set that can hold 128 characters used mostly for english
18
Q
What is extended ASCII
A
8 bit character set that can hold 256 characters with extra characters for different langauages
19
Q
What is Unicode?
A
16 or 32 bit character set that can hold characters for many languages
20
Q
What is the comparison operator for equal
A
==
21
Q
What is the comparison operator for not equal
A
<> or !=
22
Q
What is the comparison operator for greater than
A
>
23
Q
What is the comparison operator for less than
A
<
24
Q
What is the comparison operator for greater than or equal
A
> =
25
What is the comparison operator for less than or equal
<=
26
What happens when the result of a binary cacluation is greater than the assigned number of bits can hold
Binary overflow error
27
What is the range of values a binary number can hold with n digits
0 - 2^n -1
28
What is the most significant bit of a binary number
The first bit
29
What is sign and magnitude
Method where the most significant bit represents either + (0) or - (1)
30
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
31
What is two's complement?
Method by which the most significant bit is changed from positive to negative
32
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
33
What is the range of a twos complement number with n bits
-(2^(n-1)) <-> 2^(n-1) -1
34
What is fixed point binary
Method of storing reals which uses a specified number of bits where the decimal point is fixed
35
Advantage of fixed point binary
Easier to process
36
Disadvantage of fixed point binary
Cannot represent the range or accuracy of numbers that may be required
37
How does the accuracy of a fixed point binary number vary with range
Inversely
38
What is floating point representation
A method where the decimal place in a number can vary based on the exponent.
39
What is the mantissa?
The part of a floating point number that holds the actual number
40
What is the exponent
The part of a floating point number that sets the position of the floating pint
41
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
42
What is normalisation
The process of moving the floating point to achieve the maximum level of precision for a given number of bits
43
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
44
What is bit manipulation
The changing of the values in a binary value using some sort of operation
45
Why are bits manipulated
Error detection and correction algorithms
Data encryption
Data compression
46
How can we manipulate bits
Shifts
Bitwise operations
47
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
48
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
49
What is the purpose of logical shifts
Right can be used to examine least significant bit
Right divides by 2 left multiplies by 2
50
What is the problem with logical shifts
Will not work with twos complement numbers as number may lose its negative nature
51
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
52
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
53
What is a circular shift right
LSB moved into carry bit, carry bit moved into MSB
54
What is a circular shift left
MSB moved into carry bit, carry bit moved into LSB
55
When does and AND return true
when both inputs are true
56
When does an OR return true
When either or both inputs are true
57
When does a XOR return true
When either but not both inputs are true
58
When does a NOT return true
When the input is false
59
When does a NOT return false
When the input is true
60
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
61
What is an AND bitwise used for
Clear a particular bit, leaving others unchanged
62
What is an OR birwise used for
Set a particular bit leaving others unchanged
63
What is a XOR bitwise used for
Toggle a particular bit leaving others unchanged
64
What is an elementary data type
Data type that holds a single data value
65
What is a composite data type
Data type that can be constructed by compounding other data types
66
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
67
What is a queue
A First In First Out Data Structure. (FIFO)
68
Example uses of a queue
Output waiting to be printed
Characters typed on a keyboard are held in a queue on a keyboard buffer
69
What are the psuedocode methods of a queue
enqueue (item)
dequeue
isEmpty
isFull
size
70
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
71
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
72
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
73
What is a static data structure
One that is fixed in size e.g. array
74
What is a dynamic data structure
One that can grow and shrink by allocating or deallocating memory from the heap e.g. python list
75
What are the advantages of a queue
Simple to program
Predictable memory usage
76
What are the disadvantages of a queue
Fixed length
Single pass
Can't reuse spaces
77
What are the advantages of a circular queue
Can reuse free spaces
78
What are the disadvantages of a circular queue
Slightly more complex to program
79
What are the advantages of a priority queue
Gives preference to more important items
80
What are the disadvantages of a priority queue
Additional processing required to keep order
81
When might a priority queue be used
Accident and emergency
82
What is the purpose of abstract data types
To be able to deal with more complex problems with more efficient problem solving methods
83
List psuedocode operations
isEmpty()
append(item)
remove(item)
count(item)
len(item)
index(item)
insert(pos, item)
pop()
pop(pos)
84
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
85
What is a stack
A stack is a Last in First out (LIFO) abstract data structure
86
Stack psuedocode methods
push(item)
pop()
isFull()
isEmpty()
peek()
size()
87
What is stack overflow?
Attempting to push to a stack that's full
88
What is a call stack?
A system level data structure that provides the mechanism for passing parameters and return addresses to subroutines
88
What is stack underflow?
Attempting to pop from a stack that is empty
89
What is a hash table
A data structure that offers very fast insertion and searching.
90
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
91
What is a collision in a hash table
When two pieces of data (primary keys) are assigned to the same address
92
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
93
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
94
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
95
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
96
What is a graph?
An abstract data structure representing complex relationships. A set of vertices or nodes connected by edges or arcs
97
What is an directed graph
One that does not have arrows on edges indicating direction
98
What is a weighted graph
A weighted graph is a graph that has a numerical value associated with each edge.
99
What is a directed graph
One that has arrows on its edges representing direction
100
How can a graph be represented
An agency matrix
An agency list
101
What is an adjacency matrix?
A table where each row and column represents a node. An item at [row,column] indicates a connection
102
What is an agency list
A list which stores nodes paired with a list of nodes they are connected to
103
What are the advantages of an adjacency matrix
Continent to work with
Adding edge is simple
104
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
105
