1.4 Data types, data structures and algorithms Flashcards
What are the different types of data? (5)
-integer
-boolean
-real/floating point
-character
-string
What is an integer data type?
whole numbers (includes 0 and -ve numbers)
What is a boolean data type?
values which are restricted to true and false
What is a real/floating point data type?
+ and -ve numbers which can also be fractional/decimal numbers
What is a character data type?
a single symbol used by the computer
-include the letters A to Z, the numbers 0 to 9 and hundreds of symbols like % and £
What is a string data type?
a collection of characters
How are integers stored on computers? How does this work?
-stored using binary
-computers count in base 2
-0 is just to show an ‘empty space’ whereas the 1 shows the number which the integer will consist of [0= false, 1=true]
128 64 32 16 8 4 2 1
-the row above shows the place value of each digit of the number (remember computers count in base 2 e.g. 2^2, 2^3)
-if the binary code beneath consists of 1 then the integer will be made up of the place value above the 1
e.g.
128 64 32 16 8 4 2 1
0 1 0 0 1 1 0 1
64+ 8 +4 +1 = 77
Explain how we can convert the binary code into denary
128 64 32 16 8 4 2 1
0 1 0 0 1 1 0 1
-the row below is the binary code which can be converted into an integer by adding the numbers which have a value of 1
-in this case we add 64, 8, 4 and 1 as they have a place holder value of 1 which gives a number of 77
Explain how we can convert denary into binary code
-first step: find the largest power of two which is smaller than the number you’re converting, then write up the place values in power of 2 up to this power
e.g. , if we were converting the decimal 47 into binary, we would write out place values up to 32
32 16 8 4 2 1
-then, place a 1 or a 0 in each position so that the total adds up to 47 starting with the most significant bit (32)
-if we write a 1, then we subtract the place value from
our value and use the result for the next stage e.g. 47-32= 15
-as 16 is larger than 15 a 0 will be used as an empty space/false number so we move on to the next numbers and continue the steps until we reach the final bit and the number is complete
32 16 8 4 2 1
1 0 1 1 1 1
What are the four rules when adding binary code?
- when adding 0 + 0 it always gives a 0
- when adding a 0 + 1 it always gives a 1
- when adding 1 + 1 you carry the one to the next addition and instead place a zero
- when adding a 1 +1 + 1 you carry the one to the next addition and instead place a 1
How do we add binary code together?
-line up digits
-start from right hand side (least significant bit)
-add values from each column whilst following the rules
-if the value has an overflow error (having an extra digit at the end), write out the code with the extra digit noting the error
-convert value into denary to check if calculation is correct
What are the two methods which can represent negative numbers in binary?
-sign and magnitude
-two’s complement
Explain how sign and magnitude works
-equivalent of adding a + or - sign in front of a number
-binary can only use 0s and 1s, so instead we represent the signs using 0 as positive and 1 as negative.
e.g. [010101101] = 173
[110101101] = -173
How can we convert from sign and magnitude into denary and vice versa?
-same as converting normally from binary to denary and vice versa
-only difference is adding the sign at the end of the largest significant bit for binary and adding a +/- to a denary number
Explain how two’s complement works
-works by making the most significant bit negative e.g., the most significant bit, usually 128, represents -128
-add place values as normal
e.g.,
-128 64 32 16 8 4 2 1
1 1 1 1 1 0 0 1
so: -128 + 64 + 32 +16 + 8 +1= -7
How can we add binary numbers using two’s complement?
-flip the first number (all 0s turn to 1 and vice versa)
-add as a normal binary
What is hexadecimal?
makes use of the characters A-F to represent numbers 10-15
Show the conversions between denary and hexadecimal
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 <—-DENARY
0 1 2 3 4 5 6 7 8 9 A B C D E F <—-HEXADECIMAL
How do we convert hexadecimal into binary and vice versa?
B2
-split into two characters –> B 2
-convert both into denary –> 11 2
-convert denary into binary
-combine both binary sections into one
-for vice versa, split the binary into sections of 4 bits and do the opposite
How do we convert hexadecimal into denary and vice versa?
-first convert hexadecimal into binary
-convert binary into denary
-do opposite for vice versa
How can floating point numbers be shown in binary?
-can be split into two parts: mantissa and exponent
e.g., 6.63 x 10^-11
mantissa is 6.63 and exponent is -11
-the last bit next to the most significant bit shows the sign (remember 0 is positive and 1 is negative sign)
How does the mantissa and exponent work in binary?
-the mantissa is always taken to have the binary point (same as a decimal point)
[as the mantissa is considered a binary point the binary number e.g. 1100100111 becomes 1.100100111]
-the exponent is used to show the shift of how many places the decimal point moves and in which direction
-mantissa comes first then the exponent (which will also have the smaller bytes)
e.g. 6.63 x 10^-11
mantissa is 6.63 and the exponent is -11
so the decimal point will be shifted 11 times from the decimal point to give us 0.0000000000663
How do we convert the a floating point number into denary?
-convert exponent into denary using the normal method
-as the mantissa is considered a binary point the binary number e.g. 1100100111 becomes 1.100100111
-move the binary point the required number of places that the exponent gives (e.g. moving the binary point 5 places to the right of the mantissa)
-this mantissa can then be converted to the denary version
[REMEMBER for the place values in decimal, the computer counts in base 2s so it goes on as 2^-1, 2^-2 etc)
[REMEMBER WITH TWO’S COMPLEMENT IF THE INIRIAL BIT IS A NEGATIVE THE MOST SIGNIFICANT PLACE VALUE IS A NEGATIVE]
e.g.
32 16 8 4 2 1 . 0.5 0.25 0.125 0.0625
1 1 0 0 1 0 . 0 1 1 1
32 + 16 + 2 + 0.25 + 0.125 + 0.0625 = 50.4375
Give the decimal place values for binary. Explain how we get these numbers
0.5
0.25
0.125
0.0625
[REMEMBER for the place values in decimal, the computer counts in base 2s so it goes on as 2^-1, 2^-2 etc)
What does it mean if we normalise floating point numbers? What is shown to present a floating point number as normalised?
-making them precise as possible in a given number of bits
-to normalise a binary number, adjust it so that it starts 01 for a positive number or 10 for a negative number
How can we normalise a floating point number?
-check if it is a positive or negative number
-split the number into its mantissa and exponent
-adjust the mantissa so it starts in 01 (for +) or 10 (for -)
-to adjust the mantissa to create a normalised number, move bits to the required number to the left and add zeros to the end of the mantissa
-then adjust the exponent so you still remain with the same number (as we move the bits to the left the mantissa becomes larger so we need to reduce the exponent by the number of bits moved)
e.g. if we move the bits two places to the left we subtract the exponent by two and replace it with what has been left
—–> 5 - 2 = 3 so the new exponent would be three
How do we add floating point numbers?
-the exponents need to be the same
-add mantissa’s together
-normalise answer if needed
if the exponents are not the same, they need to be modified to match
-to do this, we shift the bits of the mantissa to the right to the needed number of places until the exponent is modified to match the other (same as when we normalise)
How can we subtract floating point numbers?
-make exponents the same
-the number which will be subtracted from the first needs to be flipped (converted to two’s complement)
-add both numbers together
-normalise answer if needed
if the exponents are not the same, they need to be modified to match
-to do this, we shift the bits of the mantissa to the right to the needed number of places until the exponent is modified to match the other (same as when we normalise)
What is a logical shift?
involves moving all of the bits in a binary number a specified number of places to the right or to the left
What happens to the number if a logical shift occurs?
multiplication (or division if shifting right) by two to the
power of the number of places shifted
What are the different masks that can be applied to binary calculations?
AND
OR
XOR
What does the AND mask do to a binary calculation?
all values must be true (1= true, 0 = false)
e.g.
if a calculation involves 1 and 0 the result would be 0
if a calculation involves 1 and 1 the result would be 1
if there is a false then the answer would be false
What does the OR mask do to a binary calculation?
only one value needs to be true (1= true, 0 = false)
e.g.
if a calculation involves 1 and 0 the result would be 1
What does the XOR mask to do a binary calculation?
works the same as OR where the result is true if the calculation consists of 1 (1= true, 0 = false)
both values cannot be the same: the value must consist of 1 and 0
What is a character set?
a published collection of codes and corresponding characters which can be used by computers for representing text
What are two types of character sets?
ASCII
Unicode
Describe the ASCII character set
-stands for American Standard Code for Information Interchange
-7 bits to represent 2^7 = 128 different characters
-capital letters A-Z are represented by codes 65-90 while the lower case letters a-z correspond to codes 97-122
What is one issue that arose from using ASCII? What was used to fix this?
-became a disadvantage when computers needed to represent other languages with different characters
-Unicode was introduced to solve this
Describe the Unicode character set
-uses a varying number of bits allowing for over 1 million different characters
-has enough capacity to represent a wealth of different languages, symbols and emoji
What is an array? Describe its characteristics
-a data structure
-an ordered, finite set of elements of a single data type
-usually zero indexed unless told otherwise
can be 1D, 2D, 3D
What can a 1 dimensional array be called? Give an example
a linear array
e.g.
oneDimensionalArray = [1, 23, 12, 14, 16, 29, 12] //creates a
1D array
print(oneDimensionalArray[3])
» 14
Describe a 2 dimensional array. Give an example
-can be visualised as a table or spreadsheet
-when searching through a 2D array, you first go down the rows and then across the columns to find a given position
e.g.
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
Describe a 3 dimensional array. Give an example
-can be visualised as a multi-page spreadsheet and can be
-in a 3D array requires the following syntax to be used: threeDimensionalArray[z,y,x], where z is the array number, y is the row number and x is the column number
e.g.
threeDimensionalArray = [[[12,8],[9,6,19]],[[241,89,4,1],[19,2]]]
print(threeDimensionalArray[0,1,2])
» 19
What is a record?
-a data structure
-commonly referred to as a row in a file
-made up of fields
What is a list?
-a data structure consisting of a number of ordered items where the items can occur more than once
-list values are stored non-contiguously (means they
do not have to be stored next to each other in memory)
-can also contain elements of more than one data type
What are the different operations used for lists? (9)
isEmpty()
append(value)
remove (value)
search(value)
length()
index(value)
insert(position, value)
pop()
pop(position)
What are the two differences between an array and a list?
-lists store data non-contiguously whereas arrays store data in order
-lists can store more than 1 data type
What does the isEmpty() command do for a list? Give an example
checks if the list is empty
List.isEmpty()
» False
What does the append(value) command do for a list? Give an example
adds a new value to the end of the list
List.append(15)
»
What does the remove(value) command do for a list? Give an example
removes the value the first time it appears in the list
List.remove(23)
»
What does the search(value) command do for a list? Give an example
searches for a value in the list
List.search(38)
» False
What does the length() command do for a list? Give an example
returns the length of the list
List.length()
» 7
What does the index(value) command do for a list? Give an example
returns the position of the item
List.index(23)
» 0
What does the insert(position, value) command do for a list? Give an example
inserts a value at a given position
List.insert(4,25)
»
What does the pop() command do for a list? Give an example
returns and removes the last value in the list
List.pop()
»12
What does the pop(position) command do for a list? Give an example
returns and removes the value in the list at the given position
list.pop(3)
What is a tuple?
-a data structure
-an ordered set of values of any type is called a tuple
-a tuple is immutable (cannot be changed)
-uses normal brackets instead of square
How can a tuple be accessed? Give an example
-accessed in the same way as an array
tupleExample = (“Value1”, 2, “Value3”)
print(tupleExample[0])
» Value1
What are two differences between a tuple and an array?
-elements cannot be added or removed once it has been created (will result in a syntax error)
-initialised using regular brackets instead of square brackets
What is a linked list?
a dynamic data structure used to hold an ordered sequence which are not stored in contiguous locations
What is each item in a linked list called?
nodes
What does each node in a linked list contain?
contains a field data and an address field called link/pointer
What is a data field in a linked list?
a field that stores the actual data
What is the pointer field in a linked list?
a field that contains the address of the next node in the list
How does a linked list work? Give an example
Index Data Pointer
0 ‘Linked’ 2
1 ‘Example’ 0
2 ‘List’ -
3
Start = 1 NextFree=3
to start, the algorithm will provide a start pointer (1) as well as the next free space (3)
-start with 1, to get ‘example’ as the first data item
-the pointer is showing to go to index 0 which outputs the values at each node
-this then gives a pointer to index 2 which gives the next value
-this doesn’t have another pointer as there is no other value occupying the next available space
by following the algorithm we end up with ‘example’ , ‘linked’ , ‘list’
What is one advantage of using a linked list? How does this work? Give an example
values can easily be added or removed by editing pointers
adding:
done by adding the value at the end of the linked list and updating the pointer
e.g.
index data pointer
3 ‘OCR’
4
Start = 1 NextFree=4
removing:
rearrange the pointers so that the value wanting to e removed wont be called upon and therefore not in use
e.g.
index data pointer
0 ‘Linked’ 2
1 ‘Example’ 2
2 ‘List’ -
this will leave out ‘linked’ and instead give ‘example’ , ‘list’
-if needed, update other pointers so the algorithm works properly without any mix up of values
What is one disadvantage when trying to remove a value from a linked list?
the value isn’t fully removed, only ignored which wastes memory
What are two differences between a linked list and an array?
-storing pointers means more memory is required
compared to an array
-as items in linked lists are stored in a sequence, they can only be transported in this order so an item cannot be directly accessed, as is possible in an array
What is a graph?
-a data structure
-a set of vertices/nodes connected by edges/arcs
What are the three categories of graphs? Describe them
directed graph: the edges can only be traversed in one direction
undirected graph: the edges can be traversed in both directions
weighted graph: a cost is attached to each edge
How can computers process graphs?
by using an adjacency matrix or an adjacency list
What are positives of an adjacency matrix and an adjacency list?
adjacency matrix:
-convenient to work with due to quicker access times
-easy to add nodes
adjacency list:
-more space efficient for large, sparse networks
What is a stack? How does it work?
-a last in first out (LIFO) data structure
-items can only be added to or removed from the top of the stack
Give two examples of where stacks may be used?
-back button in a web page
-undo button
How are stacks implemented?
implemented using a pointer which points to the top of the stack, where the next piece of data will be inserted
What are the two data structures stacks can be used as? Which is preferred and why?
-implemented as either a static structure or a dynamic structure
-when maximum size is required, static stacks are preferred, as they are easier to implement and make more efficient use of memory
What are the 6 types of stack operations?
isEmpty()
push(value)
peek()
pop()
size()
isFull()
What does the isEmpty() command do for a stack? Give an example
-checks if the stack is empty
-works by checking the value of the top pointer
Stack.isEmpty()
» True
What does the push(value) command do for a stack? Give an example
-adds a new value to the end of the list
-needs to check that the stack is not full before pushing to the stack
Stack.append(“Nadia”)
»
Stack.append(“Elijah”)
»
What does the peek() command do for a stack? Give an example
-returns the top value from the stack
-first checks the stack is not empty by looking at value of top pointer
Stack.peek()
» “Elijah”
What does the pop() command do for a stack? Give an example
-removes and returns the top value of the stack
-first checks the stack is not empty by looking at value of top pointer
Stack.pop()
» “Elijah”
What does the size() command do for a stack? Give an example
returns the size of the stack
Stack.size()
» 2
What does the isFull() command do for a stack? Give an example
-checks if the stack if full and returns a Boolean value
-works by comparing stack size to the top pointer
Stack.isFull()
» False
What is a queue? How does it work?
-a first in first out (FIFO) data structure
-items are added to the end of the queue and are removed from the front of the queue
Give three examples of where queues may be used in
-printers
-keyboards
-simulators
What is a linear queue? How does it work?
-a data structure consisting of an array
-items are added into the next available space in the queue, starting from the front
-items are removed from the front of the queue
How are pointers used in a queue?
-make use of two pointers
-one pointing to the front of the queue
-one pointing to the back of the queue, where the next item can be added
Why can a linear queue be ineffective to use? How can we fix this?
-as the queue removes items, there are addresses in the array which cannot be used again
-this makes a linear queue an ineffective implementation
-use a circular queue to fix this
What is a circular queue? How does it work to fix the issue with a linear queue?
-a queue which operates in a similar way to a linear queue in that it is a FIFO structure
-coded in a way that 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
-therefore, circular queues can use space in an array more effectively
What are the four different stack commands?
enQueue(value)
deQueue()
isEmpty()
isFull()
What does the enQueue(value) command do? Give an example
-adds a new item to the end of the queue
-increments the back pointer
Queue.enQueue(“Nadia”)
»
Queue.enQueue(“Elijah”)
»
What does the deQueue() command do? Give an example
-removes the item from the front of the queue
-increments the front pointer
Queue.deQueue()
»
What does the isEmpty() command do for a queue? Give an example
checks if the queue if empty by comparing the front and back pointer
Queue.isEmpty()
» False
What does the isFull() command do for a queue? Give an example
checks if the queue is full by comparing the back pointer and queue size
Queue.isFull()
» False
What is a tree?
-a data structure
-has a root node and child node which are connected by branches
-is a connected form of a graph
What is a node (for a tree data structure)?
an item in the tree
What is an edge (for a tree data structure)?
connects two nodes together and is also known as a branch, or arc
What is a root (for a tree data structure)?
a single node which does not have any incoming nodes
What is a child (for a tree data structure)?
a node with incoming edges
What is a parent (for a tree data structure)?
a node with outgoing edges
What is a subtree?
subsection of a tree consisting of a parent and all the children of a parent
What is a leaf (for a tree data structure)?
a node with no children
What is a binary tree? What are they used for?
-a type of tree where each node has a maximum of two children
-used to search for values quickly such as representing information for binary searches
What are the three ways we can traverse through a binary tree?
-pre-order
-in-order
-post-order
How does pre-order traversing work?
-follows the order: root node, left subtree, then right subtree
-nodes are traversed in the order in which you pass them on the
left, beginning at the left-hand side of the root node
How does in-order traversing work?
-follows the order: left subtree, root node, right subtree
-nodes are traversed in the order in which you pass under them,
beginning at the first node from the left which does not have two child nodes
How does post-order (depth first) traversing work?
- follows the order: left subtree, right subtree, root node
-nodes are traversed in the order in which you pass them on the
right
What is a hash table?
-an array which is coupled with a hash function
How does a hash table work?
-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
What is a collision (hashing)? How can we solve this issue?
-two keys producing the same hashed value
-if this occurs, the item is typically placed in the next available location
What properties does a good hashing algorithm have?
-has a low chance of collision
-must be fast
How can problems in boolean equations be solved?
by using boolean logic
What are the only two solutions a boolean equation can equate to?
true or false
What are the four operations which can be used for boolean equation?
-conjunction (AND)
-disjunction (OR)
-negation (NOT)
-exclusive disjunction (XOR)
What is the symbol for conjunction? What can it also be called?
also known as AND
What is the symbol for disjunction? What can it also be called?
v
also known as OR
What is the symbol for negation? What can it also be called?
¬
also known as NOT
What is the symbol for exclusive disjunction? What can it also be called?
⊻
also known as XOR
Draw a diagram showing all the logic gates for the four operations
https://spinningnumbers.org/i/logic11.svg
What is a truth table? How are the inputs and outputs represented?
-a table showing every possible arrangements of inputs to a logic gate and the corresponding output
-inputs are usually labelled A, B, C etc
-1 represents True, 0 represents False
How are boolean equations made? Give an example and explain how to solve it
made by combining boolean operators
-e.g. ¬(A ^ (B v C))
-first do the equation in the first bracket—> B v C
-work out the next bracket—> A ^ (B v C)
-then apply the negation to the answer
-this could be carried out using truth tables
How can we simplify boolean expressions?
by using karnaugh maps
How do karnaugh maps work?
-they create tables filled corresponding to the expression’s truth table
-can be used for a truth table with two, three or four variables
-use the bits for each column and row and apply the operation
How can we simplify an expression using a karnaugh map? Show an example
-first write your truth table as a Karnaugh map
-then highlight all of the 1s in the map with a rectangle
-the larger the rectangle you can highlight at once the better
-only groups of 1s with edges equal to a power of 2 (1, 2 or 4 in a row) can be highlighted, wraparound is included
-remove variables which change within these rectangles from the expression
-keep variables which do not change, but negate to become True if required
https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcROPkC5L7D_3lwHMAcnkYks-WVR7mfrPeMbWA&usqp=CAU
What are the four laws to simplify boolean algebra?
-De Morgan’s Laws
-distribution
-association
-commutation
-double negation
How does De Morgan’s Law work and when is it used? Give an example
-involve breaking UP negation (NOT) and changing the operator between two literals
-used when negation (NOT) applies to the whole of the operator between the two literals
-the AND symbol would also be replaced by the OR symbol and vice versa
e.g. ¬(A ^ B) == ¬A v ¬B
¬(A v B)== ¬A ^ ¬B
How does distribution work and when is it used? Give an example
-applies when conjunction (AND) is used with another operator that contains disjunction (OR) and vice versa
-can also be used with the same operator
e.g. A ^ (B v C) == (A ^ B) v (A ^ C)
A v (B ^ C) == (A v B) ^ (A v C)
How does association work? Give an example
-involves the addition or removing of brackets and reordering of literals in a boolean expression
e.g. (A ^ B) ^ C == A ^ B ^ C
(A v B) v C == A v B v C
How does commutation work? Give an example
-shows that the order of literals around an operation do not matter
e.g. A v B == B v A
A ^ B == B ^ A
How does double negation work? Give an example
-if negation on a literal is used twice, they cancel out and remain the same truth value
e.g. ¬¬A == A
What are three types of logic circuits?
-D-type flip flops
-half adders
-full adders
Describe what a D-type flip flop is
-a type of logic circuit which can store the value of one bit
-has two inputs, a control signal and a clock input (a regular pulse generated by the CPU to coordinate the computers’ components)
How does a D-type flip flop circuit work? Draw a diagram
-clock pulse rises and falls
-edges can be classified rising or falling
-the output of a D-type flip flop can only change at a rising edge, the start of a clock tick
-uses four NAND gates
-updates the value of Q to the value of D whenever the clock (CLK) rises
-the value of Q is the stored value
e.g.
https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2017/01/D-logic-diag.png
Describe what an adder is
-a logic circuit which adds together the number of inputs which are true and outputs the number in binary
How does a half adder work? Draw a diagram
-has two inputs, A and B
-has two outputs, Sum and Carry
-formed from two logic gates: AND and XOR
-when both A and B are False, both outputs are False
-when one of A or B is True, Sum (S) is True
-when both inputs are True, Carry (C) is True
e.g.
https://media.geeksforgeeks.org/wp-content/uploads/20201009113450/outputonlinepngtools3.png
https://www.techopedia.com/wp-content/uploads/2023/03/9097e01b7bfd4e8dbf671dcfa129beae.png
How does a full adder work? Draw a diagram
-similar to a half adder, but has an additional input
-allows carry in to be represented
-formed from two XOR gates, two AND gates and an OR gate
can be chained together to form a ripple adder with many inputs
e.g.
https://www.watelectronics.com/wp-content/uploads/Full-Adder-Truth-Table.jpg
https://circuits-diy.com/wp-content/uploads/2021/08/full-adder-circuit.png
