1.4.2 Data Structures & in Paper 2 Flashcards
What is a Graph?
An abstract data structure used to show relationships between items.
What is the definition for Node/Vertex?
An item, or piece of data
What is an Edge/Arc?
A relationship between nodes.
Describe a Weighted Graph
Each edge has a value, or a cost to travel.
Describe an unweighted graph
Edges have no values or costs.
What is a Directed Graph?
Edges can only be traversed in one direction.
What is an Adjacency Matrix?
A table to show the relationships in a graph.
What is an Undirected Graph?
Edges can be traversed in any direction.
What is an Adjacency List?
A space-efficient way to store the relationships in a graph.
What is the definition of Static?
Structures with a fixed length.
What is the definition of Dynamic?
Structures with a changeable length.
What is the definition of Array?
A static, ordered set of elements of the same type
What is the definition of Tuple?
- A static, ordered set of elements of any type.
- Immutable.
What is a 2D array?
- An array that contains other arrays.
- Often used to store tables
What is a Linked List?
- An abstract, dynamic data structure…
- Which holds ordered data from different locations
What are the steps in inserting an item into linked lists?
- Use nextFree to place the item in the next free node
- Follow pointers from start until you find the node with data greater than the item.
- Change the pointer of the previous node to point to your item.
- Change the pointer of your item to point to the next code.
What is a List?
An abstract data structure that stores a number of items.
What is the general method to adding items to an ordered list?
Is the list full? If so, stop.
REPEAT:
If targetIndex<nextIndex:
move all items along by 1
insert them
ELSE:
Look at next list item.
What is Depth-first traversal ?
Read a graph by going as far down each route as
you can before backtracking.
What is Breadth-first traversal ?
Read a graph by checking all available routes
from a node before progressing.
What is a Binary Search Tree ?
A rooted tree where each node has a maximum of two children.
Makes data easy to search.
What are the 3 ways you can be traversing a binary tree ?
- Pre-order (to the left)
- In order (underneath)
- Post-order (to the right)
What is abstract data structure?
A data structure made by the
programmer.
What is a Queue ?
A static, first-in-first-out structure for
ordering data.
What does enQueue(item) do ?
Add an item to the rear of the list.
What does deQueue() do ?
Remove the item from the front of the
list.
What does isEmpty()/isFull() do ?
Check if the list is empty / is full.
What is a Stack ?
A Last In First Out (LIFO) data structure.
Usually used to store instructions.
What is the Call Stack ?
A structure to hold the active subroutines
and their data.
