Questions Chapter 12 Flashcards

1
Q

What does the term “complete” mean when applied to binary trees?

A

all the rows are filled with nodes, except possibly the bottom one.

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

What does the term weakly ordered mean when applied to heaps?

A

both the right and left children have keys less than (or equal to) the parent

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

In a heap, a node is always removed from the _____.

A

root

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

To “trickle up” a node in a descending heap means:

a. to repeatedly exchange it with its parent until it’s larger than its parent
b. to repeatedly exchange it with its child until it’s larger than its child
c. to repeatedly exchange it with its child until it’s smaller than its child
d. to repeatedly exchange it with its parent until it’s smaller than its parent

A

a. to repeatedly exchange it with its parent until it’s larger than its parent

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

A heap can be represented by an array because a heap

A

is a binary tree

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

The last node in a heap is always:

a. a left child
b. a right child
c. on the bottom row
d. never less than its sibling

A

c. on the bottom row

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

A heap is to a priority queue as a(n) __________ is to a stack

A

linked list

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

Insertion into a descending heap involves trickle ______.

A

up

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

A heap is an implementation of an ADT ____________

A

priority queue

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

removal of the largest item, insertion in a heap is _______ time

A

O(N*logN)

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

In a heap, the largest item is always at the ______

A

root

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

True or False: Heaps support ordered traversal of the data, locating an item with a specific key, and deletion.

A

False

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

A heap is usually implemented as a(n) ______ representing a complete ______ tree.

A

array, representing a complete binary tree

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

Each node has a key __________ than its parents and __________ than its children

A

each node has a key less than its parents and greater than its children

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

An item to be inserted in a heap is always placed in the first vacant cell of the array and then trickled ____ to its appropriate position

A

trickled up

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

When an item is removed from the _____ of a heap, it’s replaced by the last item in the array, which is then trickled down to its appropriate position

A

removed from the root

17
Q

Changing the priority of a item can be changed in a heap. First the _____ is changed, then the item is trickled _____ if the item is ________

A

key is changed, key is increased, item trickled up.