Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures > Test 3 > Flashcards

Test 3 Flashcards

1
Q

A __________ ___________ is a restricted form of a list. Items have priorities (or _____)

A

priority queuekeys

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

A priority queue removes items based on _________

A

priority

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

Unsorted list implementation store the items of the priority queue in a ____-_____, in arbitrary order

A

list-based

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

Unsorted list implementation example

A

4 - 5 - 2 - 3 - 1

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

Unsorted list implementation Performance: ____________ takes _____ time since we can insert the item at the beginning of the sequence

A

insertItemO(1)

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

Unsorted list implementation Performance: ___________, __________, and ___________ take ______ time since we have to traverse the entire sequence to find the smallest key

A

removeItem, min/maxKey, min/maxElementO(n)

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

Sorted list implementation store the items of the priority queue in a sequence, sorted by _____

A

key

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

Sorted list implementation example

A

1 - 2 - 3 - 4 - 5

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

Sorted list implementation Performance: __________ takes ______ time since we have to find the place where to insert the item

A

insertItemO(n)

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

Sorted list implementation Performance: ___________, __________, and ___________ take ______ time since the smallest key is at the beginning of the sequence

A

removeItem, min/maxKey, min/maxElementO(1)

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

Sorting Using a Priority Queue -given a ___________ of N items: a PQ can be used to sort the ___________:

A

sequencesequence

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

Sorting Using a Priority Queue -given a sequence of N items: a PQ can be used to sort the sequence: -Step 1: ___________…

A

Insert N items into the PQ via insertItem(key, data)

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

Sorting Using a Priority Queue -given a sequence of N items: a PQ can be used to sort the sequence: -Step 1: Insert N items into the PQ via insertItem(key, data) -Step 2: ___________…

A

Remove the items by calling removeItem() N times-the first remove removes the largest item, the second call the second largest, … the last removes the smallest item

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

Binary Search -uses a _________ and ___________ methodology

A

divideconquer

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

Binary Search -requires data to be ________

A

sorted

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

Binary Search -Runs in _______ time

A

O(lg n)

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

Binary Search -example of divide and conquer

A

looking up a word in a dictionary

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

Bubble Sort 1st run (5), (7), 2, 6, 9, 3 can’t switch 5 and 7 because 7 is larger 5, (7), (2), 6, 9, 3 then 7 and 2 5, 2, (7), (6), 9, 3 switch 7 and 2 because 7 is larger 5, 2, 6, (7), (9), 3 switch 7 and 6 5, 2, 6, 7, (3), (9) switch 9 and 3

A

the largest value has now bubbled to the end

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

Bubble Sort 2nd run (5), (2), 6, 7, 3, 9 2, (5), (6), 7, 3, 9 2, 5, (6), (7), 3, 9 2, 5, 6, (7), (3), 9 2, 5, 6, 3, (7), 9

A

the second largest value has now bubbled to the end

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

Complexity of bubble sort

A

n^2

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

Quicksort Algorithm 1. While data[___________] <= data[______] {++BiggerIndex; }

A

BiggerIndexpivot

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

Quicksort Algorithm 2. While data[___________] > data[_____] {–SmallerIndex; }

A

SmallerIndexpivot

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

Quicksort Algorithm 3. If ___________ < ____________ { swap data[BiggerIndex] and data[SmallerIndex] }

A

BiggerIndexSmallerIndex

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

Quicksort Algorithm 4. While SmallerIndex > BiggerIndex, go to 1

A

SmallerIndexBiggerIndex

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

Quicksort Algorithm 5. Swap data[____________] and data[____________]

A

SmallerIndexpivotIndex

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

Quicksort Algorithm given an array of n ________ (integers) -if array only contains one element, return -else –pick one element to use as ______ –partition elements into two ___-______: —elements less than or equal to pivot —elements greater than pivot

A

elementspivotsub-arrays

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

Quicksort example pivot index = 0 bigger index = 1 smaller index = 8 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 20 <= 40?

A

yes

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

Quicksort example pivot index = 0 bigger index = 2 smaller index = 8 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 10 <= 40?

A

yes

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

Quicksort example pivot index = 0 bigger index = 3 smaller index = 8 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 80 <= 40?

A

no

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

Quicksort example pivot index = 0 bigger index = 3 smaller index = 8 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 100 > 40?

A

yes

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

Quicksort example pivot index = 0 bigger index = 3 smaller index = 7 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 80 | 60 | 50 | 7 | 30 | 100 so is 30 > 40?

A

no

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

Quicksort example pivot index = 0 bigger index = 3 smaller index = 7 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 60 | 50 | 7 | 80 | 100 swap 80 and 30 so is 30 <= 40?

A

yes

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

Quicksort example pivot index = 0 bigger index = 4 smaller index = 7 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 60 | 50 | 7 | 80 | 100 swap 80 and 30 so is 60 <= 40?

A

no

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

Quicksort example pivot index = 0 bigger index = 4 smaller index = 7 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 60 | 50 | 7 | 80 | 100 so is 80 > 40?

A

yes

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

Quicksort example pivot index = 0 bigger index = 4 smaller index = 6 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 60 | 50 | 7 | 80 | 100 so is 7 > 40? so swap 7 and 60

A

no

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

Quicksort example pivot index = 0 bigger index = 4 smaller index = 6 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 7 | 50 | 60 | 80 | 100 so is 7 <= 40?

A

yes

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

Quicksort example pivot index = 0 bigger index = 5 smaller index = 6 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 7 | 50 | 60 | 80 | 100 so is 50 <= 40?

A

no

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

Quicksort example pivot index = 0 bigger index = 5 smaller index = 6 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 40 | 20 | 10 | 30 | 7 | 50 | 60 | 80 | 100 so is 60 > 40? then the bigger index = smaller index

A

yes

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

Quicksort example pivot index = 0 bigger index = 5 smaller index = 4 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 7 | 20 | 10 | 30 | 40 | 50 | 60 | 80 | 100 swap 40 and 7 so what’s the new pivot index?

A

pivotIndex = 4

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

Quicksort Analysis with the assumption the keys are random uniformly distributed, the runtime of QuickSort is usually taken to be ____________

A

O(n lg n)

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

Quicksort to avoid such bad scenarios a better choice of pivot is typically used: use the Median of 3 Rule:

A

pick the median value of 3 elements from the data array as the pivot specifically: data[0], data[n/2], and data[n-1]

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

Quicksort median of 3 rule example: data[0] = 10, data[n/2] = 70, data[n-1] = 50 median of {10, 50, 70} = ?

A

50

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

Quicksort: small arrays for very small arrays (circa n <= 20), quicksort in physical time does not perform as well as __________ ______.

A

insertion sort

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

Quicksort: small arrays And because quicksort is ___________, these cases occur frequently

A

recursive

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

“Quicksort: small arrays common solution: when the array size becomes ““sufficiently”” small _____ ______ ______ quicksort recursively. instead, use a sorting algorithm that is more efficient for small arrays (such as ___________ _____)”

A

do not useinsertion sort

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

worst case time for Selection Sort

A

O(n^2)

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

worst case time for Insertion Sort

A

O(n^2)

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

worst case time for Bubble Sort

A

O(n^2)

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

worst case time for Heap Sort

A

O(n log(n) )

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

worst case time for Merge Sort

A

O(n log(n) )

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

worst case time for Quick Sort

A

O(n^2)

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

________ sort is based on divide and conquer paradigm

A

merge

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

Merge sort consists of three steps. What is the first step?

A

Divide: partition input sequence S into two sequences S1 and S2 of about n/2 elements each

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

Merge sort consists of three steps. What is the second step?

A

Recur: recursively sort S1 and S2

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

Merge sort consists of three steps. What is the third step?

A

Conquer: merge S1 and S2 into a unique sorted sequence

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

MergeSort you may also see MergeSort Trees that: -instead of reversing direction back up the tree -continue down – ______________…

A

merging the branches as they go

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

MergeSort the execution results of a MergeSort can be represented as a _________ _______

A

binary tree

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

MergeSort uses a ________ and ________ method

A

divide conquer

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

MergeSort The height of the tree is _________, where N is the number of items being sorted

A

lg N

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

MergeSort The height of the tree is lg N, where N is the number of items being sorted How do we know that? because lg N is _________________….

A

the number of times N can be divided by 2 (integer wise)

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

Runtime of MergeSort knowing the height of the representative tree is lg N is important because:

A

“it is the ““key concept”” in showing/proving the runtime of MergeSort is O(N lg N)”

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

“Merge sort consists of three steps. The first step ““divide”” has what runtime?”

A

O(1)

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

“Merge sort consists of three steps. The third step ““conquer”” has what runtime?”

A

O(n)

64
Q

“Merge sort consists of three steps. The second step ““recur”” has what runtime?”

A

O(lg n)

65
Q

MergeSort The Tree Proof The height h of the mergesort tree is _______

A

O(lg n)

66
Q

MergeSort The Tree Proof at each recursive call we ______________

A

divide the sequence in half

67
Q

MergeSort The Tree Proof The work done at each level is _______

A

O(n)

68
Q

MergeSort The Tree Proof -at level i, we partition and merge ______ sequences of size _______ (# boxes) * (# things in each box)

A

2^in / 2^i

69
Q

MergeSort The Tree Proof Thus, the total running time of merge-sort is __________

A

O(n lg n)

70
Q

MergeSort Telescoping Proof given T(N) = 2T(N/2) + N prove T(N) = N lg N for N > 1, and also given T(1) = 0 (do algebra) T(N) = 2 * T(N/2) + N T(N) / N = 2 * (N/2) / N + 1 = T(N/2) / (N/2) + 1 = T(N/4) / (N/4) + 1 + 1 = T(N/8) / (N/8) + 1 + 1 + … + 1 = lg N that is T(N) / N = lg N so…

A

T(N) = N lg Nrecall that lg N denotes log base 2 of N

71
Q

Average time for Selection Sort

A

O(n^2)

72
Q

Notes for Selection Sort

A

slow, in placefor small data sets

73
Q

Worst case time for Selection Sort

A

O(n^2)

74
Q

Average time for Insertion Sort

A

O(n^2)

75
Q

Notes for Insertion Sort

A

slow, in placefor small data sets

76
Q

Worst case time for Insertion Sort

A

O(n^2)

77
Q

Average time for Bubble Sort

A

O(n^2)

78
Q

Notes for Bubble Sort

A

slow, in placefor small data sets

79
Q

Worst case time for Bubble Sort

A

O(n^2)

80
Q

Average time for Merge Sort

A

O(n log(n) )

81
Q

Notes for Merge Sort

A

fast, sequential data accessfor huge data sets

82
Q

Worst case time for Merge Sort

A

O(n log(n))

83
Q

Average time for Quick Sort

A

O(n log(n))

84
Q

Notes for Quick Sort

A

assumes key values are random and uniformly distributed

85
Q

Worst case time for Quick Sort

A

O(n^2)

86
Q

What is a tree? in computer science, a tree is…

A

an abstract model of a hierarchical structure

87
Q

A tree consists of…

A

nodes with a parent-child relation

88
Q

Tree applications:

A

organization chartsfile systemsmany others

89
Q

General tree terminology -Root:

A

node without parent

90
Q

General tree terminology -Internal node:

A

node with at least one child

91
Q

General tree terminology -Leaf (aka external node):

A

node without children

92
Q

General tree terminology -Ancestors of a node:

A

parent, grandparent, great-grandparent, etc

93
Q

General tree terminology -Depth of a node:

A

number of ancestors (root has a depth of 0)

94
Q

General tree terminology -Height of a tree:

A

maximum depth of any node

95
Q

General tree terminology -Descendant of a node:

A

child, grandchild, great-grandchild, etc

96
Q

General tree terminology -Size:

A

number of nodes in a tree

97
Q

General tree terminology -Subtree:

A

tree consisting of a node and its descendants

98
Q

Tree terminology -depth of a node p: most often we speak of the depth of nodes and the height of the tree

A

number of ancestors of p

99
Q

Tree terminology -height of a node p: most often we speak of the depth of nodes and the height of the tree

A

the length of the longest path to a leaf from p

100
Q

Tree ADT Nodes will hold _______ and ________ to other nodes

A

data links

101
Q

Tree ADT Generic methods:

A

integer size()boolean isEmpty()objectIterator elements()positionIterator positions()

102
Q

Tree ADT Accessor methods:

A

position root()position parent(p)positionIterator children(p)

103
Q

Tree ADT Query methods:

A

boolean isInternal(p)boolean isLeaf(p)boolean isRoot(p)

104
Q

Tree ADT Update methods: additional update methods may be defined by data structures implementing the Tree ADT

A

swapElements(p, q)object replaceElement(p, o)

105
Q

A Linked Structure for General Trees -a node is represented by an object storing:

A

elementparent nodesequence of children nodes

106
Q

Binary Tree A binary tree is a tree with the following properties: -Each node has ______ children -The children of a node are an _________ ________

A

twoordered pair

107
Q

Binary Tree We call the children of an internal node _________ ________ and ________ ________.

A

left child right child

108
Q

BinaryTree ADT The BinaryTree ADT extends the ________ ADT. (it inherits all the methods of this ADT)

A

Tree

109
Q

A Linked Structure for Binary Trees -a node is represented by an object storing

A

elementparent nodeleft child noderight child node

110
Q

“Balanced Tree A binary tree is balanced if every level above the lowest is ““full”” (contains 2^level nodes) a / \ b c /\ / \ d e f g / \ h i is this tree balanced?”

A

yes

111
Q

A Complete Binary Tree with height h, is a tree such that -_________________________, for ____________________ -nodes at level h fill up ____ to _____

A

level i has 2^i nodes0 <= i <= h-1leftright

112
Q

Sorted Binary Tree a binary tree is sorted if every node in the tree is larger than (or equal to) its _____________________, and smaller than (or equal to) its _____________________ equal nodes can go either left or the right but it has to be ___________

A

left descendantsright descendantsconsistent

113
Q

A full (or proper) binary tree is a tree such that every non-leaf node has ____ children

A

2

114
Q

Generalizing Traversals the 3 tree traversals methods: 1. ___________ 2. ___________ 3. ___________ they are all very similar in nature

A

preorderinorderpostorder

115
Q

Claim about sorting possible to create a _________ __________ -pq sort where the ____ ___________ used to implement it __________ ____ ___________ of the algorithm

A

generic algorithmdata structureaffects the runtime

116
Q

Priority Queue ADT a priority queue (PQ) is a restricted form of a list items are arranged to their priorities (or keys) –keys may or may not be unique a priority queue removes items based on __________

A

priority

117
Q

Queue ADT what does FIFO stand for?

A

first in, first out

118
Q

PQ - Total Order Relation a priority queue must hold a ______ ______ ___________ (example <= )

A

total order relation

119
Q

PQ - Total Order Relation a total order relation has the following properties:

A

-reflexive-antisymmetric-transitive

120
Q

PQ - Total Order Relation -reflexive

A

k <= k

121
Q

PQ - Total Order Relation -antisymmetric

A

if x <= y and y <= x then x = y

122
Q

PQ - Total Order Relation -transitive

A

if a <= band b <= cthen a <= c

123
Q

2 types of PQ

A

min PQmax PQ

124
Q

Min PQ

A

minimum key value is the highest priority

125
Q

Max PQ

A

maximum key value is the highest priority

126
Q

Priority Queue ADT Operations Main Methods of PQs

A
  1. insertItem(key, data)–aka enqueue(key, data)–inserts data into the PQ according to key2. removeItem()–removes the item with the smallest (largest) key—depending if using min PQ or max PQremoveItem() may also be named removeMin() or removeMax() or dequeue()
127
Q

Priority Queue ADT Operations Additional Methods of PQs

A
  1. size()–returns number of elements in PQ2. empty()–returns true if zero elements in PQ3. minItem() / maxItem()–returns item with smallest/largest key4. minKey() / maxKey()–returns smallest/largest key
128
Q

Sorting Using a PQ given a sequence of N items a PQ can be used to sort the sequence Step 1: insert N items into the PQ via ____________

A

insertItem(key, data)

129
Q

Sorting Using a PQ given a sequence of N items a PQ can be used to sort the sequence Step 2: remove the items by calling _________________ N times the first remove removes the largest item, the second call the second largest,…the last removes the smallest item

A

removeItem()

130
Q

Recall doubly linked list

A

prevnext | key data

131
Q

for priority queue, we split elem into two things:

A

key (of type int)data (of type T)

132
Q

so if we have a list of (un)ordered stuff to make it a PQ we need the functions:

A

insertItem(key, data)removeItem()–assume a Min PQ so this removes the item with the smallest key

133
Q

PQ as Unordered List PQ::_____________________ this is just an insertFront() call for the list –like m_list.insertFront(…) recall this is an ____ operation

A

insertItem(key, data)O(1)

134
Q

so if we have a list of unordered stuff to make it a PQ we need the functions: insertItem(key, data) –can be done in ____ removeItem() –requires ____

A

O(1)O(n)

135
Q

let’s say we have a list of ordered stuff to make it a PQ we need the functions: insertItem(key, data) –requires _______ removeItem() –can be done in _______

A

O(n)O(1)

136
Q

Selection and Insertion Sort are:

A

two different implementations of PQ sort

137
Q

Selection sort uses a data structure of

A

unsorted list

138
Q

Insertion sort uses a data structure of

A

sorted list

139
Q

Priority Queues can be implemented using a _______ _______

A

binary heap

140
Q

A heap is a binary tree with two properties:

A

structure propertyheap order property–max heap–min heap

141
Q

Structure Property A heap is a complete binary tree. When a complete binary tree is built, its first node must be the ____

A

root

142
Q

Structure Property The second node is always the ____ ______ of the root.

A

left child

143
Q

Structure Property The third node is always the ____ ______ of the root.

A

right child

144
Q

Structure Property The next nodes always fill the next level from _____-__-______

A

left-to-right

145
Q

Structure Property Each node in a heap contains a ____ that can be compared to other nodes’ ______.

A

keykeys

146
Q

“Heap Order Property For a ““MaxHeap”” The key value of each node is at least as ______ as the key value of its children”

A

large

147
Q

“Heap Order Property For a ““MaxHeap”” The root of the heap is the _______ value in the tree”

A

largest

148
Q

“Heap Order Property For a ““MaxHeap”” The ““max heap property”” requires that each node’s key is _______(operator) the keys of its children”

A

> =

149
Q

“Heap Order Property For a ““MinHeap”” The key value of each node is the ____ __ _______ than the key value of its children”

A

same or smaller

150
Q

“Heap Order Property For a ““MinHeap”” The root of the heap is the ___________ value in the tree”

A

smallest

151
Q

“Heap Order Property For a ““MinHeap”” The ““min heap property”” requires that each node’s key is _______(operator) the keys of its children”

A

<=

152
Q

Heap Implementation A heap could be implemented using a regular binary tree (left and right child pointers) however, a heap is a _________ binary tree so we can use an array or vector instead

A

complete

153
Q

Big Oh int sum = 0; cout &laquo_space;value if (count < 20) { area = (1.0 / 2.0) * base * height; total = total + current;

A

O(1)

154
Q

“Big Oh for (int j = 1; j <= n; j++) { cout &laquo_space;"”this prints n times”” &laquo_space;endl; }”

A

O(n)

155
Q

“Big Oh for (int j = 1; j<= n; j++) { for (int k=1; k <= n; k++) { cout &laquo_space;"”this prints n^2 times”” &laquo_space;endl; } }”

A

O(n^2)

156
Q

“Big Oh for (int j = 1; j <= sqrt(n); j++) { cout &laquo_space;"”this prints n^1/2 times”” &laquo_space;endl; }”

A

O(n^1/2)

157
Q

“Big Oh for (int j = n; j > 0; j /= 2 ) { cout &laquo_space;"”this prints lg n times”” endl; }”

A

O(lg n)

Data Structures (14 decks)

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