1.4 - Data types, data structures and algorithms Flashcards
What is a data type?
It is the classification of data telling the computer how the computer will use the data.
What is an integer?
Any positive/negative whole number.
What is a real/float?
Any real world quantity expressed as a number (decimals).
What is boolean?
Used to represent one of two truth values (True/False)
What is a character?
Represents a single character, alphanumeric/symbol.
What is a string?
A collection of characters.
What is casting data types?
Changing data types
What is a primitive data type?
A basic data type.
What base in binary?
Base 2 = 01
What base is denary?
Base 10 0-9
What base is hexadecimal?
Base 16 0-9, A-F
What are the 5 positives of hexadecimal?
- Values easier to remember/read than binary.
- Quicker to write, less characters.
- Less chance of eror when typing hex.
- Defines colours, MAC addresses, in assembly languages/machine code.
- Easy to convert to/from Binary.
How do you use sign + magnitude?
(Negative numbers in binary)
The most significant number represents whether the number is positive (= 0)/negative (=1).
How do you use two’s compliment?
(Negative numbers in binary)
The most significant number represents whether the number is positive (= 0)/negative (=1). Then all the numbers afterwards (until the last 1 (1 closest to the end)) are switched to the opposite value.
How do you convert from Denary to Binary?
Put in place value to add to make total of the number.
e.g. 99 = 01100011
128/64/32/16/8/4/2/1
0 1 1 0 0 0 1 1
How do you convert from Hexadecimal to Denary
Do the rule of place values. 256 16 1 time number based on plate.
How do you convert from Denary to Hexadecimal?
Divide number by 16 and add remainder.
e.g. 43/16 = 2 + 11 = 2B
(11 = remainder in the example)
How do you convert from Binary to Hexadecimal?
Divide binrary number into 2 (2 x 4 digits)= 0011 1100 (Use 8421 place values) and then add to make up the 2 hex digits.
What is a bit?
An individual digit in a binary value.
Used to represent ON + OFF voltage signals om a computer.
What is a byte
- 8 Bits grouped together.
- Can group 2 or more bytes together to hold larger values.
What is a fixed bit?
extra zeros that pad the data at the front. So that the binary can be a full byte.
How big is a Kilobyte?
10^3 = 1,000 bytes
KB = Kilobyte
How big is a Megabyte?
10^6 = 1,000,000 Bytes
MB = Megabyte
How big is a Gigabyte?
10^9 = 1,000,000,000 Bytes
GB = Gigabyte
How big is a Terabyte?
10^12 = 1,000,000,000,000 Bytes
TB = Terabyte
How big is Kibibyte?
2^10 = 1,024 Bytes
KiB = Kibibyte
How big is a Mebibyte?
2^20 = 1,048,576
MiB = Mebibyte
How big is a Gibibyte?
2^30 = 1,073,741,824
GiB = Gibibyte
How big is a Tebibyte?
2^40 = 1,099,511,627,776
TiB = Tebibyte
What is ASCII?
- American Standard Code for Information Interchange.
- Established in 1963 to encode symbols found in the english Alphabet.
- 7 bit = 2^7 = 128 possible binary codes
How does ASCII work?
- Every single character on the keyboard is represented by a binary value.
- 1st 32 codes are control characters e.g. Backspace / Enter
- 8th bit introduced later for extra characters. e.g. ©️
What is the purpose of Unicode?
- Introduced to standardise the encoding of characters of all languages.
- Either apply the variable length of 16 bits or 32 bits encoding.
- 1st 128 characters same as ASCII, to improve the adoption of it.
- Every single character in every single language, mathematic + scientific can be represented.
What are the binary addition number rules?
- 1+1 = 0 carry 1
- 1 + 1 + 1= 1 carry 1
- 0 + 0 = 0
What is an overflow error?
The result of an addition is too large for the number of bits the computer works with.
What determines the calculating range?
No. bits determines how many values can be represented in binary.
How much of the range of values can represent the binary values?
- Positive = the full range.
- Negative = half the range.
Max for 8 bit = 127↓10 = 0111 1111
Min for 8 bit = -128↓20 = 1000 0000
How do you do binary subtraction?
Turn the number you are subtracting into its negative form then add the two numbers together.
What are the 3 types of data?
- Elementary
- Composite
- Abstract
What are some examples of an elementary data type?
- e.g Char, Real, Integer, Boolean
What are Structured data types?
- Built in = Strings, Arrays, Lists, Records.
- Mainly made up of Elementary data types.
What is an array?
- An array is an ordered, finite set of elements of a single type
- They are zero indexed (First element at index 0)
- 1D array = linear e.g. [1]
What is a 2D array?
- 2 different indexes (Seperated by commas).
- Like a table e.g [0, 1]
What is a multidimensional array?
- Can define w any no. of dimensions.
- e.g. 3D = hold xyz coordinates, [x, y, z]
- e.g. 4D can hold the sales of branches of a supermarket by country/store/department/year, sales[c, s, d, y] = 23450
What are 4 features of Tuples?
- Ordered set of values.
- May have elements of mixed types.
- Immutable - elements cannot change.
- ## Doesn’t use square brackets.
What is a disadvantage of a tuple?
You can’t change it if there is a spelling error or add another element to a tuple.
An example of a tuple
Player ID, Lastname, Firstname, Score1, Score2, Score3
Player 1 = (34296, “Jones”, “Jane”, 125, 150, 137)
What are the 2 characteristics of a record?
- Composed of a fixed number of fields of different data types (Resembles a spreadsheet)
- Can be implemented as an object + treated like a tuple.
(In writing files: each record is usually written as a single line).
What is a static data type?
Cannot change size.
- Arrays in most languages don’t change size automatically.
- Some languages provide functions to resize, has to be programmed; not automatic.
What is a dynamic data type?
Change size when required.
- Array lists/lists grow when items are added + shrink when items are removed.
What is a abstract data type?
(ADT)
- Logical description of how we view the data and possible operation.
- Only concerned with what the data is representinig not how it is constructed.
- e.g. a tree
What principle does a queue follow?
- The FIFO (first in, first out) principle
What are the 4 stages of a queue?
- Add item to the rear of the queue.
- Remove the item from the front of the queue.
- Check if the queue is empty.
- Check if the queue is full.
What are 2 features of a queue?
- Can’t add to a full queue or take away from an empty queue.
- When initialising a queue specify max no. it can hold, e.g. maxsize. May be necessary to have a variable size to hold the number of items currently in the queue.
What are the 4 queue functions/methods?
- enQueue(item) - add an item to the rear.
- deQueue - remove and return an item from the front.
- isEmpty - indicates if the queue is empty.
- isFull - indicates if the queue is full.
What principle does a stack follow?
- The LIFO (last in first out) principle.
What is a stack?
A data structure where new items added to the top of the stack and items are removed from the top of the stack.
- Order of insertion opposite to order of removal.
- e.g. [R,O,B,E,R,T] -> [T,R,E,B,O,R]
What is the model of a stack?
- Add an item to the top.
- Remove an item from the top of the stack.
- Check if the stack is full.
- Check if the stack is empty.
What are the 6 programming operations of a stack?
- push(item) - adds item to the top of the stack.
- pop() - removes + returns the item on top of the stack.
- isFull() - Checks if the stack is full.
- isEmpty() - Checks if the stack is empty.
- peek() - returns the top item without removing it.
- size() - returns the number of items in the stack.
How are the 4 stages of a stack?
- Add an item to a stack.
- Remove an item from a stack.
- Check if the stack is empty.
- Find the number of items in the stack.
What are the built in list operations of a stack?
- len(stack) - finds the length (height) of the stack.
- append(item) - add item to the top of the stack.
- pop() - removes + returns the item on the top of the stack.
What is a tree?
A connected, undirected graph with no cycles (i.e. there is a unique path from each node to any other node).
What is a rooted tree?
One node is identified as the root so every node execpt the root has a unique parent. All branches start from 1 node.
What is a node?
It holds a value or data, one of them becomes the root.
What is an edge?
It is the connection between the nodes.
What is a child?
It is a node with a parent node.
What is a parent?
It has an edge to a child node.
What is a leaf?
A node that doesn’t have a child node.
What is a binary tree?
A rooted tree which each node has a maximum of 2 children.
What are the 3 parts of a node?
(Binary tree)
- The data (Primitive or more complex object).
- Left pointer to a child.
- Right pointer to a child.
How do you build a binary tree?
- Nodes are added in the order given, with the first item at the root.
- Starting at the root each time, if the next item is less than the root, it is added to the left of the root, otherwise to the right. Same rule applied at the root of each subtree.
- e,g, 12, 7, 18, 22, 14, 10, 56, 3 , 2, 20, 8 (Work in order of list).
12
7 8
3 10. 14 22
2. 8. _. 20 56
How else can you represent a tree?
In an array.
- Pointer -1 means that there is no subtree on that side.
- e.g. tree[0] 1, 24, 3
- 1 is the index number of the value of the left child.
- 24 is the data index 0 holds on the tree.
- 3 is the index number of the value of the right child.
What are the 3 types of binary tree traversal?
- Pre-order.
- In-order.
- Post-order.
What order is pre-order traversal?
Visit the root, then traverse th eleft sub tree, then the right sub tree.
What order is in-order traversal?
Traverse the left sub-tree, visit the root, traverse the right sub-tree.
What order is post-order traversal?
Traverse the left sub-tree, traverse the right sub-tree, then visit the root.
What is a linked list?
A data structure which is the foundation for other structures to be built upon. e.g. stacks, queues, graphs + trees.
What are 4 features of a linked list?
- Contains nodes + pointers.
- Start pointer identifies the first node.
- Each node contains data and a pointer to the next node.
- Can be stored anywhere in memory, pointers indicate the address of the next item.
What is a circular linked list?
Where the last node points to the first node.
Combined with a double linked list to make a double circular linked list
What is a double linked list?
Uses an extra pointer so nodes point to the previous and the next node.
Combined with a circular list to make a double circular linked list
How can a linked list be implemented?
Through a static array. (Though requires the use of an index register; to determine where a specific index is in relation to a base address).
What are the 2 benefits of implementing the linked list through objects?
- Any available memory address can store the data. It doesn’t have to be adjacent (As each node points to the next).
- It is a dynamic data structure (Memory footprint is not determined at the compile time + can change during the run time).
What are the 6 applications of a linked list?
- Operating systems managing a processor to store process blocks in a ready state.
- Image viewers to switch between previous and next images.
- Music players to store tracks in a playlist.
- Web browswers to navigate back + forwards.
- For hash table collision resolution as an overflow.
- Maintaining a file allocation table of linked clusters on secondary storage.
What 5 operations can be performed on a linked list?
- Add: Adds a node to the linked list.
- Delete: Removes a node from the linked list.
- Next: Moves to the next item in the linked list.
- Previous: Moves to the previous item in the doubly linked list.
- Traverse: A linear search through the linked list.
What is a graph?
- It is a data structure consisting of nodes/vertices and edges/pointers.
- ## Each vertex can have more than 2 edges + point to any vertex in the structure.
What is a directed graph?
A graph where the edges point in one direction.
What is a undirected graph?
A graph where the edges do not specify a direction.
What is a weighted graph?
Each edge has a value which represents the relationship between the vertices. e.g. distance between them, time, bandwidth.
What is cost?
(Graphs)
The edge value.
How are graphs implemented?
- Stored as objects or using dictionaries (adjacency lists).
- ## Stored as an array (adjacency matrix; rows + colums represent the vertices + edges). 1 represents a edge between 2 vertices. 0 represents no edges between the vertices.
What are the 4 applications of a graph?
- Mapping road networks for navigation systems.
- Storing social network data.
- Resource allocation in operating systems.
- Representing molecular structures in geometry.
How do you traverse a graph?
The same way as a binary tree.
What are the standard operations of a graph?
- Adjacent: Returns whether there is an edge between 2 vertices.
- Neighbours: Returns all the vertices between 2 vertices.
- Add: Adds a new vertex to the graph.
- Remove: Removes a vertex from the graph.
- Add edge: Adds a new edge connecting 2 vertices.
- Remove edge: Removes an edge connecting 2 vertices.
- Get vertex value: Returns the data stored in a vertex.
- Set vertex value: Sets the data for a vertex.
- Get edge value: Returns the value of an edge between 2 vertices.
- Set edge value: Sets the value of an edge between 2 vertices.
What is a depth-first search?
(Graph search operations)
Starts at the root vertex, visits each vertex and explores each branch as far as possible before backtracking.
What is a breadth-first search?
(Graph search operations)
Starts at the root node and visits each neighbouring node before moving to the vertices at the next depth.
What are the 3 types of graph traversal?
- Pre-order
- In-order
- Post-order
What is the goal of a hash table?
Find an item in an unsorted/sorted list without needing to compare to other items in the data sets.
What does a hashing function do?
It calculates the position of an item in a hash table.
Order = Initial data -> Converted value to fed to hash function -> Hash function -> Hash Table (holds address and data at the address).
What is collision?
(Hash table)
When the algorithm returns the same value for more than one item. It happens because 2 data items cannot occupy the same position in the hash table
What should you do to minimise the chances of a collision?
(Hash Table)
Make the hash table significantly larger than it needs to be to store the data items.
What are the 4 ways to resolve a collision in a hash table?
- Open addressing.
- Linear Probing.
- Using a 2D hash table.
- Use an overflow table.
What is open addresing?
(Hash Table)
Repeatedly checking the next availible space in the hashing table until an empty position is found and store the value there.
What is linear probing?
- Used to find the item later.
- The hashing function delivers the start position from which a linear search can then be applied until the item is found.
What are 2 disadvantages of linear probing?
- Prevents other items from being stored in their position in the hash table.
- Causes clustering.
What is clustering?
(Hash Table)
Several values being filled around common collision values.
What is rehashing?
Finding an alternative position for items in the hash table.
What is the tradeoff between efficiency of the algroithm and the size of the hash table?
The larger the hash table the less collusions occuring. e.g. table size 10 has 2 collisions, table size 5 has 3 collisions so less efficient but smaller memory footprint.
What is the benefit of using a 2D hash table?
Chaining can occur.
What is chaining?
(Hash Table)
More than 1 item being placed in the same position.
What is an overflow table?
A second table created for collisions - which can be searched sequentially.
Or use a linked list to manage the overflow.
What are the 2 applications of a hash table?
- File systems linking a file name to the path of the file.
- Identifying the keywords in a programming language during complimation.
What are the 3 operations performed on a hash table?
- Add: Adds a new item to a hash table.
- Delete: Removes an item from a hash table.
- Retrieve: Retrieves an item from a hash table using its hash value.
