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