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
What are the four types of Trees
Rooted Trees
Binary Trees
Binary search Trees
Expression Trees
Define Rooted Trees
A Tree with one node designated as the root, all other nodes descend from this node
Define Binary Trees
A rooted Tree where very node has at most two child nodes
Define Binary search Trees
A rooted Tree where the nodes of the tree are ordered
Define Expression trees
They are trees that represent expressions
Define Linked Lists
They are dynamic data structures which means they can grow in size during execution.
What is each element in a linked list called
A node
What do nodes store
a pointer to the next node and the data relating to the element
What are the two additional pointers
One towards the front and one towards the end of the list
What are the two types of linked lists
Ordered and Unordered
What are the three steps to adding new nodes to a linked list
- Creating the new node
- Setting the pointer of the new node to the value of the next node
- Setting the header point to point to the new node
What is the special about deleting a from a linked list node
No actual data is deleted, it is just un assigned
How to delete a node from a linked list
Set the pointer to the “Deleted” node to the next node
Define Hashing Algorithms
They store the data in an array and assign them an index
How are the index’s in hashing algorithms assigned
They are dependent upon the position of the data within the array
When do collisions occur, in hashing algorithms
When the hashing function produces the same hash value for two or more keys
What are the two methods to deal with collisions
Linear Probing
Chaining (Retrieving data)
How does linear probing work
It assigns the second key with the next position in the table that is available
How does Chaining work
It creates a chain or linked list within the data table, the hash value that had the collision will then store the location or the linked list.
Uses of Pre-order Traversal
Copy a tree, or search for a node within the tree
Uses of In-order traversal
Create an ordered list of the nodes, or to recreate the order that the tree was made in
Uses of Post-order traversal
Deleting a tree, since it visits each leaf node before visiting the parent node
What is the easy way of remembering InOrder traversal
Left, Root, Right
What is the easy way of remembering PreOrder traversal
Root, Left, Right
What is the easy way of remembering PostOrder Traversal
Left, Right, Root
What is the method of adding items to a stack called
Pushing
What is the method of removing items from a stack called
Popping
