Multi-Way Search Trees Chapter 23 5e Test Bank Answers

Chapter 23: Multi-way Search Trees

Multiple Choice Questions:

1) A 2-3 tree is a form of a

a) binary search tree

b) multi-way search tree

c) either a binary or a trinary search tree

d) map

e) set

2) Which of the following is true about a 2-3 tree?

a) A node may contain more than one element

b) A node may have more than two children

c) A 2-node has 0 or 3 children

d) A 2-node has 0 or 3 children

e) All of these statements are true

3) How many levels apart are the leaf nodes in a 2-3 tree?

a) 0

b) 1

c) 0 or 1

d) 0, 1, or 2

e) the number of levels is not specified

4) Which choice below represents the number of children that a node in a 2-3 tree can not have?

a) 0

b) 1

c) 2

d) 3

e) All of these are possible numbers of child nodes in a 2-3 tree.

5) A 2-3 tree contains a single element. How many nodes will the tree have after a new element is inserted?

a) 0

b) 1

c) 2

d) 3

e) It is not possible to predict the number of nodes

6) How many elements can a 2-4 tree hold before it must have more than one node?

a) 5

b) 4

c) 3

d) 2

e) The answer depends on the particular values of the elements.

7) 2-3 tree and 2-4 trees are examples of

a) binary trees

b) binary search trees

c) heaps

d) B-trees

e) None of these is correct

8) When working with different B-trees for a given number of elements, as the order of the B-tree goes up, the number of nodes in the B-tree tends to

a) go down

b) go up as well

c) stay the same

d) oscillate between two values

e) none of the above

9) A -Tree improves on a B-tree by offering

a) fewer nodes

b) more nodes

c) sequential access to all elements of the tree

d) fewer levels

e) more levels

10) B-Trees were introduced to address which constraint in the design of efficient binary tree algorithms?

a) the execution speed of the computer

b) the version of the operating system that is installed

c) sparsely populated trees

d) problems in which all of the elements may not fit in memory at the same time

e) None of these is correct.

11) In a B-tree of order 6, each internal node other than the root node has at least ____ elements and at least ________ children.

a) 6, 5

b) 5, 6

c) 6, 6

d) 3, 2

e) 2, 3

12) A B-tree is a search tree. What is the efficiency of searching for an element in a B-tree?

a) O(1)

b) O(n)

c) O(log n)

d) O(n log n)

e) O()

13) The height of a 2-3 tree increases

a) down from the leaf nodes

b) when they use secondary storage

c) up from the root node

d) when an element is removed

e) none of the above

14) When removing an element from a 2-3 tree, rotation and ______ may both be employed to maintain the properties of the B-tree.

a) reducing the height of the tree

b) increasing the height of the tree

c) reflection

d) reinsertion

e) None of these is correct

15) The non-leaf root of a B-tree of order m has a minimum of how many children?

a) 0

b) 1

c) 2

d) m/2

e) None of these is correct

True/False Questions:

1) In a 2-3 tree, each element is in its own node.

2) The root node of a 2-3 tree is always a 2-node.

3) Inserting an element into a 2-3 tree may add more than one node to the tree.

4) The easiest element to remove from a 2-3 tree is an element that is in a 3-node that is a leaf node.

5) A 2-4 tree extends the concept of a 2-3 tree by allowing a node to have 1, 2, or 3 elements and 0, 2, 3, or 4 children.

6) The height of a 2-3 tree increases when an element is inserted.

7) Rotation may be used when deleting an element from a 2-3 tree to maintain the balance and properties of a 2-3 tree.

8) A -Tree ensures that each non-root node in the tree is at least 2/3 full.

9) A linked representation of a B-tree is the best way to implement the collection, regardless of the amount of data to be held in the tree.

10) The middle child node of a 3-node in a 2-3 tree has one or two elements whose values are between the values of the elements in the parent node.

1) Explain the difference between a 2-node and a 3-node.

2) When does a 2-node become a 3-node?

3) Where are elements inserted into a 2-3 tree? Is your answer different if it is a 2-4 tree? What about if it is a B-tree?

4) A new 2-3 tree is created. Explain the steps in inserting the following elements in this order into the initially empty tree: 13, 23, 17.

Inserting 13 involves creating a node for the root and inserting the element with 13 into it. The root element is now a 2-node and is a leaf node. The tree looks like this:

(13)

Inserting 23 into the tree containing 13 involves adding the element 23 to the leaf node containing 13. The root node is now a 3-node and is still a leaf node. The tree looks like this:

(13 23)

Inserting 17 into the tree involves locating the leaf node for the insertion, which is the root node, then adding it to the node. However, the node cannot hold another element, so it is split, and the middle element, 17, is moved up. A new root node is created and 17 is added to it, with the node containing 13 as the left node and the node containing 23 as the right node. The root node has 17. The tree looks like this:

(17)

/ \

(13) (23)

All nodes are now 2-nodes. The nodes containing 13 and 23 are leaf nodes.

5) Starting with the 2-3 tree from question 4), insert the elements 19 and 29. Sketch the tree after each insertion.

(17)

/ \

(13) (19 23)

Inserting 29 will lead to the same leaf node containing 19 and 23. However, inserting 29 violates the number of elements in a node, so the middle element, 23, is moved up to share the root node with 17. The tree looks like this:

(17 23)

/ \

(13) (19 29)

However, this still violates the rules for a 2-3 tree. The root node is a 3-node but it only has 2 children. The right leaf node is split into two leaf nodes. The resulting tree is now:

(17 23)

/ | \

(13) (19) (29)

The root is a 3-node and has 3 children. Each leaf node is a 2-node.

6) Starting with the 2-3 tree from question 5), remove the element 17. Sketch the tree.

(19 23)

/ \

(13) (29)

However, the root node is a 3-node with only 2 children. Rotate 19 down to the left child node, which makes the root of the tree a 2-node. The tree now looks like this:

(23)

/ \

(13 19) (29)

7) Sketch the tree that results from removing element 35 from the tree below:

(45)

/ \

(30) (60 82)

/ \ / \

(22) (35 50) (51 55) (87)

(45)

/ \

(30) (60 82)

/ \ / \

(22) (50) (51 55) (87)

8) An internal 4-node in a 2-4 tree has 3 elements and 4 children. The elements, in ascending order, are e1, e2, and e3. The child nodes, from left to right, are c1, c2, c3, and c4. What is the relation between the elements in the node and the children of the node?

9) What event occurs to increase the height of a 2-3 tree?

10) What is the concern about secondary storage when working with a search tree?

11) Are there improvements on the concept of a B-tree?

12) What issues need to be considered when designing a linked implementation of a B-tree?

13) What is involved in using a B-tree as a search tree?

14) In a B-tree of order m, how many elements can be inserted into the tree before a new node is created?

15) What is the maximum number of elements that can be held in a two-level B-tree of order 4?