Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Data structures > Quiz 1 > Flashcards

Quiz 1 Flashcards

0
Q

If f(n) is in O(kg(n)) for any constant k>0 then

A

f(n) is in O(g(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
1
Q

If f(n) is in O(n) and g(n) is in O(h(n)) then…

A

f(n) is in O(h(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

If f1(n) is in g1(n) and f2(n) is in g2(n) then f1(n) + f2(n) is

A

in O(max(g1(n),g2(n)))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)) then f1(n)f2(n) is

A

in O(g1(n)g2(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Growth ratefastest->slowest

A

constant, multi log, log, log squared, log^k, linear, nlogn, N^2, N^3, c^N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Form for an algebraic spec

A 
adt NAME
    uses \_\_\_\_\_
    operations:
    preconditions
    axioms
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Big O

A

T(N) is (f (N)) if there exists c, n such that T(N) = n. (upper bound)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Big Omega

A

T(N) is Omega(g(N)) if there exists c, n such that

T(N) >= cg(N) for all N >= n. (lower bound)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Big Theta

A

T(N) is Theta(h(N)) if and only if T(N)=(h(N)) and

T(N) = Omega(h(N)). (tight bound)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Little o

A

T(N) is o(p(N)) if for all c there exists n such that
T(N) < cp(N) when N > n. (loose upper bound: T(N)=(p(N))
but T(N) 6 != (p(N)) )

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Array - indexing complexity

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Array - search

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Dynamic Array - indexing

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Dynamic Array - Search

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Dynamic Array - Insertion

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Dynamic Array - deletion

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Singly Linked List - indexing

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Singly Linked List - Search

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Singly Linked List - insertion

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Singly Linked List - deletion

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Doubly Linked List - indexing

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Doubly Linked List - Search

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Doubly-Linked List - insertion

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Doubly-Linked List - deletion

A

O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Binary Search Tree - Indexing
O(log(n)), average. O(n) worst
26
Binary Search Tree - Search
O(log(n)), average. O(n) worst
27
Binary Search Tree - Insertion
O(log(n)), average. O(n) worst
28
Binary Search Tree- deletion
O(log(n)), average. O(n) worst
29
Splay Tree - Search
Always O(log(n))
30
Splay Tree - Insertion
Always O(log(n))
31
Splay Tree - deletion
Always O(log(n))
32
AVL Tree- Search
Always O(log(n))
33
AVL Tree- insertion
Always O(log(n))
34
AVL Tree - deletion
Always O(log(n))
35
Binary Search
O(log(n)) always on sorted array of n elements
36
Bubble Sort
Best, O(n). Worst, O(n^2). Average, O(n^2)
37
Merge Sort
always O(nlog(n))
38
Insertion Sort
``` best O(n). average O(n^2) worst O(n^2) ```
39
Bag Structure methods
add, remove, contains, size, clear, isEmpty
40
Set Structure Methods
add, remove, size, isEmpty, contains, union, intersect
41
Queue Structure Methods
enqueue, dequeue, front,
42
Stack Structure Methods
push, pop, peek
43
Tree
update, insert, delete, getValueFromKey
44
amortized analysis of efficiency
method of anallyzing algorithms that consider the entire sequence of operation of the program. Its bigO notation.
45
binary trees - how many children
2 most
46
BST property
the key in any node is larger than all keys in that nodes left subtree and smaller than all keys in the right subtree.
47
how many nodes fit in each level
2^i where i is the level
48
how many nodes can a tree with h levels store
(2^h) - 1
49
depth of root
0
50
depth of node generally
1 + depth of parent
51
heigh of tree
leaves have 0. | Generally - 1 + heigh of children
52
AVL Tree condition
every node in tree, heigh of left and right differ by <= 1
53
breadth first print
Starts at root, prints left to right before going to next level down
54
depth first preorder
visit current node, then entire left tree, then entire right subtree
55
depth first postorder
visit entire left, then entire right tree - then current node.
56
Binary Search
O(logn)
57
find place to check binary search
(start +end )/2
58
deque
removeal and insertion at both ends "double ended queue"
59
bubble sort
bubble biggest rightward. O(N^2)
60
selection sort
find smallest each time O(N^2)
61
insertion sort
swap adjacent each time two insert O(N^2)
62
merge sort
O(NlgN)
63
heap sort
bottum up build + N removals O(NlgN)
64
quick sort time complexity
``` worst O(N^2) best O(NlgN) ```
65
bottom up heap build time complexity
O(N)
66
insert/removemax for heap
o(lgN)
67
degree
number of incident edges
68
adjacent edges
edge between u and v exists
69
multigraph
a graph that can have repeated edges
70
Cycle
a path of length >= whose first and last are the same
71
connected graph G
there is a path in g from every vertex to everyother
72
acyclic graph
a graph with no cycles
73
tree
an acyclic connected graph
74
forrest
a disjoint set of trees
75
subgraph of G
subset of graph G's edges and verts
76
spanning tree of a connected graph G
a subgraph that contains all of G's verticies and is a single tree
77
summ of all degrees in normal graph
2M
78
undirected graph
M<= (N(N-1)/2)
79
directed graph M
M <= N(N-1)
80
connected graph M
M >= N -1
81
tree M
M = N - 1
82
forrest M
M <= N - 1
83
graph small scale operations
getnumVerts, getNumEdges, boolean adjacent(u,v), neighbors(V), int degree (v), boolean incident(v,e), bolean connected(u,v)
84
graph large scale operations
depth first search, breadth first search, find spanning tree, shortest path between verts, connected components, isConnected, isTree, hamiltonianTour, Eulerian Path
85
Hamiltonian Tour
visit every vertex exactly 1x
86
Eulerian Path
visit all edges exactly 1x
87
adjacency matrix
store a v x v boolean array that is true exactly when an edge v-w exists
88
array of edges
stores a list of edge objects where each one has two int instance variables
89
adjacency list
store a vertex index array of lists of vertices. VertexArray[i] is linked list of verticies adjacent to vertex[i]
90
Topological Sort
order vertices so that each v comes earlier in list than any other vertex to which an edge leads from v
91
strongly connected graph
are all vertex pairs(v,w) s.t. v is reachable from w and w is reachable from v
92
single source unweighted shortest path
``` O(N+M). Set all distances to infinity Set all previous to null. Set source to 0. Begin BFS: Q.enqueue(s) While Q is not empty: v = Q.dequeue() for all u in neighbors(v) with prev[u]==null dist[u] = dist[v] + 1 prev[u] = v Q.enqueue(u) ```
93
Complexity of Dijkstras Algorithm
O(MlgN) with adaptable heap
94
Topological Sort time complexity
O(N+M) to compute indegrees O(N+M) to determine ordering O(N+M) total

Data structures (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions