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)
»
