ADTs Flashcards
(44 cards)
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
