Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

CSC 225 > Final Exam > Flashcards

Final Exam Flashcards

1
Q

How are items inserted and removed in a Stack?

A

LIFO

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

What methods does the Stack ADT support?

A 
push()
pop()
isEmpty()
top()
size()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

pro/cons of Array-based Stack

A

O(1) per operation, but size must have an upper bound

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

How are items inserted/removed in a queue?

A

FIFO

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

What methods does queue support?

A 
enqueue()
dequeue()
isEmpty()
front()
size()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Pro/cons for array implementation of the queue

A

O(1) per operation

needs to have a fixed size

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

Methods that Index Based List supports

A

get(index)
set(index, element)
add(index, element)
remove(index)

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

Running times of array based index-based list

A

get - O(1)
set - O(1)
add - O(n)
remove - O(n)

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

Running times of various linked list methods

A 
first() - O(1)
last() - O(1)
before() - O(1)
after() - O(1)
element() - O(1)
remove - O(1)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Steps of MergeSort

A

1) Divide: sequence into 2 sequences
2) Recur: until all sequences have zero or one element
3) Conquer: merge the sequences all back together

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

Steps of QuickSort

A

1) Pick a pivot element
2) Sort list into 2 new lists less than pivot and greater than pivot
3) recur
4) conquer

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

What is a Priority Queue?

A

A container of elements, each with a key which determines the priority used to remove elements

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

Pros/Cons of unsorted vs sorted Priority Queue?

A

Unsorted: insert takes O(1) but remove takes O(n)
Sorted: insert takes O(n) time but remove takes O(1)

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

How to use a priority queue to sort elements?

A

Insert comparable elements one by one, and then remove them

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

PQ-sort where the priority queue is implemented with an unsorted sequence is like…

A

Selection sort!

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

PQ-sort where the priority queue is implemented with a sorted sequence is like….

A

Insertion-Sort!

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

A heap is what kind of tree

A

A complete binary tree

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

What is the Heap-Order Property?

A

for every node v other than the root, the key stored at v is geq than the key stored at v’s parent

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

What is a complete binary tree

A

A tree that fills from the left to the right

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

General idea of inserting into Heap

A

insert at first available spot, and then bubble up the tree

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

removing min element from a heap

A

remove root, select last element and put it at root position, and bubble down to restore tree

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

What is the height of a balanced tree?

A

log(n)

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

What is the worst case time of insertion sort?

A

O(n^2)

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

What is the worst case time of bubblesort?

A

O(n^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What is the worst case time of selection sort?
O(n^2)
26
What is the worst case time of quick sort?
O(n^2)
27
What is the worst case time of heap sort?
O(n log n)
28
What is the worst case time of merge sort
O(n log n)
29
What is the best case time of insertion sort?
O(n)
30
What is the best case time of bubble sort?
O(n)
31
What is the best case time of selection sort?
O(n)
32
What is the best case time of quick sort?
O(n log n)
33
What is the best case time of heap sort?
O(n log n)
34
What is the best case time of merge sort?
O(n log n)
35
What is the average case time of insertion sort?
O(n^2)
36
What is the average case time of bubble sort?
O(n^2)
37
What is the average case time of selection sort?
O(n^2)
38
What is the average case time of quick sort?
O(n log n)
39
What is the average case time of heap sort?
O(n log n)
40
What is the average case time of merge sort?
O(n log n)
41
What are some properties of Insertion sort?
adaptive, stable, in place
42
What are some properties of bubble sort?
in place
43
What are some properties of selection sort?
in place
44
What are some properties of quick sort?
in place
45
What are some properties of heap sort?
in place
46
What are some properties of merge sort?
not in place
47
What's Stirling's formula? (utter bullshit)
n! ~= (2npi)^(1/2)*(n/e)^n
48
What is the time complexity of radix sort with d keys?
O(dn)
49
Methods for Tree ADT
``` isInternal() isExternal() isRoot() size() elements() positions() swapElements() replaceElements() ```
50
What is a binary tree
Every node that is not a leaf has exactly 2 children
51
What kind of search is pre-order traversal? What ADT does it use?
Depth first, stack
52
What kind of search is in-order traversal? What ADT does it use?
symmetric, stack
53
What kind of search is post-order traversal? What ADT does it use?
bottom up, stack
54
What kind of search is level-order traversal? What ADT does it use?
breadth first, queue
55
What happens in a removal from a BST if the node has children?
find the node that would follow the removed node in an inorder traversal, and put it in it's place.
56
Time complexity of size, IsEmpty, find, insert, remove on BSTs
``` size - O(1) isEmpty - O(1) find - O(h) insert - O(h) remove - O(h) ```
57
Worst case BST height | Best case BST height
O(n) | O(log n)
58
Efficiency of 2-3 search and insertion
both O(log n)
59
what is the height of a RBT with n keys
O(log n)
60
What is a walk with no repeated edges
A trail
61
A closed trail is a
circuit
62
A walk with no repeated vertices is a
path
63
A closed path is a
cycle
64
What is a simple graph?
A graph with no self loops, parallel, or multi edges
65
The sum of the degrees of all vertices =
2*number of edges
66
the number of edges (m) is leq than THIS equation for the number of vertices (n)
(n(n-1)) / 2
67
How many edges does a complete graph have?
(n(n-1)) / 2
68
What is a spanning subgraph ?
A subgraph which contains all of the vertices of G
69
A tree is
a connected, undirected graph with no cycles
70
A forest is
an undirected graph without cycles (not necessarily connected! is made of many trees)
71
Let G be an undirected graph with n vertices and m edges: 1) if G is connected, then m geq 2) if G is a tree, then m = 3) if G is a forest, then m leq
1) n-1 2) n-1 3) n-1
72
In a simple digraph, the indegree of all vertexs =
outdegree of all vertex = number of edges
73
For a digraph G, a pair of vertices is connected iff
every pair of vertices is connected
74
For a digraph G, a pair of vertices is strongly connected iff
for all pairs of vertices u and v, u is reachable from v and v from u
75
What is a DAG
a directed acyclid graph with no cycles
76
The outdegree of a vertex k is the sum of the adjacency matrix
elements in row k
77
The indegree of a vertex k is the sum of the adjacency matrix
elements in column k
78
When do you use adjacency matrix structure over adjacency list structure
when there is a large number of edges
79
What ADT does DFS use?
Stack
80
What ADT does BFS use?
queue
81
2 properties of DFS
1) DFS visits all the vertices and edges in the connected component of starting vertex 2) the discovery edges labeled by DFS form a spanning tree of v
82
Time complexity of DFS for a graph G = (V, E) is
O(n+m) for n vertices and m edges
83
The BFS traversal of a graph visits
all vertices and edges
84
the discover edges of a BFS
form a spanning tree
85
What does it mean if (v, w) is a backedge in DFS
w is an ancestor of v
86
What does it mean if (v, w) is a cross edgein BFS
w is either on the same level as v or in the next level
87
What is the time complexity of BFS?
O(n + m) n vertices and m edges
88
What is a discovery arc in BFS?
arcs leading to unvisited nodes (form a forest)
89
What is a back arc in DFS
goes from a node to its ancestor
90
What is a forward arc in DFS?
a non-spanning arc that goes from a node to a proper desendent
91
What is a cross arc in DFS?
arcs that go from one node to another that are neither ancestor nor desendant
92
Steps to Kosarajus algorithm
1) perform a post order DFS on G=(V, A) 2) construct G^-1 = (V, A^-1) by reversing each arc 3) redo DFS starting with highest numbered postorder DFS 4) resulting trees are Strongly connected components
93
Topological sort is the same as
reverse postorder DFS
94
The sum of i from 1 to n
(n(n+1)) / 2
95
the sum of all a^i from 1 to n
(1-(a^(n+1))) / (1-a)
96
f(n) is big-Oh g(n) if
f(n) leq g(n)
97
f(n) is little-Oh g(n) if
f(n) < g(n)
98
f(n) is big-Theta g(n) if
f(n) = g(n)
99
f(n) is big-Omega g(n) if
f(n) geq g(n)
100
f(n) is little-Omega g(n) if
f(n) > g(n)
101
Def of Big-Oh
Let f, g: Z+ -> R f(n) is O(g(n)) iff /exists constant c>0, c \in R and n_o>0, n \in Z such that f(n) leq cg(n) for all n>n_o

CSC 225 (1 decks)

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