Questions Chapter 10

Question 1

A 2-3-4 tree is a multiway tree with up to ______ keys and ______ children per node.

Answer 1

up to three keys and four children per node

Question 2

In a multiway tree, the keys in a node are arranged in __________ order.

Answer 2

ascending

Question 3

In a 2-3-4 tree, all insertions are made in ______ node(s), and all the _____ nodes are on the same level

Answer 3

all insertions made in leaf nodes, all leaf nodes on same level

Question 4

In a 2-3-4 tree, a 2-node has ____ key(s) and _____ child/children, a 3-node has ____ key(s) and _____ child/children, and a 4-node has _____ key(s) and ______ child/children

Answer 4

2-node has one key, two children
3-node has two keys, three children
4-node has three keys, four children

Question 5

True or False: there is no 1-node in a 2-3-4 tree

Answer 5

True

Question 6

Insertion into a 2-3-4 tree requires than any full node be split on the way _____ the tree, during the search for insertion point.

Answer 6

down

Question 7

Splitting the ______ creates two new nodes; splitting any other node creates _____ new node

Answer 7

splitting the root creates two new nodes, splitting any other node creates one new node.

Question 8

The height of a 2-3-4 tree can increase only when ___________________.

Answer 8

the root is split

Question 9

Search times in a 2-3-4 tree is proportional to ______

Answer 9

height

Question 10

True or False: the 2-3-4 tree is efficient because all the nodes are full

Answer 10

False

Question 11

A 2-3 tree is similar to a 2-3-4 tree, except that it can have only one or two data items and up to _______ children.

Answer 11

three

Question 12

Insertion in a 2-3 tree involves finding the appropriate ________ and then performing ________ from the from the insertion point in the _________ direction, until a non-full node is found

Answer 12

find the appropriate leaf, perform splits, upward direction

Question 13

A ______ tree is a multiway tree in which each node may have dozens or hundreds of keys and children

Answer 13

b-tree

Question 14

There is always one more ______ than there are ______ in a b-tree node

Answer 14

one mor child than there are keys in a b-tree node

Question 15

A 2-3-4 tree is so named because a node can have:

a. three children and four data items
b. two, three, or four children
c. two parents, three children, and four items
d. two parents, three items, and four children

Answer 15

b. two, three, or four children

Question 16

A 2-3-4 tree is superior to a binary search tree in that it is _________

Answer 16

balanced

Question 17

Imagine a parent node with data items 25, 50, and 75. If one of its child nodes had items with values 60 and 70, it would be child numbered _____

Answer 17

2

Question 18

True or False: Data items are located exclusively in leaf nodes

Answer 18

False

Question 19

Which of the following is NOT true each time a node is split?

a. exactly one new node is created
b. exactly one new data item is added to the tree
c. one data item moves from the split node to its parent
d. one data item moves from the split node to its new sibling

Answer 19

a. exactly one new node is created

Question 20

A 2-3-4 tree increases its number of levels when ________

Answer 20

root split

Question 21

Searching a 2-3-4 tree does NOT involve:

a. splitting nodes on the way down if necessary
b. picking the appropriate child to go to, based on data items in a node
c. ending up at a leaf node if the search key is not found
d. examining at least one data item in any node visited

Answer 21

a. splitting nodes on the way down if necessary

Question 22

After a non-root node of a 2-3-4 tree is split, does its new right child contain the item previously numbered 0, 1, or 2?

Answer 22

2

Question 23

Which of the following statements about a node-splitting operation in a 2-3 tree is NOT true:

a. the parent of a split node must also be split if it is full
b. the smallest item in the node being split always stays in the node
c. when the parent is split, child 2 must always be disconnected from its old parent and connected to the new parent
d. the splitting process starts at a leaf and works upward

Answer 23

c. when the parent is split, child 2 must…

Question 24

What is the efficiency of a 2-3 tree?

Answer 24

O(logN)

Question 25

In accessing data on a disk drive:

a. inserting data is slow, but finding the place to write data is fast
b. moving data to make room for more data is fast because so many items can be accessed at once
c. deleting data is unusually fast
d. finding the place to write data is comparatively slow but a lot of data can be written quickly

Answer 25

d. finding the place to write data is slow, but a lot of data can be written quickly.

Question 26

True or False: Node splits in a B-tree have similarities to node splits in a 2-3 tree

Answer 26

True

Question 27

In external storage, indexing means keeping a file of:

a. keys and their corresponding blocks
b. records and their corresponding blocks
c. keys and their corresponding records
d. last names and their corresponding keys

Answer 27

a. keys and their corresponding blocks