Questions Chapter 10 Flashcards
A 2-3-4 tree is a multiway tree with up to ______ keys and ______ children per node.
up to three keys and four children per node
In a multiway tree, the keys in a node are arranged in __________ order.
ascending
In a 2-3-4 tree, all insertions are made in ______ node(s), and all the _____ nodes are on the same level
all insertions made in leaf nodes, all leaf nodes on same level
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
2-node has one key, two children
3-node has two keys, three children
4-node has three keys, four children
True or False: there is no 1-node in a 2-3-4 tree
True
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.
down
Splitting the ______ creates two new nodes; splitting any other node creates _____ new node
splitting the root creates two new nodes, splitting any other node creates one new node.
The height of a 2-3-4 tree can increase only when ___________________.
the root is split
Search times in a 2-3-4 tree is proportional to ______
height
True or False: the 2-3-4 tree is efficient because all the nodes are full
False
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.
three
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
find the appropriate leaf, perform splits, upward direction
A ______ tree is a multiway tree in which each node may have dozens or hundreds of keys and children
b-tree
There is always one more ______ than there are ______ in a b-tree node
one mor child than there are keys in a b-tree node
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
b. two, three, or four children
A 2-3-4 tree is superior to a binary search tree in that it is _________
balanced
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 _____
2
True or False: Data items are located exclusively in leaf nodes
False
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
a. exactly one new node is created
A 2-3-4 tree increases its number of levels when ________
root split
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
a. splitting nodes on the way down if necessary
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?
2
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
c. when the parent is split, child 2 must…
What is the efficiency of a 2-3 tree?
O(logN)
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
d. finding the place to write data is slow, but a lot of data can be written quickly.
True or False: Node splits in a B-tree have similarities to node splits in a 2-3 tree
True
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
a. keys and their corresponding blocks
