1. Which of the following is the most widely used external memory data structure?
a) AVL tree
c) Red-black tree
d) Both AVL tree and Red-black tree
In external memory, the data is transferred in form of blocks. These blocks have data values and pointers. And B-tree can hold both the data values and pointers. So B-tree is used as an external memory data structure.
2. B-tree of order n is a order-n multiway tree in which each non-root node contains __________
a) at most (n – 1)/2 keys
b) exact (n – 1)/2 keys
c) at least 2n keys
d) at least (n – 1)/2 keys
B-tree of order n is an order-n multiway tree in which each non-root node contains at least (n – 1)/2 keys.
A non-root node in a B-tree of order n contains at least (n – 1)/2 keys. And contains a maximum of (n – 1) keys and n sons.
3. A B-tree of order 4 and height 3 will have a maximum of _______ keys.
A B-tree of order m of height h will have the maximum number of keys when all nodes are completely filled. So, the B-tree will have n = (mh+1 – 1) keys in this situation. So, required number of maximum keys = 43+1 – 1 = 256 – 1 = 255.
4. Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
If s splits occur in a B-tree, 2s + 1 nodes are written (2 halves of each split and the parent of the last node split). So, if 5 splits occurred, then 2 * 5 + 1, i.e. 11 nodes are written.
5. B-tree and AVL tree have the same worst-case time complexity for insertion and deletion.
B-tree and AVL tree have the same worst-case time complexity for insertion and deletion. Both the B-tree and the AVL tree have O(log n) as worst-case time complexity for insertion and deletion.
6. 2-3-4 trees are B-trees of order 4. They are an isometric of ________ trees.
2-3-4 trees are isometric of Red-Black trees. It means that, for every 2-3-4 tree, there exists a Red-Black tree with data elements in the same order.
7. Which of the following about B-tree is true?
a) larger the order of the B-tree, the less frequently the split occurs
b) larger the order of the B-tree, the more frequently the split occurs
c) smaller the order of the B-tree, the more frequently the split occurs
d) smaller the order of the B-tree, the less frequently the split occurs
The average probability of the split is 1/(⌈m / 2⌉ – 1), where m is the order of the B-tree. So, if m is larger, the probability of split will be less.
8. What is the best case height of a B-tree of order n and which has k keys?
a) logn (k+1) – 1
c) logk (n+1) – 1
B-tree of order n and with height k has best case height h,
where h = logn (k+1) – 1.
The best-case occurs when all the nodes are completely filled with keys.
9. Compression techniques can be used on the keys to reducing both space and time requirements in a B-tree.
The front compression and the rear compression are techniques used to reduce space and time requirements in B-tree. The compression enables to retention of more keys in a node so that the number of nodes needed can be reduced.
1. State true or false: B+ trees are not always balanced trees.
B+ trees are always balanced. Every path from the root to the leaf of the tree is of the same length.
2. What are the leaf nodes in a B+ tree?
a) The topmost nodes
b) The bottommost nodes
c) The nodes in between the top and bottom nodes
d) None of the mentioned
The bottommost nodes that mark the end of a tree are known as the leaf nodes in a B+ tree.
3. Non-leaf nodes are also called as __________
a) Internal nodes
b) External nodes
c) Middle nodes
d) Primary nodes
Non-leaf nodes are also known as internal nodes. A non-leaf node may hold up to n pointers and should hold at least n/2 pointers.
4. The queries used to find all records with search key values in a particular range are known as ________
a) Gap queries
b) Graph queries
c) Range queries
d) None of the mentioned
The queries used to find all records with search key values in a particular range are known as Range queries. These types of queries are executed using procedures.
5. Statement 1: Insertion of record might require the change in position of the initial nodes.
Statement 2: Deletion of records might require a change in the position of the initial nodes.
a) Both the statements are true
b) Statement 1 is true but statement 2 is false
c) Statement 2 is true but statement 1 is false
d) Both the statements are false
Both insertion and deletion of records might require the change in position of the initial nodes because the new data value might not exactly fit into the B+ tree. Thus rotation of the nodes is generally required.
6. If a relation can have more than one record containing the same search key value, the search key is said to be a __________
a) Unique search key
b) Non-unique search key
c) Multiple search key
d) Identical search key
If a relation can have more than one record containing the same search key value, the search key is said to be a non-unique search key. A problem with non-unique search keys is inefficiency during delete operations.
7. State true or false: The fanout of nodes can be increased by using a technique called _________
a) Prefix compression
b) Postfix compression
c) Prefix expansion
d) Postfix expansion
The fanout of nodes can be increased by using a technique called prefix compression. In this, we do not store the entire value of the search key at the node. We only store the prefix of the search key.
8. Insertion of a large number of entries at a time into an index is referred to as _______ of the index.
a) Bulk loading
b) Mass insertion
c) Quick insertion
d) Quick loading
Insertion of a large number of entries at a time into an index is referred to as bulk loading of the index. This reduces the time complexity as multiple entries are loaded at the same time.
9. ___________ are the indices that store the values of some attributes along with the pointers to the record.
a) Binary indices
b) Covering indices
c) Key indices
d) Static indices
Covering indices are the indices that store the values of some attributes along with the pointers to the record. Storing extra attribute values is useful as they allow us to Answer queries without actually looking up the records.
1. 2-3 tree is a specific form of _________
a) B – tree
b) B+ – tree
c) AVL tree
The 2-3 trees is a balanced trees. It is a specific form of the B – tree. It is B – a tree of order 3, where every node can have two child subtrees and one key or 3 child subtrees and two keys.
2. AVL trees provide the better insertion of the 2-3 trees.
Insertion in AVL tree and 2-3 tree requires searching for a proper position for insertion and transformations for balancing the tree. In both, the tree searching takes O(log n) time, but rebalancing in the AVL tree takes O(log n), while the 2-3 tree takes O(1). So, 2-3 tree provides better insertions.
3. Which of the following is false about the B-tree?
a) 2-3 tree requires less storage than the BST
b) lookup in 2-3 tree is more efficient than in BST
c) 2-3 tree is shallower than BST
d) 2-3 tree is a balanced tree
Search is more efficient in the 2-3 tree than in BST. 2-3 tree is a balanced tree and performs efficient insertion and deletion and it is shallower than BST. But, 2-3 tree requires more storage than the BST.
4. The height of 2-3 tree with n elements is ______
a) between (n/2) and (n/3)
c) between (n) and log2(n + 1)
d) between log3(n + 1) and log2(n + 1)
The number of elements in a 2-3 tree with height h is between 2h – 1 and 3h – 1. Therefore, the 2-3 tree with n elements will have the height between log3(n + 1) and log2(n + 1).
5. Which of the following the BST is isometric with the 2-3 tree?
a) Splay tree
b) AA tree
d) Red – Black tree
AA tree is isometric of the 2-3 trees. In an AA tree, we store each node at a level, which is the height of the corresponding 2-3 tree node. So, we can convert a 2-3 tree to an AA tree.
6. Which of the following data structure can provide efficient searching of the elements?
a) unordered lists
b) binary search tree
d) 2-3 tree
The average case time for lookup in a binary search tree, treap and 2-3 tree is O(log n) and in unordered lists, it is O(n). But in the worst case, only the 2-3 trees perform lookup efficiently as it takes O(log n), while others take O(n).
7. LLRB maintains 1-1 correspondence with 2–3 trees.
A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree. It is a variant of the red-black tree and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement.
LLRB maintains 1-1 correspondence with 2–3 trees.
8. Which of the following is not true about the 2-3 tree?
a) all leaves are at the same level
b) it is perfectly balanced
c) postorder traversal yields elements in sorted order
d) it is B-tree of order 3
In a 2-3 tree, leaves are at the same level. And 2-3 trees are perfectly balanced as every path from the root node to the null link is of equal length. In 2-3 tree in-order traversal yields elements in sorted order.