Cs 261 Midterm

Front 1

Three Levels of Abstrac5on
There are at least three levels of abstrac<on in the study of data
structures:

Back 1

•  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)

Front 2

Can you describe the three levels of
abstrac<on of the stack ADT?
1) Specifica<on/Interface: Proper<es and behaviors (what)

Back 2

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]

Front 3

Bag ADT functions

Back 3

Add ( val)
bool Contains ( val )
Remove ( val )

Front 4

Queue functions

Back 4

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.

Front 5

Deque Functions

Back 5

void addFront(TYPE val);
void removeFront();
TYPE front();
void addBack(TYPE val);
void removeBack ()
TYPE back();

Front 6

DynArrDeque vs Linked List Deque, algorithmic complexity

Best, ave, worst
addLast

removeLast

addFirst

removeFirst

Back 6

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)

Front 7

in a tree,
A path’s length is equal to the number of

Back 7

arcs traversed

Front 8

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 ______

Back 8

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

Front 9

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 ______

Back 9

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

Front 10

Opera3on
DynArrBag LLBag OrderedArrBag BSTBag
Add
Contains
Remove

Back 10

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)