ADTs Flashcards
Name 9 ADTs
- Queue
- Stack
- List
- Arrays
- Linked Lists
- Hash Tables
- Graphs
- Trees
- Binary Trees
What is a Queue’s priority
FiFo
What is a Stack’s priority
LiFo
What is Static and Dynamic
Static - Fixed size e.g. arrays
Dynamic - Variable sized e.g. Lists
What are the parts of linked lists
There are 2 parts
Data (can be complex data structure)
Pointer (index of next node)
What is Encapsulation
To hide data from users. To hide inner workings of program.
What is Overflow
Trying to push to a full stack
What is underflow
Trying to pop from an empty stack
What is a Call Stack
Provides a system for passing parameters and return addresses to subroutines
What are the functions for adding to and removing from a Queue
enQueue(item)
deQueue()
What are the functions for adding to and removing from a stack
Push(item)
Pop()
What are the functions to check if a stack or queue is full or empty
IsFull()
IsEmpty()
What is the function to view whats on top of the stack
Peek()
What’s the function to return the num of items on a stack
size()
What is a Hash table
Uses a hashing algorithm to find data quickly
Each record is assigned a unique address
Collision occurs if addresses are the same, they are remade if this happens
What function is in most hashing algorithms
MOD by number of slots. The remainder is the address
What is a collision
Keys that generate the same address for different primary keys, referred to as synonyms
What is clustering
After a collision, if you put the item in the next available spot, clustering occurs
What could you do to prevent clustering
Implement Skip value to add 1, 3, 5 instead
What happens when an item is deleted from a hash
The space is replaced with a dummy item
What is a Dictionary
ADT made of associated pairs
Each pair has a key and a value
The value is accessed via the key
In a dictionary multiple items can have the same key
What is the address of the key
Value pair is calculated using a hashing algorithm
What is a graph
an ADT representing complex relationships
What are the 2 types of graphs
Directed
Undirected
How can you tell if a graph is directed
If there are arrows between nodes
How can you represent a graph
With an adjacency matrix or adjacency list
Advantages and Disadvantages of a Matrix
Adv: Convenient to work with, adding edge is simple
Dis: Sparse graph will leave cells empty wasting lots of memory space.
Advantages of a List
More space efficient (for large sparse graphs)
What are 3 applications of graphs
- Maps
- Computer Networks
- Social Networks
What is a tree
A connected, undirected graph with no cycles
What are the parts of a tree
Root (at top), Branches, Leaves. Can have subtrees
What is a rooted tree
Has one node as the root, every node except the root has one unique parent.
What is a binary tree
Each node has a max of two children
What are the 3 parts of a node
Data
Left Pointer to child
Right Pointer to child
What is a binary search tree
Nodes are added in order given starting at root each time. If item is less, its added to left. Larger, right
How is a tree represented
In an array
What are the three types of traversal
- Pre-order
- In-Order
- Post-Order
What is Pre-order Traversal
Draw Road:
Left
What is Post-order Traversal
Draw Road:
Right
What is In-order Traversal
Draw Road:
Underneath
What are the 3 cases when deleting a node
- Leaf has no children
- Leaf has 1 child
- Leaf has 2 children
What happens if the leaf deleted has no children
Nothing, it simply disappears
What happens if the leaf deleted has one child
Child takes parents place
What happens if the leaf deleted has 2 children
Leaf replaced with the leftmost value on its right subtree
