1.4 Data Types, Data Structures and Algorithms Flashcards
1
Q
What does AND (∧) mean?
A
A logical operator which returns TRUE (or 1) if and only when all inputs are TRUE (or 1)
2
Q
What is ASCII?
A
A character set used to represent alphanumeric characters or symbols as a set of 8 bits
1 check bit and 7 bits for the number
3
Q
What is binary?
A
A number system that only uses 1s and 0s to represent numbers (a base 2 system)
4
Q
What is bitwise manipulation?
A
Operations perfomed on a set of bits
5
Q
What is boolean?
A
A data type that can only store one of two possible values (1 or 0, TRUE or FALSE, etc.)
6
Q
What is a character?
A
A data type for storing one letter, number or special character
7
Q
What is Denary?
A
A number system that only uses 10 characters (0 to 9) to represent numbers (a base 10 system)
8
Q
What are the 5 data types?
A
Character
Boolean
String
Integer
Real/Float
9
Q
What is Floating Point Arithmetic?
A
Performing arithmetic operations on floating point numbers in binary
10
Q
What is Hexadecimal?
A
A number system that only uses 16 characters (
0 to 9 and A to F) to represent the numbers (a base 16 system)
11
Q
What is an integer?
A
A data type for storing whole numbers with no decimals, positive or negative
12
Q
What does OR (V) mean?
A
A logical operator which returns TRUE (or 1) if and only if any one of the inputs are TRUE (or 1)
13
Q
What is the primitive data type?
A
A basic built in data type provided by a programming language
14
Q
What is a Real/Floating point?
A
A data type for storing numbers with decimal or fractional parts
15
Q
What are the binary Shifts?
A
A bitwise manipulation where a set of bits are all moved by one place in a given direction, and the end bit may be taken as a carry or appended to the other end depending on the shift method
16
Q
What is the String data type?
A
Used to store a sequence of alphanumeric characters or symbols, typically within quotation marks
17
Q
What is Two’s Complement?
A
A method of storing negative numbers in binary
It involves flipping all the bits of the binary representation of the positive number and then adding 1
18
Q
What is UNICODE?
A
A character set that is a superset of ASCII
It is used to represent alphanumeric characters and symbols as an integer code point which is equal to that character’s ASCII code
19
Q
What does XOR do?
A
A logical operator which returns TRUE or 1 when only one input is TRUE or 1
20
Q
What are arrays?
A
A data structure for storing a finite, ordered set of data of the same data type within a single identifier
21
Q
What is a Binary Search Tree?
A
A tree where each node cannot have more then 2 children nodes
The right node and its descendants always have a greater value than the root node (first data item)
22
Q
What is a Depth First Transversal?
A
A method of traversing an entire graph by travelling as far as possible along one route before backtracking and trying alternative unexplored routes
23
Q
What is a Breadth First Transversal?
A
A method of traversing an entire graph by visiting all the neighbours of the first node before repeating the same with each neighbour in the order they were visited
24
Q
What is a Directed Graph?
A
A graph where the order of the vertices paired in an edge matter
The edges are one way
25
What is a graph?
A data structure consisting of a set of vertices/nodes connected by a set of edges/arcs
26
What is a Hash Table?
A data structure where a hashing algorithm calculates a value to determine where a data item is to be stored
The data item can then be directly accessed by recalculation, without any search
Uses an algorithm to determine storage location.
27
What are Linked Lists?
A data structure that stores an ordered sequence of data where each item is stored with a pointer to the next item
The items are not stored contiguously (in this same order) in memory
28
What are Records?
A data structure that stores a collection of fields which store data based on attributescan be did data type
29
What are Trees?
AA data structure that uses a set of linked nodes to form a hierarchical structure starting at a root node
Each node is a child/sub-node of a parent node
30
What are Tuples?
A data structure for storing an immutable, ordered set of data, which can be of different data types, within a single identifier
31
What is an Undirected Graphs?
A graph where the order of the vertices paired in an edge does not matter
Their edges are bidirectional
32
What are the Association Laws?
A ∧ (B ∧ C) = (A ∧ B) ∧ C
A V (B V C) = (A V B) V C
33
What are Boolean expressions?
A combination of Boolean values and logical operators which evaluates to either TRUE or FALSE depending on the inputs
34
What is Boolean Logic?
A type of algebra with logical operators where all the values and expressions ultimately reduce to TRUE or FALSE
35
What are the Commutation Laws?
A ∧ B = B ∧ A
A V B = B V A
36
What are the De Morgan's Laws?
¬(A V B) = ¬A ∧ ¬B
¬(A ∧ B) = ¬A V ¬B
37
What are the Distribution Laws?
A ∧ (B V C) = (A ∧ B) V (A ∧ C)
(A V B) ∧ (C V D) = (A ∧ C) V (A ∧ D) V (B ∧ C) V (B ∧ D)
38
What is the Double Negation Law?
¬¬A = A
39
What are D-Type Flip Flops?
A sequential logic circuit used to store a single bit
It has two stable states, which can be flipped between using an input signal
40
What are Full Adders?
A combination od two half adders that takes a carry bit and two other input bits and returns their sum and trhe new carry as two output bits
41
What are Half Adders?
A combinational arithmetic circuit that adds two numbers and produces a sum bit (S) and carry bit (C) as the output
42
What are Karnaugh Maps
A method of simplifying Boolean expressions by redrawing the truth table and applying a set of visual rules to obtain expressions wit (or close to) the minimum logical operators, as a sum of products
43
What are Logic Gate Diagrams?
A graphical method of representing Boolean expressions using the standard symbols for logic gates
44
Why do computers store data in binary?
Easier to process and takes up less space
45
Binary to decimal?
1101
Write out the binary number under powers of increasing 2...
2^3 2^2 2^1 2^0
1 1 0 1 = 13
8 + 4 + 1 = 13
46
Decimal to binary?
82
Write out the powers of 2 again, take away the greatest one possible till 0 is acquired.
82 - 64 = 18
18 - 16 = 2
2 - 2 = 0... done.
01010010
47
Hexadecimal to binary?
B2
Split up the hexadecimal..
B 2
B = 11 2 = 2
11 = 1011 2 = 0010 (convert to binary)
Then combine to make the full conversion = 10110010 = B2
48
Hexadecimal to decimal?
4C3
Same thing as binary to decimal, line up the hexadecimal number with the columns of increasing powers of 16...
16^2 16^1 16^0
4 C 3
4x256 + 12x16 + 3x1 = 1219
49
How can you tell if a floating point numbers in binary have been normalised?
They start with either...
01, for a positive number
10, for a negative number
50
Normalise the binary number 000110100101 which is a floating point number with an eight bit mantissa and a four bit exponent.
Mantissa = 01101000
Exponent = 0011
if you got this wrong check one note and revisit later on...
51
Why is hexadecimal used to represent data?
More compact so use less memory, so more numbers can be stored in computer systems. More user friendly representation of binary-coded values
52
Why is decimal used?
Easiest to read and understand for humans
53
Each binary shift to the left or the right does what affect to the binary number?
Left = Doubling
Right = Halving
54
What is a mask?
A mask can be applied to binary numbers by combining them withy a logic gate
55
What happens when you mask the binary numbers below with an AND, OR and XOR gates?
00101011
10111011
AND = 00101011
XOR = 10010000
OR = 10111011
56
What is a character set?
A published collection of codes and corresponding characters which can be used by computers for representing text
57
How many different characters could be represented through ASCII?
0-127, so therefore 128
58
What else can you say about arrays, how do they start?
Zero indexed base
59
How does a 3D array select an item? (pseudocode )
threeDimensionalArray = [[[12,8],[9,6,19]],[[241,89,4,1],[19,2]]]
print(threeDimensionalArray[0,1,2])
>> 19
Uses...
threeDimensionalArray[z,y,x], where z is the array number, y is the row number and x is the column number.
60
How does a 2D array select an item? (pseudocode )
twoDimensionalArray = [[123, 28, 90, 38, 88, 23, 47],[1, 23, 12,
14, 16, 29, 12]]
print(twoDimensionalArray)
>> [[23, 28, 90, 38, 88, 23, 47],
[ 1, 23, 12, 14, 16, 29, 12]]
print(twoDimensionalArray[1,3]) // Goes down and then across
>> 14
61
Where are records typically found?
As a row in a file or in a database
62
What is the difference between lists and arrays?
List values are stored non-contiguously, lists can also store more than one data types
63
What does it mean when data is stored in non-contiguous memory?
This means that they do not have to be stored next to one another in memory
64
Checks if the list is empty
list.isEmpty()
65
Adds a new value to the
end of the list
list.append(value)
66
Removes the value the first time it appears in the list
list.remove(value)
67
Searches for a value in the
list
list.search(value)
68
returns length of list
list.length()
69
Returns the position of the item
list.index(value)
70
How to insert value into a list in a specific place
List.insert(position,value)
71
How to remove and return last value in list
list.pop()
72
How to remove and return specific value in list
List.pop(position)
73
What does immutable mean?
It cannot be changed, elements cannot be added or removed once it has been created
Cannot be changed at runtime.
74
Are tuples immutable or mutable?
Immutable
75
Within a linked list what is each item called?
A node, containing a data field alongside another address called a link or a pointer field
76
What does the data field contain?
The data field contains the value of the actual data which is part of the list
77
What does the pointer field contain?
The pointer field contains the address of the next item in the list.
78
What do linked lists store the index of the first item in their list as?
The pointer which also points to the next available space
79
By the way that linked lists are stored, how does this affect their transversal? And how is it different to an array?
As items in linked lists are stored in a sequence, they can only be traversed in this order; an item cannot be directly accessed, as is possible in an array
80
What is a weighted graph?
A graph with costs added to each edge
81
What does an adjacency list look like and when is it used?
When computers can process graphs by using...
Adjacency List
A → {B:4, C:18, D:12}
B → {A:4, C:5, E:8}
C → {A:18, B:5, D:5}
D → {A:12, E:3}
E → {B:8, D:3}
82
What does an adjacency matrix look like and when is it used?
When computers can process graphs by using...
Adjacency Matrix
A B C D E
A - 4 18 12 -
B 4 - 5 - 8
C 18 5 - 5 -
D 12 - - - 3
E - 8 - 3 -
83
What are the advantages of adjacent matrix?
Convenient to work with due to quicker access times
Easy to add nodes
84
What are the disadvantages of adjacent matrix?
More space efficient for large, sparse networks
85
When are stacks typically used in computers?
used to reverse an action, such as to go back a page in web browsers
The ‘undo’ buttons
that applications widely make use of also utilise stacks
86
Can stacks be static or dynamic?
Both, where the maximum size required is known in advance, static stacks are preferred, as they are easier to implement and make more efficient use of memory
87
Where does the pointer point to in a stack?
Points to the top of the stack, where the next piece of data will be inserted
88
What does Stack.isEmpty() do?
Checks if the stack is empty
Works by checking the value of the top pointer
89
How to add a new value to end of stack
What does Stack.push(value) do?
90
return top value of stack
stack.peek()
91
Removes and returns the top value of the stack
stack.pop()
92
When are queues commonly used?
Printers, keyboards and simulators
93
How can you select a field from a record using pseudocode?
recordName.fieldName
94
What is the difference between a tuple and an array?
Tuples are initialised using regular bracket instead of square brackets
95
What is the root node>
The node which doesn't have any incoming nodes, at the top of the tree
96
What is a child node?
Any node which has an incoming edge
97
What is a parent node?
Any node which has outcoming edges
98
What is a subtree?
A section of the tree which consists of a parent and all the children of that parent
99
What is a leaf?
A nod which has no children
100
What is a collision? (hashing)
A collision is where two inputs result in the same hashed value
101
What does a good hashing algorithm have?
A low chance of collision
Fast
102
What is a linear queue?
a data structure consisting of an array
103
What do circular queues do that linear queues do not?
Once the queue’s rear pointer is equal to the maximum size of the queue, it can loop back to the front of the array and store values here, provided that it is empty
104
What are the advantages of using a circular queue instead of a linear queue?
They use space in an array more effectively, although they are harder to implement
105
What does Queue. enQueue(value) do?
Adds a new item to the end of the queue
Increments the back pointer
106
What does Queue. deQueue() do?
Removes the item from the front of the queue
Increments the front pointer
107
What does Queue. isEmpty() do?
Checks if the queue if empty by comparing the front and back pointer
108
What does Queue. isFull() do?
Checks if the queue is full by comparing the back pointer and queue size
109
What are hash tables normally used for?
Hash tables are normally used for indexing, as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored
110
What is collision resolution?
When collisions occur and the item is typically placed in the next available location
111
What does the hash function do?
The hash function takes in data (a key) and releases an output (the hash)
The role of the hash function is to map the key to an index in the hash table
112
What is a Node?
An item in the tree
113
What is a root?
A single node which does not have any incoming nodes, typically the node at the top of the tree
114
What is an Edge?
Connects two nodes together and is also known as a branch, or arc
115
116
What does the symbol v with a _ underneath it represent?
XOR Gate
117
When interpreting a Karnaugh Map, what sjhoykd you do first?
Highlight and try to group all the 1s in the map
Remember that overlapping top and bottom and sides is possible
118
What are the three logic circuits you need to be familiar wwith?
D-Type Flip Flops
Half Adders
Full Adders
119
When does the output of a D-Type Flip Flop change?
At a rising edge, the start of a clock tick
120
When are half adders used?
In digital circuits
121
When are full adders used?
ALUs
CPU registers
memory units
122
What is the purpose of a D-type flip flop?
To store the value of a single bit
123
When does a ripple adder come into play?
Because the full adders have a carry input, the circuits can be chained together to form what's known as a ripple adder
124
Difference between list and 1 d array
Lists are similar to 1D arrays and elements can be accessed in the
same way. The difference is that list values are stored non-contiguously. This means they
do not have to be stored next to each other in memory, as data in arrays is stored. Lists
can also contain elements of more than one data type, unlike arrays
125
What is the benefit of using a linked list that uses objects
any available memory can be used to store data as they do not have to be contiguously adjacent
126
Applications of linked lists
OS managing processor to store process blocks in a ready state and web browsers to navigate backwards and forwards
127
Linked list add
Adds a node to the linked list
128
Linked list delete
Removes a node from the linked list
129
Linked list next
Moves to the next item in the listL
130
inked list previous
Moves to the previous item in a doubly linked list
131
Linked list traverse
A linear search through the linked list
132
What is a binary tree
Each node has a max of 2 children
133
What are the two inputs for a d type flip flop
Control signal and a clock input
134
What is a d type flip flop
Logic circuit which can store the value of one bit
135
Image of a d type flip flop
136
WHere are d type flip flops used
memory circuits counters and shift registers
137
How are d type flip flops used in shift registers
Handle signals arriving on parallel lines at different times
138
Why is it important to use as few expressions as possible
139
What do tuples and lists have in common?
They both can have different data types
140
How does arrays get stored in memory?
In Contiguous memory
141
What does OR mask do
Change bits in a binary number to one
142
Function of AND mask
AND something with 0 it will turn it to 0 (masking out a bit )
143
Disadvantage of embedded OS
Difficult to update if required
144
What does list.search(value)
Returns true or false depending on whether the value is present in the list
145
146
Returns the size of the stack
stack.size()
147
stack.isFull()
Checks if the stack if full and returns a Boolean value
Works by comparing stack size to the top pointer
148
What are Stacks?
A last-in-first-out data structure
The last item added/pushed is the first to be removed/popped off
149
What are Queues?
A first in first out (FIFO) data structure
The first item added/pushed on to the queue is the first to be removed/popped off
150
What are Lists?
A data structure that stores a sequence of data values, each with a unique index
