Fs Of Data Structures Flashcards
What are the 4 categories for data types?
Strong types
Static types
Dynamic types
Abstract types
Define strong data types.
Standard data types; integer, character etc. They’re the basis for all other types, and a fixed amount of memory is defined.
Define static data types?
Those that require a fixed amount of memory, such as arrays and sets. But are not included in the pre-defined data types.
Define dynamic data types?
Those that may be expanded given the limitation of the memory. For example files and pointers.
What are abstract data types
Abstract means they don’t usually exist as a pre-built data structure but instead must be manually built. Such as stacks and queues.
What structure does a stack have?
LIFO (last in first out)
What sort of structure does a queue have?
FIFO (First in first out)
What are the 3 commands used in stacks?
Pushing = adding an item Popping = taking an item off Peeking = finds the start (bottom) of the stack
What happens to the pointer as an item is pushed or popped?
When an item is popped the pointer moves down.
When an item is pushed the pointer moves up.
What are stack overflow and underflow errors?
Overflow - When an item is pushed onto a full stack.
Underflow - When an item is popped from an empty stack.
What is an advantage and disadvantage of implementing a queue as an array.
Advantage - faster and more memory efficient than a linked list.
Disadvantage - fixed size
What is an advantage and disadvantage to implementing a queue as a linked list?
Advantage - Dynamic size. Means no wasted memory.
Disadvantage - Not as memory efficient as an array. Requires more memory per element.
What operations are needed in a queue?
Add item Remove item Front item Is queue empty Is queue full
What are the 3 types of queue?
Linear queue
Circular queue
Priority queue
Define a linear queue.
A queue with a fixed amount of memory. Usually implemented using a 1D array. Items added to the back and removed from the front, memory can not be re-used.
Define a circular queue.
A queue with a fixed amount of memory.
The back of is connected to the front.
Memory can be re-used.
This is often used to store data waiting to be transferred from one device to another.
Define a priority queue.
Elements in the queue are ordered into levels of priority.
What are vertices in a graph?
Objects in the graph (represented by a circle)
What is an edge in a graph?
A connection between two vertices (or nodes)
What does neighbour mean (graphs)?
A vertex connected to another vertex via an edge is a neighbour.
What is the degree of a vertex (graphs)?
The number of neighbours it has.
What are some uses of graphs?
Mapping Game theory Electrical circuits Social networks The internet
What are undirected graphs?
Graphs without arrows (direction)
What is a weighted/labelled graph?
A graph with values attached to edges (usually numerical)
What is a directed graph?
A diagram with arrows (direction)
What is a graph?
A graph is an abstract data type used to model the relationship between 2 or more vertices.
What are the two ways of storing a graph of a computer?
Adjacency lists
Adjacency matrices
How do adjacency lists work?
By recording the relationship between all relevant vertices.
Only records vertices with edges between them.
What are all separate values separated by on an adjacency list?
;
For example: D,15; H,10; C,20
What is an advantage and disadvantage of an adjacency list?
Advantage - Good for graphs with fewer edges than nodes.
Disadvantage- Bad for graphs with more edges than nodes.
How do adjacency matrices work?
By recording the relationship between vertices in 2D array or grid populated with 1s or 0s.
An adjacency matrix also records when there isn’t an edge between vertices.
What is an advantage and disadvantage of an adjacency matrix?
Advantage - Good for graphs with more edges than nodes.
Disadvantage - Bad for graphs with less edges than nodes.
Adjacency List vs matrix?
List:
Stores data only when there is edge = less memory.
Has to check if adjacencies exist = more time.
Quicker for sparse graphs.
Matrix:
Stores data for every combination = more memory
Because of ^ easier to ID adjacencies = less time
Quicker for dense graphs
What is a tree?
An abstract data structure with a structure similar to a graph but with a hierarchical structure.
How does a tree differ from a graph?
It has a hierarchical structure.
It is undirected.
It has no loops.
What is a rooted tree?
A tree with one vertex designed as the root in which all other vertices spread out from.
How do you construct a binary tree?
- Create a root node
- Insert data into root node
- Compare new item with root node
- If it’s > root follow the right pointer otherwise follow the left
- Compare until left of right pointer is null
- Create node, insert right and left pointers and set them to null
- Connect the node to the tree
What methods can be used to traverse a tree?
Breadth first
Depth first
What methods can be used to traverse a tree?
Breadth first Depth first Pre-order In-order Post-order
What are the four CRUD operations?
Create
Retrieve
Update
Delete
What are the four CRUD operations in their SQL and HTTP method format?
(SQL , HTTP):
INSERT , POST
SELECT , GET
UPDATE , PUT
DELETE , DELETE
What is a priority queue and how does it work?
It has different points at which items can join according to priority.
They join at the back of their priority section.
If there are no items in correct priority section they join the front of the next lower section.
