1.4 Data Types, Data Structures and Algorithms Flashcards
What does AND (∧) mean?
A logical operator which returns TRUE (or 1) if and only when all inputs are TRUE (or 1)
What is ASCII?
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
What is binary?
A number system that only uses 1s and 0s to represent numbers (a base 2 system)
What is bitwise manipulation?
Operations perfomed on a set of bits
What is boolean?
A data type that can only store one of two possible values (1 or 0, TRUE or FALSE, etc.)
What is a character?
A data type for storing one letter, number or special character
What is Denary?
A number system that only uses 10 characters (0 to 9) to represent numbers (a base 10 system)
What are the 5 data types?
Character
Boolean
String
Integer
Real/Float
What is Floating Point Arithmetic?
Performing arithmetic operations on floating point numbers in binary
What is Hexadecimal?
A number system that only uses 16 characters (
0 to 9 and A to F) to represent the numbers (a base 16 system)
What is an integer?
A data type for storing whole numbers with no decimals, positive or negative
What does OR (V) mean?
A logical operator which returns TRUE (or 1) if and only if any one of the inputs are TRUE (or 1)
What is the primitive data type?
A basic built in data type provided by a programming language
What is a Real/Floating point?
A data type for storing numbers with decimal or fractional parts
What are the binary Shifts?
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
What is the String data type?
Used to store a sequence of alphanumeric characters or symbols, typically within quotation marks
What is Two’s Complement?
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
What is UNICODE?
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
What does XOR do?
A logical operator which returns TRUE or 1 when only one input is TRUE or 1
What are arrays?
A data structure for storing a finite, ordered set of data of the same data type within a single identifier
What is a Binary Search Tree?
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)
What is a Depth First Transversal?
A method of traversing an entire graph by travelling as far as possible along one route before backtracking and trying alternative unexplored routes
What is a Breadth First Transversal?
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
What is a Directed Graph?
A graph where the order of the vertices paired in an edge matter
The edges are one way
What is a graph?
A data structure consisting of a set of vertices/nodes connected by a set of edges/arcs
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.
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
What are Lists?
A data structure that stores a sequence of data values, each with a unique index
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
What are Stacks?
A last-in-first-out data structure
The last item added/pushed is the first to be removed/popped off
What are Records?
A data structure that stores a collection of fields which store data based on attributescan be did data type
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
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
What is an Undirected Graphs?
A graph where the order of the vertices paired in an edge does not matter
Their edges are bidirectional
What are the Association Laws?
A ∧ (B ∧ C) = (A ∧ B) ∧ C
A V (B V C) = (A V B) V C
What are Boolean expressions?
A combination of Boolean values and logical operators which evaluates to either TRUE or FALSE depending on the inputs
What is Boolean Logic?
A type of algebra with logical operators where all the values and expressions ultimately reduce to TRUE or FALSE
What are the Commutation Laws?
A ∧ B = B ∧ A
A V B = B V A
What are the De Morgan’s Laws?
¬(A V B) = ¬A ∧ ¬B
¬(A ∧ B) = ¬A V ¬B
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)
What is the Double Negation Law?
¬¬A = A
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
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
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
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
What are Logic Gate Diagrams?
A graphical method of representing Boolean expressions using the standard symbols for logic gates
Why do computers store data in binary?
Easier to process and takes up less space
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
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
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
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
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
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…
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
Why is decimal used?
Easiest to read and understand for humans
Each binary shift to the left or the right does what affect to the binary number?
Left = Doubling
Right = Halving
What is a mask?
A mask can be applied to binary numbers by combining them withy a logic gate
What happens when you mask the binary numbers below with an AND, OR and XOR gates?
00101011
10111011
AND = 00101011
XOR = 10010000
OR = 10111011
What is a character set?
A published collection of codes and corresponding characters which can be used by computers for representing text
How many different characters could be represented through ASCII?
0-127, so therefore 128
What else can you say about arrays, how do they start?
Zero indexed base
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.
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
Where are records typically found?
As a row in a file or in a database
What is the difference between lists and arrays?
List values are stored non-contiguously, lists can also store more than one data types
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
Checks if the list is empty
list.isEmpty()
Adds a new value to the
end of the list
list.append(value)
Removes the value the first time it appears in the list
list.remove(value)
Searches for a value in the
list
list.search(value)
returns length of list
list.length()
Returns the position of the item
list.index(value)
How to insert value into a list in a specific place
List.insert(position,value)
How to remove and return last value in list
list.pop()
How to remove and return specific value in list
List.pop(position)
What does immutable mean?
It cannot be changed, elements cannot be added or removed once it has been created
Cannot be changed at runtime.
Are tuples immutable or mutable?
Immutable
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
What does the data field contain?
The data field contains the value of the actual data which is part of the list
What does the pointer field contain?
The pointer field contains the address of the next item in the list.
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
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
What is a weighted graph?
A graph with costs added to each edge
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}
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 -
What are the advantages of adjacent matrix?
Convenient to work with due to quicker access times
Easy to add nodes
What are the disadvantages of adjacent matrix?
More space efficient for large, sparse networks
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
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
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
What does Stack.isEmpty() do?
Checks if the stack is empty
Works by checking the value of the top pointer
How to add a new value to end of stack
What does Stack.push(value) do?
return top value of stack
stack.peek()
Removes and returns the top value of the stack
stack.pop()
stack.isFull()
Checks if the stack if full and returns a Boolean value
Works by comparing stack size to the top pointer
Returns the size of the stack
stack.size()
When are queues commonly used?
Printers, keyboards and simulators
How can you select a field from a record using pseudocode?
recordName.fieldName
What is the difference between a tuple and an array?
Tuples are initialised using regular bracket instead of square brackets
What is the root node>
The node which doesn’t have any incoming nodes, at the top of the tree
What is a child node?
Any node which has an incoming edge
What is a parent node?
Any node which has outcoming edges
What is a subtree?
A section of the tree which consists of a parent and all the children of that parent
What is a leaf?
A nod which has no children
What is a collision? (hashing)
A collision is where two inputs result in the same hashed value
What does a good hashing algorithm have?
A low chance of collision
Fast
What is a linear queue?
a data structure consisting of an array
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
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
What does Queue. enQueue(value) do?
Adds a new item to the end of the queue
Increments the back pointer
What does Queue. deQueue() do?
Removes the item from the front of the queue
Increments the front pointer
What does Queue. isEmpty() do?
Checks if the queue if empty by comparing the front and back pointer
What does Queue. isFull() do?
Checks if the queue is full by comparing the back pointer and queue size
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
What is collision resolution?
When collisions occur and the item is typically placed in the next available location
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
What is a Node?
An item in the tree
What is a root?
A single node which does not have any incoming nodes, typically the node at the top of the tree
What is an Edge?
Connects two nodes together and is also known as a branch, or arc
What does the symbol v with a _ underneath it represent?
XOR Gate
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
What are the three logic circuits you need to be familiar wwith?
D-Type Flip Flops
Half Adders
Full Adders
When does the output of a D-Type Flip Flop change?
At a rising edge, the start of a clock tick
When are half adders used?
In digital circuits
When are full adders used?
ALUs
CPU registers
memory units
What is the purpose of a D-type flip flop?
To store the value of a single bit
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
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
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
Applications of linked lists
OS managing processor to store process blocks in a ready state and web browsers to navigate backwards and forwards
Linked list add
Adds a node to the linked list
Linked list delete
Removes a node from the linked list
Linked list next
Moves to the next item in the listL
inked list previous
Moves to the previous item in a doubly linked list
Linked list traverse
A linear search through the linked list
What is a binary tree
Each node has a max of 2 children
What are the two inputs for a d type flip flop
Control signal and a clock input
What is a d type flip flop
Logic circuit which can store the value of one bit
Image of a d type flip flop
WHere are d type flip flops used
memory circuits counters and shift registers
How are d type flip flops used in shift registers
Handle signals arriving on parallel lines at different times
Why is it important to use as few expressions as possible
What do tuples and lists have in common?
They both can have different data types
How does arrays get stored in memory?
In Contiguous memory
What does OR mask do
Change bits in a binary number to one
Function of AND mask
AND something with 0 it will turn it to 0 (masking out a bit )
Disadvantage of embedded OS
Difficult to update if required
What does list.search(value)
Returns true or false depending on whether the value is present in the list
