Multi-Way Search Trees Chapter 23 Full Test Bank

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

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.

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

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

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

(45)

/ \

(30) (60 82)

/ \ / \

(22) (35 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?