Questions Chapter 12

Question 1

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

Answer 1

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

Question 2

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

Answer 2

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

Question 3

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

Answer 3

root

Question 4

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

Answer 4

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

Question 5

A heap can be represented by an array because a heap

Answer 5

is a binary tree

Question 6

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

Answer 6

c. on the bottom row

Question 7

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

Answer 7

linked list

Question 8

Insertion into a descending heap involves trickle ______.

Answer 8

up

Question 9

A heap is an implementation of an ADT ____________

Answer 9

priority queue

Question 10

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

Answer 10

O(N*logN)

Question 11

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

Answer 11

root

Question 12

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

Answer 12

False

Question 13

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

Answer 13

array, representing a complete binary tree

Question 14

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

Answer 14

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

Question 15

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

Answer 15

trickled up

Question 16

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

Answer 16

removed from the root

Question 17

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 ________

Answer 17

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