Q5Cisp430

Front 1

Suppose that a binary taxonomy tree includes 8 animals. What is the minimum number of NONLEAF nodes in the tree?

Back 1

7

Front 2

Select the one FALSE statement about binary trees:

Back 2

Every binary tree has at least one node.

Front 3

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40

Which statement is correct?

Back 3

The tree is neither complete nor full.

Front 4

Suppose that a B-tree has MAXIMUM of 10 and that a node already contains the integers 1 through 10. If a new value, 11, is added to this node, the node will split into two pieces. What values will be in these two pieces?

Back 4

The first piece will have 1 through 5 and the second piece will have 7 through 11

Front 5

Which statement is true for a B-tree?

Back 5

All leaves are at the exact same depth.

Front 6

Consider the tree at the following. Which nodes are siblings with each other?

Back 6

2 and 4; 3 and 5; 6 and 7.

Front 7

Suppose that we have a tree where the left subtree contains 3000 nodes and the right subtree contains 100 nodes. For post-ordertraversal, how many nodes are processed before the root node?

Back 7

3100

Front 8

How many comparisons is needed to search for pear in the following search tree?

Back 8

3

Front 9

Which of the description of the erase_one function in section 10.5 is the most appropriate?

Back 9

If target was in the bag, then one copy of target has been removed from the bag; otherwise the bag is unchanged. A true return value indicates that one copy was removed; false indicates that nothing was removed.

Front 10

Here is an output from the tree-printing function for a tree of integers:

Back 10

Front 11

Consider the tree at the following. What is the depth of the tree?

Back 11

3

Front 12

For the tree at the following, what additions will make the tree complete?

Back 12

To make a complete tree, add a left and right child to node 3.

Front 13

What is meant by loose insertion?

Back 13

A loose insertion allows the top node of a subtree to temporarily hold one too many entries.

Front 14

Add one entry, 15, to the following heap what will be the new heap?

Back 14

Front 15

Which statement of the following is the most appropriate?

Back 15

The STL includes a priority queue class as well as algorithms for building and manipulating heaps.

Front 16

Which of the following description about B-tree (section 11.3) is the the most appropriate?

Back 16

Each node in a B-tree may contain more than one entry.

Front 17

Why is a stub useful?

Back 17

It is useful for writing and testing functions one at a time.

Front 18

Which of the following description about B-tree (section 11.3) is the the most appropriate?

Back 18

The number of children for a nonleaf node in a B-tree is exactly one more than the number of entrie.

Front 19

Start with an empty B-tree, with MINIMUM set to 1. Enter the integers 1 through 10. What would be the resulting tree?

Back 19

Front 20

what is the value of the following logarithm?log 10 100

Back 20

2

Front 21

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40

What is the minimum number of nodes in a full binary tree with depth 3?

Back 21

15

Front 22

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40

What is the order of nodes visited using a pre-order traversal? (Ch10)

Back 22

14 2 1 3 11 10 7 30 40

Front 23

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40How many descendants does the root have?

Back 23

8

Front 24

What feature of heaps allows them to be efficiently implemented using a partially filled array?

Back 24

Heaps are complete binary trees.

Front 25

Suppose that a non-leaf node in a B-tree has 41 entries. How many children will this node have?

Back 25

42

Front 26

Look at the tree at the following, in what order are the letters printed for an in-order traversal?

Back 26

The in-order traversal prints O, L, R, A, G, T.

Front 27

What is the depth of the node that contains me!?

Back 27

The node containing me! has a depth of two.

Front 28

Suppose that we have a tree where the left subtree contains 3000 nodes and the right subtree contains 100 nodes. For in-order traversal, how many nodes are processed before the root node?

Back 28

3000

Front 29

What statement about the traversal methods for general trees where there is no limit to the number of children that a node may have is more accurate?

Back 29

Pre-order and post-order make sense but in-order doesn’t for a general tree.

Front 30

What is the depth of the tree at the following?

Back 30

3

Front 31

What would be the most appropriate description of the following declaration?private: Item data_field; tree_node *parent_ptr; tree_node *links[4];

Back 31

It is a member variables for a node definition that could be used for a tree where each node has up to four children, and each node also has a pointer to its parent. The note stores the children pointers in an array of four pointers.

Front 32

Why is it bad to insert nodes from smallest to largest in a binary search tree?

Back 32

The nodes will be inserted into the bag from smallest to largest, resulting in a tree with a single path with only right children.

Front 33

Which of the following is one of the heap storage rules?

Back 33

The entry contained by a node is never less than the entries of the node’s children.

Front 34

what is the value of the following logarithm?log 2 32

Back 34

5

Front 35

Which of the following description about B-tree (section 11.3) is the the most appropriate?

Back 35

In a B-tree, the searcher must choose among more than just two possible children.

Front 36

How are subtrees stored in the B-tree set implementation in the chapter 11?

Back 36

Each subtree is stored as a set object. The parent of each subset stores pointers to the smaller set objects.

Front 37

What are the worst-case time for adding, deleting, and searching in a B-tree?

Back 37

All of them are O( log n ).

Front 38

Why is a new entry to a heap initially placed at its location?

Back 38

The reason is to maintain a complete binary tree

Front 39

Suppose MINIMUM is 200 for a B-tree, what is the maximum number of children that a node may have?

Back 39

The maximum number of children that a node may have is 401, although during an insertion, we may temporarily have a node with 402 children

Front 40

Add 15 first, 11 second, 14 third, 12 fourth, and 13 fifth to the following heap what will be the new heap?

Back 40

Front 41

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40

How many children does the root have?

Back 41

2

Front 42

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40How many of the nodes have at least one sibling?

Back 42

6

Front 43

How many recursive calls usually occur in the implementation of the tree_clear function for a binary tree? (Ch10)

Back 43

2

Front 44

Tree algorithms typically run in time O(d) . What is d?

Back 44

The depth of the tree.

Front 45

Suppose that we have implemented a priority queue by storing the items in a heap (using an array for the heap items). We are now executing a reheapification upward and the out-of-place node is at data[i] with priority given by data[i]. Which of the following boolean expressions is TRUE to indicate that the reheapification IS NOT YET DONE.

Back 45

(i > 0) && (data[(i-1)/2] < data[i])

Front 46

Consider the tree at the following. Which nodes are leaves?

Back 46

3, 4, 6, and 7

Front 47

Suppose that we have a tree where the left subtree contains 3000 nodes and the right subtree contains 100 nodes. For pre-order traversal, how many nodes are processed before the root node?

Back 47

zero.

Front 48

What is the base case for the recursive function tree_clear?

Back 48

The base case is when the tree is empty (the root pointer is NULL).

Front 49

Consider a complete binary tree with exactly 10,000 nodes, implemented with an array. Suppose that a node has its value stored in location 4999. Where is the value stored for this node’s parent?

Back 49

The parent is stored at index 2499.

Front 50

Consider the tree at the following, what is the order of the nodes processed in a post-order traversal?

Back 50

3, 6, 7, 5, 2, 4, 1

Front 51

What statement of the following is the most appropriate?

Back 51

Trees may be implemented with either fixed-sized arrays or dynamic data structures. An array is particularly appropriate for complete binary trees because of the conditions that require the nodes of a complete tree to occur in specific locations.

Front 52

Consider a complete binary tree with exactly 10,000 nodes, implemented with an array. Suppose that a node has its value stored in location 4999. Where is the value stored for its left child?

Back 52

The left child is stored at index 9999.

Front 53

Suppose MINIMUM is 200 for a B-tree, what is the minimum number of children that a nonleaf, nonroot node may have?

Back 53

The minimum number of children that a nonleaf, nonroot node may have is 201, although during a removal we may temporarily have a node with 200 children.

Front 54

Which of the following description of the top function (section 11.2) is the the most appropriate?

Back 54

Returns the highest priority item of the queue (without removing it). If there are several equally high priorities, the implementation may decide which one to return.

Front 55

Which of the following is one of the heap storage rules?

Back 55

The tree is a complete binary tree, so that every level except the deepest must contain as many nodes as possible; and at the deepest level, all the nodes are as far left as possible

Front 56

Which statement of the following is the most appropriate?

Back 56

The tree algorithms that we have seen for binary search trees, heaps, and B-trees all have worst-case time performance of O(d), where d is the depth of the tree.

Front 57

How is a loose insertion eventually fixed?

Back 57

The problem is fixed by splitting the node with too many entries. After the split, one new node contains the entries before the middle, another new node contains the entries after the middle, and the middle entry itself has been passed upward to a higher level.

Front 58

Which of the following description of the pop function (section 11.2) is the the most appropriate?

Back 58

Removes the highest priority item of the priority queue.

Front 59

Which statement of the following is the most appropriate?

Back 59

The depth of a heap or B-tree is never more than O(log n), where n is the number of nodes. Hence, the operations on these structures are also O(log n).

Front 60

Suppose MINIMUM is 200 for a B-tree, what is the maximum number of entries that a node may contain?

Back 60

The maximum number of entries that a node may contain is 400, although during an insertion we may temporarily have a node with 401 entries

Front 61

Consider the binary_tree_node from page 486. Which expression indicates that t represents an empty tree?

Back 61

(t == NULL)

Front 62

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40

What is the order of nodes visited using a post-order traversal?

Back 62

1 3 2 7 10 40 30 11 14

Front 63

What is the minimum number of nodes in a complete binary tree with depth 3?

Back 63

8

Front 64

Which formula is the best approximation for the depth of a heap with n nodes?

Back 64

log (base 2) of n

Front 65

Suppose that we have implemented a priority queue by storing the items in a heap. We are now executing a reheapification downward and the out-of-place node has priority of 42. The node's parent has a priority of 72, the left child has priority 52 and the node's right child has priority 62. Which statement best describes the status of the reheapification.

Back 65

The next step will swap the out-of-place node with its right child

Front 66

What statement of the following is the most appropriate?

Back 66

Trees are a nonlinear structure, with many applications, including organizing information (such as taxonomy trees) and implementing an efficient version of the bag class (using binary search trees).

Front 67

What statement is the most appropriate for the big square of the following tree?

Back 67

The big square include all nodes that are descendants of Mom node.

Front 68

Look at the tree at the following, in what order are the numbers printed for a post-order traversal?

Back 68

The post-order traversal prints 13, 9, 53, 17, 19, 7, 4, 11, 14.

Front 69

What statement is the most appropriate for the following tree?

Back 69

It is a full and complete binary taxonomy tree with 16 animals.

Front 70

What statement of the following is the most appropriate?

Back 70

Operations on trees are good candidates for recursive thinking. This is because many tree operations include a step to process one or more subtrees, and this step is “a smaller version of the same problem.”

Front 71

What statement of the following is the most appropriate?

Back 71

Binary search trees are one common application of trees, which permit us to store a bag of ordered items in a manner where adding, deleting, and searching for entries is potentially much faster than with a linear structure.

Front 72

What would be the binary search tree with the following words (inserted in this order): blueberry, peach, apricot, pear, cherry, mango, and papaya?

Back 72

Front 73

what is the value of the following logarithm?log 3 81

Back 73

4

Front 74

what is the value of the following logarithm?log 16 256

Back 74

2

Front 75

Suppose MINIMUM is 200 for a B-tree, what is the minimum number of entries that a nonroot node may have?

Back 75

The minimum number of entries that a nonroot node may have is 200, although during a removal we may temporarily have a node with 199 entries

Front 76

Where is a new entry to a heap initially placed?

Back 76

A new entry to a heap is initially placed in the leftmost available location in the deepest level.

Front 77

Which of the following description of the size function (section 11.2) is the the most appropriate?

Back 77

Returns the number of items in the queue.

Front 78

Which statement of the following is the most appropriate?

Back 78

A B-tree is a tree for storing entries in a manner that follows six rules. The first two rules specify the minimum and maximum number of entries for each node. The third rule requires each node’s entries to be sorted from smallest to largest. Rules 4 and 5 indicate how many subtrees a nonleaf node must have and impose an order on the elements of the subtrees. The last rule requires each leaf to be at the same depth.

Front 79

Remove the number 8 and then 3 from the following B-tree, what is the resulting tree after the removal?

Back 79

Front 80

In the description of reheapification upward, we specified that the out-of-place entry must be swapped with ________________________.

Back 80

its parent with a less value, or when it reaches the root.

Front 81

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40

What is the value stored in the parent node of the node containing 30?

Back 81

11

Front 82

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40What is the order of nodes visited using an in-order traversal?

Back 82

1 2 3 14 7 10 11 40 30

Front 83

Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored?

Back 83

data[2*i + 2]

Front 84

Suppose you run a O(log n) algorithm with an input size of 1000 and the algorithm requires 110 operations. When you double the input size to 2000, the algorithm now requires 120 operations. What is your best guess for the number of operations required when you again double the input size to 4000?

Back 84

130

Front 85

Select the true statement about the worst-case time for operations on heaps.

Back 85

Both insertion and removal are better than linear.

Front 86

What statement of the following is the most appropriate?

Back 86

A parameter of a function may be a function itself.

Front 87

What is the depth of a tree with no nodes?

Back 87

The depth of an empty tree is –1.

Front 88

What would be the most appropriate description of the following tree?

Back 88

It is representation of a small binary tree with three nodes containing integers. The tree has 10 in the root, 20 in the left child of the root, and 30 in theright child of the root

Front 89

How many comparisons is needed to search for blueberry in the following search tree?

Back 89

1

Front 90

What is the depth of a tree with only a root node?

Back 90

The depth of a tree with only a root is zero.

Front 91

Look at the tree at the following, in what order are the numbers printed for a pre-order traversal?

Back 91

The pre-order traversal prints 14, 17, 9, 13, 53, 11, 4, 19, 7.

Front 92

Consider the tree at the following, what is the output from this tree with the tree-printing function fromsection 10.4?

Back 92

Front 93

Start with an empty heap of integers, and enter the 10 numbers 1 through 10. Draw the resulting heap.

Back 93

Front 94

Suppose MINIMUM is 1000 for a B-tree, the tree has a root and one level of 1000 nodes below that. What is the minimum number of entries that this tree might have?

Back 94

The root has 999 entries, and each of the 1000 nodes at the next level has minimum of 1000 entries. Therefore, the total minimum number of entries in the tree is 1,000,999 entries.

Front 95

Which of the following is one of the heap storage rules?

Back 95

A heap is a binary tree where the entries of the nodes can be compared with the less-than operator of a strict weak ordering.

Front 96

what is the value of the following logarithm?log 37 1

Back 96

0

Front 97

What are two factors to consider when using external B-trees?

Back 97

The total number of accesses to the secondary memory devices should be minimized. Also, ensure that each node is stored in a contiguous area of the disk.

Front 98

Which statement of the following is the most appropriate?

Back 98

A heap is a complete binary tree that follows the rule that the entry at any node is never less than any of its children’s entries. Heaps provide an efficient implementation of priority queues.

Front 99

Remove four entries from the following heap what will be the new heap?

Back 99

Front 100

Remove three entries from the following heap what will be the new heap?

Back 100

Front 101

Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?

Back 101

3

Front 102

Select the one true statement.

Back 102

A binary tree could be neithercomplete nor full

Front 103

14 / \ 2 11 / \ / \ 1 3 10 30 / / 7 40What is the depth of the tree?

Back 103

3

Front 104

Suppose that X is a B-tree leaf containing 41 entries and having at least one sibling. Which statement is true?

Back 104

Any sibling of X is also a leaf.

Front 105

If a heap is implemented using a partially filled array called data, and the array contains n elements (n > 0), where is the entry with the greatest value?

Back 105

data[0]

Front 106

Consider a complete binary tree with exactly 10,000 nodes, implemented with an array. Suppose that a node has its value stored in location 4999. Where is the value stored for its right child?

Back 106

There is no right child.

Front 107

What statement is the most appropriate for the following f1 function? template int f1(binary_tree_node node){ int answer = 0; if (node->left( )!= NULL) ++answer; if (node->right( )!= NULL) ++answer; eturn answer;}

Back 107

The f1 function computes the number of children that a node has.

Front 108

What statement is the most appropriate for the following tree?

Back 108

It is a neither complete nor full binary tree with 12 nodes. The root is circled, and each leaf has an asterisk. There are two nodes that are siblings, and they are connected with a wiggly line. All of the ancestors of one of the leaves are shaded.

Front 109

How many comparisons is needed to search for orange in the following search tree?

Back 109

5

Front 110

Look at the tree at the following, in what order are the letters printed for a backward in-order traversal?

Back 110

The backward in-order traversal prints T, G, A, R, L, O.

Front 111

What statement of the following is the most appropriate?

Back 111

A tree traversal consists of processing a tree by applying some action to each node. Three common traversal methods—pre-order traversal, in-order traversal, and post-order traversal—differ only in the order in which the nodes are processed. A backward in-order traversal is a quick and convenient way to print the data from a tree in a readable format

Front 112

What is the best statement about the following function, f1?

void f1 (int i){ int j; for (j = 0; j < i; ++j); cout << ‘*’; cout << endl;}

Back 112

The f1 function prints a star.

Front 113

What is a stub?

Back 113

A stub is a function with a single line that simply prints the name of the function, indicating that it has been activated.

Front 114

Which of the following description of the empty function (section 11.2) is the the most appropriate?

Back 114

Returns true if the queue is empty (otherwise returns false).

Front 115

what is the value of the following logarithm?log 5 125

Back 115

3

Front 116

Add 15 first, 11 second, and 14 third to the following heap what will be the new heap?

Back 116

Front 117

Add 15 first, 11 second, 14 third, and 12 fourth to the following heap what will be the new heap?

Back 117

Front 118

Remove one entry from the following heap what will be the new heap?

Back 118

Front 119

Add 15 first and 11 second to the following heap what will be the new heap?

Back 119

Front 120

After an item is removed from a heap, which item is placed in the root?

Back 120

When an item is removed from a heap, the last entry of the deepest level is placed in the root.