Description
Q1.Given the following B-Tree with degree of 2.The next key to be inserted is 245. How many nodes are going to be split? Type in the numeric value.Q2.Given the following Red-Black TreeLet’s say we delete the node with key 34 (using the successor rule). Which case(s) are going to be applied?Group of answer choicesCase 1Case 2Case 3Case 4None of the CasesQ3.Given the following Red Black TreeLet’s say we want to delete the node 34 and the predecessor rule is applied. Will the red black tree need to be rebalanced?Group of answer choicesYesNoQ4.Given the following skip list.Let’s assume we are about to add a few new values to the skip list. The values we will add will be in the order of 101, 52, 88, 210, 305, 137, and 65. A 2 sided fair coin is used to determine the highest level a key will be inserted in the associated express lists. Heads means yes and tails means no. Assume the coin we flipped gives us the sequence of results (H is heads and T is tails): HTHTHHHHTTHHHHHTHTTHSelect the following option from each drop down menu if a new level will be generated from the key inserted. In other words, will a brand new express list such as �5 and others be generated?Note: You will need to use the resulting skip list for each key after each insertion in order to determine the appropriate answer for each part.Key 101 [ Select ] [“Yes”, “No”] Key 52 [ Select ] [“Yes”, “No”] Key 88 [ Select ] [“Yes”, “No”] Key 210 [ Select ] [“Yes”, “No”] Key 305 [ Select ] [“Yes”, “No”] Key 137 [ Select ] [“Yes”, “No”] Key 65 [ Select ] [“Yes”, “No”] Q5.Given the following treap that stores a character type value as data and uses an integer type to represent the priority.Let’s say we want to perform the delete operation on the node with data key ‘M’. How many total rotations will occur until the node is successfully removed from the treap? Type in the numerical answer below. Q6.This question comes from your lab session on the Disjoint Set Data Structure.Given the following Disjoint Set Data Structure:How many nodes are going to point to the representative in the structure if path compression is applied when searching for element G? Q7.Consider the following Treap (that is utilizing the max-heap property). The top numerical value represents the key/value and the bottom numerical value represents the priority.Let’s say the next key/value to be inserted is 10 and the random method assigns the value 81 as the priority, how many rotations will the Treap perform until heap property is satisfied. Select the correct answer choice below.Group of answer choices0123456None of these choicesQ8.Consider the following Treap (that is utilizing the max-heap property). The top numerical value represents the key/value and the bottom numerical value represents the priority.Let’s say the key/value to be removed is 11, how many rotations will the Treap perform until the value is successfully removed. Select the correct answer choice below.Group of answer choices0123456None of these choices Q9.Consider the following Red-Black Tree.Let’s say we would like to insert the value 264 into the Red-Black Tree. Based on the cases learned in class, how many times will each case be applied? Use the following drop down menus to select the correct number. Note, if the case never gets applied, then you can just select 0.Case 1: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 2: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 3: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Q10.Consider the following Red-Black Tree.Let’s say we would like to insert the value 160 into the Red-Black Tree. Based on the cases learned in class, how many times will each case be applied? Use the following drop down menus to select the correct number. Note, if the case never gets applied, then you can just select 0.Case 1: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 2: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 3: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Q11.Consider the following Red-Black Tree.Let’s say we would like to remove the value 426 from the Red-Black Tree (using the successor rule). Based on the cases learned in class, how many times will each case be applied? Use the following drop down menus to select the correct number. Note, if the case never gets applied, then you can just select 0.Case 1: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 2: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 3: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 4: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Q12.Consider the following Red-Black Tree.Let’s say we would like to remove the value 242 from the Red-Black Tree (using the successor rule). Based on the cases learned in class, how many times will each case be applied? Use the following drop down menus to select the correct number. Note, if the case never gets applied, then you can just select 0.Case 1: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 2: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 3: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”] Case 4: [ Select ] [“0”, “1”, “2”, “3”, “4”, “5”]
