4.2 Abstract Data Types Flashcards
What is a Data Structure?
A Data Structure is a common format for storing large volumes of related data in an organised and accessible format
What is an Abstract Data type?
An Abstract Data Type is a conceptual model of how data is stored and the operations that can be performed upon them
What is an Array?
1) An array is a list or table of data consisting of elements with the same data type that has a variable name that identifies the list or table
2) Each item in the table is called an element
3) Can be 1 or 2 Dimensional
5) 1 Dimensional array represents a vector
6) 2 Dimensional Array represents a matrix
What is a text file?
1) A text file is an organised collection of records where data is stored in human-readable characters
2) Different items of data stored in a file are referred to as a field
What is a Static Data Structure?
1) A static data structure is a method of storing data where the amount of data stored and memory used is fixed
What is a Dynamic Data Structure?
1) A dynamic data structure is a way of storing data where the amount of data stored will vary as the program is run
2) Uses heap which is a memory that can be allocated dynamically to a dynamic data structure
What is a Stack and how does it work?
1) A stack is an example of a LIFO (Last In First Out) data structure the last item of data added is the first to be removed
2) Works, in the same way, a plate of dishes but no physical movement a stack pointer tracks the top stack position
3) -Adding an item to the stack = Pushing
- Removing item from the stack = Popping
- Identifying the top of the stack = Peeking
4) E.g. Browsers (when you press the previous page button)
What is a Queue and how does it work?
1) A queue is a FIFO (First In First Out) data structure where the first item of data entered is the first item of data to leave
2) E.g. in a peripheral such as a Hard Drive sending data to the CPU, if the CPU cant deal with the data straight away then it will be placed in a queue or when a document is sent to a printer
What is a Graph and how is it represented?
1) A graph is an abstract data type that can be used to represent complex, non-linear relationships between objects
2) A graph consists of nodes (also called vertices) that are connected by edges (also called arcs)
3) Graphs are usually represented as diagrams with circles that represent the nodes and lines to represent the edges
What are the three main types of queues?
There ate three main types of Queue (All FIFO):
1) Linear Queue: Line of Data
2) Circular Queue: Implemented as a Ring
3) Priority Queue: Where some data is left out of sequence
What are the typical uses of graphs?
Graphs can be used to represent a wide range of complex data relationships including:
1) Social Networking
2) Transport Networks (tube maps etc)
3) The Internet
4) Electric Circuits
What is a weighted graph?
1) A weighted graph is a graph that has data values associated with the edges
2) A weighted graph can be either direct or undirected
What is an undirected and a directed graph?
1) An undirected graph is a graph where the relationship between the vertices can go in either direction E..g On a train map
2) A Directed (Diagprah) graph is a graph where the relationship between vertices is one-way E.g. in a family tree
- Arrows were used instead of lines to represent the edges
How can an adjacency list be used to represent a graph?
1) An adjacency list is a data structure that stores a list of nodes with their adjacent nodes
2) It can be represented in three different ways:
1) Directed Graph
2) Weighted Graph
3) Undirected Graph
How can an adjacency matrix be used to represent a graph?
1) A matrix representation of a graph that stores the edges connecting all possible nodes
2) it is populated with 1’s and 0’s
3) A 1 is put in a cell where there is an edge and a 0 where there is no edge
3) There are again three variations of this graph:
1) Undirected Graph
2) Directed Graph
3) Weighted Graph
Compare the uses of an adjacency matrix and an adjacency list?
1) List requires less memory as matrix stores a value for every combination of adjacencies which requires more memory
2) Matrix has faster processing time as all the combinations are already stored a List has to be parsed to find particular adjacencies
What are an Adjacency List and Matrix more suited to and what are they called?
1) Adjacency List suited more to where there are fewer edges known as a sparse graph
2) Adjacency Matrix suited where their many edges are known as a dense graph
What type of data structure is an array?
Static data structure
What is a Binary file and what are its functions?
1) Binary File is organised collection of records where data is stored in binary
2) Functions of Binary File and File:
- Read into a file from a program
- Write data into a file from a program
What is Stack overflow and underflow?
1) Stack Overflow: Stack needs more memory than is allocated
2) Stack Underflow: When there is no data to be popped
What are the advantages and disadvantages of a static data structure? (6 Points)
1) Fast access of individual elements of data
2) Structure is a fixed size so they are more predictable
3) Memory addresses allocated so quicker access
4) E.g. Records and some arrays
5) Fixed relationship between different elements
6) Takes up memory even if it isn’t needed making it less efficient
What are the advantages and disadvantages of a Dynamic data structure?
2 Advantages, 2 Disadvantages
Advantages:
1) More efficient as data needed varies
2) Structures vary in size so need to have a mechanism to know the size of the structure
Disadvantages
3) Slower access to each element as the memory location isn’t fixed
4) Variable relationship between elements of data as a program is run
5) E.g. Stacks, Queues and Binary Trees
What is a Tree?
1) A tree is an abstract data structure that is very similar to a graph in that it has nodes and edges
2) It is a hierarchical structure with branches with a root node as all the other nodes branch away from it
What is a rooted Tree?
1) A root of a tree is a start node for traversals and it is a tree with a root
2) The root is the only node with no parent and all other nodes are descendants of the roots
3) All other nodes have a parent-child relationship and are descendants of root node
3) A leaf is a node with no children
4) A Parent node is a node that comes directly before another node next to it
What is a Binary Tree?
1) A binary tree is a rooted tree where each node has at most two children
2) Binary search tree which is optimised to search it is a rooted tree with ordered nodes
What are the uses of a rooted Tree?
1) Can be used to store data that has an inherent hierarchical structure
E.g. Operating System uses a tree for dictionaries, files and folders in its file management system
What is a Hash table and what are its uses?
1) A hash table is a data structure that creates a mapping between keys and values
2) Made up of two parts
- Table of data
- A Key identifies the location of the data within the table
What is a Hashing algorithm?
1) A hashing algorithm creates a mapping between keys and values
2) Essentially a lookup table that uses a key/value combination
What is a collision?
A collision occurs when a Hashing algorithm produces the same index for two or more different keys
How does chaining fix collisions?
1) Chaining is a technique for generating a unique index when there is a collision by adding the key/value to a list stored at the same index
How does Rehashing fix collisions?
1) The process of running the hashing algorithm again until a unique key is created when a collision occurs
2) This is done through probing where the algorithm searches for an empty slot by looking for the next available slot to the index where there was a clash
What is a dictionary?
1) A dictionary is a collection of key-value pairs in which the value is accessed via the associated key
2) An Associative array is a two-dimensional structure containing key/value pairs of data
What are the applications of Dictionaries?
1) Information retrieval
- Add Data
- Retrieve Data
- Delete Data
- Update Data
What is a Vector?
A data structure representing a quantitiy with both magnitude and direction, It can be represented as a list, function or geometric point
How can a Vectors represent a data structure?
1) Vectors can be implemented as values that are stored in a list form
What is Dot product of two vectors?
Dot product is an operation on two vectors that returns a scalar value. Hence it is sometimes also called scalar product
What is the Application of dot product?
1) Dot product of two vectors is used to calculate the angle between the two vectors
How do you calculate the angle between vectors?
E.g. Given a = (3,4), a = (2,6)
1) (3 x 2) + (4 x 6) = 30
2) Square root the square of the first numbers
3) Square root of 3 squared + four squared
4) Square root the square of the second numbers
5) square root 2 squared + six squared
6) Multiply the answers
7) Divide answer to 1) and answer of 6)
8) Cos -1 (the answer)
How do you use convex combinations in two vectors?
What is the expression?
1) Convex combinations of vectors can be used in fields of computer science such as computer games
2) The expression is (a * u) + (B * v) or au + Bv - u and v are both vectors - a + B = 1 - a and B are each greater than equal to 0
3) If you plot the vectors u and v from the same starting point of origin a new vector from the same start point on the line to the connect u and v tips is made
How do you do Vector addition with two vectors with different values
1) Vector Addition: Add value from the first component to the same component of the second vector
2) E.g. a = (5,13) b = (29,5)
a + b = ( 5 + 29 + 13 + 5) = (34, 18)
How do you do Vector multiplication?
1) Vector Multiplication: Multiply each component by the scalar of the vector
2) E.g. a = (5, 8) by 2 (10, 16)
3) E.g. b = (35, 15) by 0.5 (17.5, 7.5)
