Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
10 Cards in this Set
- Front
- Back
Three Levels of Abstrac5on
There are at least three levels of abstrac<on in the study of data structures: |
• Specifica<on/Interface: Proper<es and behaviors (what)
• Applica<on: How it’s used (why) • Implementa<on: the various implementa<ons in a par<cular library (how) |
|
Can you describe the three levels of
abstrac<on of the stack ADT? 1) Specifica<on/Interface: Proper<es and behaviors (what) |
Specifica<on/Interface View
initStack( ); pushStack(val); valType topStack( ); popStack( ); bool isEmptyStack( ); Properyires: A Stack is a collection that has the property that an item removed is the most recently entered item [ LIFO] |
|
Bag ADT functions
|
Add ( val)
bool Contains ( val ) Remove ( val ) |
|
Queue functions
|
int isEmpty();
void addBack(TYPE val); // Add value at end of queue. TYPE front(); // Get value at front of queue. void removeFront(); // Remove value at front. |
|
Deque Functions
|
void addFront(TYPE val);
void removeFront(); TYPE front(); void addBack(TYPE val); void removeBack () TYPE back(); |
|
DynArrDeque vs Linked List Deque, algorithmic complexity
Best, ave, worst addLast removeLast addFirst removeFirst |
DynArrDeque vs Linked List Deque, algorithmic complexity
Best, ave, worst addLast O(1),O(1+),O(N) O(1),O(1),O(1) removeLast O(1),O(1),O(1) O(1),O(1),O(1) addFirst O(1),O(1+),O(N) O(1),O(1),O(1) removeFirst O(1),O(1),O(1) O(1),O(1),O(1) |
|
in a tree,
A path’s length is equal to the number of |
arcs traversed
|
|
A node’s height is equal to the _______:
– A leaf node has a height of _____ – The height of a tree is equal to the height of the ______ |
A node’s height is equal to the maximum path length from
that node to a leaf node: – A leaf node has a height of 0 – The height of a tree is equal to the height of the root |
|
A node’s depth is equal to the path length from _____:
– The root node has a depth of __ – A tree’s depth is the maximum depth of all its ______ |
A node’s depth is equal to the path length from the root to
that node: – The root node has a depth of 0 – A tree’s depth is the maximum depth of all its leaf nodes |
|
Opera3on
DynArrBag LLBag OrderedArrBag BSTBag Add Contains Remove |
Opera3on
DynArrBag LLBag OrderedArrBag BSTBag Add O(1) O(1) O(n) O(logn) Contains O(n) O(n) O(logn) O(logn) Remove O(n) O(n) O(n) O(logn) |