Data Structures Flashcards
Define a 1D array
Is a structure of data elements all of the same data types
Define a 2D array
Is a collection of data elements arranged in a grid like structure with rows and columns
Define a 3D array
is a structure of data elements arranged in 3D grid structure, with elements in rows in slabs
State three points about Stacks
Last in first out
Real world example; stack of books
Computing example; undo and redo buttons
State three points about Queues
First in first out
Real world example; queue of people
Computing example; list of instructions with a CPU
State one thing that both Stacks and Queues have in common
They are both Linear data structures
Define a Tree
Is a connected, undirected graph with no cycles
What does connected mean in reference to Tree’s
There is a path from one node to another
What does undirected mean in reference to Tree’s
There is no direction associated with a path
What does ,No cycles, mean in reference to Tree’s
There is only ever on route between two nodes
Are Tree’s linear data structures
No
What are the five different methods to traverse a Tree
Breadth-first traversal,
Depth-first traversal,
In-order traversal,
Pre-order traversal,
Post-order traversal
Define Breadth-first traversal
You visit each node in a level before looking at any of the children nodes from that level
Define Depth-first traversal
You visit all the children of a node before moving on to the next node on that level, starting from the left nodes
Define In-order traversal
You visit the left most node and all of its children then the next left most node and it’s children and so on.
Define Pre-order traversal
You visit the root node first then the left most child nodes, the the root nodes and then the right child node.
Define Post-order traversal
You visit each parent node after visiting both of it’s child nodes
What are the five components of a Tree
Root
Node
Edge
Leaf
children