CSE 331 Exam 1 ACTUAL UPDATED QUESTIONS AND CORRECT ANSWERS
ADT (Abstract Data Type) defines a general data type like list that describes a collection of data without
worrying about the specific implementation
List ADT common ADT for holding ordered data, having operations like append a data
item, remove a data item, search whether a data item exists, and print the list
singly linked list a data structure in which each list element contains a pointer to the next list
element
doubly linked list a linked list in which each element has both forward and backward pointers.
code modeling process of mathematically representing howmany operations a piece of code will
run in relation to the input sizen
asymptotic analysis Analysis of function behavior as its input approaches inf
find dominating term, remove any constant factors
simple, mathematically rigorous, decisive when we analyze code we want it to be:
O(nlogn) runtime of sorted() alg
O(n) runtime of sum() alg
len(), abs(), round(), range() python functions that are O(1)
sum(), max(), min(), enumerate(), any(), all() python functions that are O(n)
Big Oh, O(g(n)) -definition f(n): there exist positive constants c and n0 such that
0 <= f(n) <= cg(n) for all n>=n0
c- what is the constant factor
n0- what pt onward is f(n) smaller
Big Omega f(n): there exists positive constants c & n° such that
0 <= cg(n) <= f(n) for all n >= n°
c- what is the const factor
n0 - what pt onward is f(n) larger
ADT (Abstract Data Type) defines a general data type like list that describes a collection of data without
worrying about the specific implementation
List ADT common ADT for holding ordered data, having operations like append a data
item, remove a data item, search whether a data item exists, and print the list
singly linked list a data structure in which each list element contains a pointer to the next list
element
doubly linked list a linked list in which each element has both forward and backward pointers.
code modeling process of mathematically representing howmany operations a piece of code will
run in relation to the input sizen
asymptotic analysis Analysis of function behavior as its input approaches inf
find dominating term, remove any constant factors
simple, mathematically rigorous, decisive when we analyze code we want it to be:
O(nlogn) runtime of sorted() alg
O(n) runtime of sum() alg
len(), abs(), round(), range() python functions that are O(1)
sum(), max(), min(), enumerate(), any(), all() python functions that are O(n)
Big Oh, O(g(n)) -definition f(n): there exist positive constants c and n0 such that
0 <= f(n) <= cg(n) for all n>=n0
c- what is the constant factor
n0- what pt onward is f(n) smaller
Big Omega f(n): there exists positive constants c & n° such that
0 <= cg(n) <= f(n) for all n >= n°
c- what is the const factor
n0 - what pt onward is f(n) larger
