URGENT:

Question 1 (2 points)

Consider the 2-3 tree whose level order traversal is 60 28-47 82 23 41 59 65-66 95. What is the level order traversal of the 2-3 tree that results after inserting the following sequence of 3 keys? 31 62 39 (The notation X-Y specifies a 3-node containing the two keys X and Y.)

Question 1 options:

	60 28-41 65-82 23 31-39 47-59 62 66 95
	60 31-47 65-82 23-28 39-41 59 62 66 95
	39-60 28 47 66 23 31 41 59 62-65 82-95
	39-60 28 47 65-82 23 31 41 59 62 66 95

Question 2 (1 point)

In a balanced 2-3 tree, it is possible for a node to have exactly one child.

Question 2 options:

	True
	False

Question 3 (1 point)

When inserting into a 2-3 tree, the height of the tree increases by splitting the root node.

Question 3 options:

	True
	False

Question 4 (1 point)

There may be multiple left-leaning red-black BSTs that correspond to a single 2-3 tree.

Question 4 options:

	True
	False

Question 5 (1 point)

In a red-black BST, the nodes joined by red links correspond to 3-nodes in a 2-3 tree.

Question 5 options:

	True
	False

Question 6 (1 point)

When inserting into a red-black tree, at most one rotation is required.

Question 6 options:

	True
	False

Question 7 (2 points)

Consider the left-leaning red-black BST whose level-order traversal is:

51 33 85 28 45 57 91 27 31 35 54 69 88

List the keys in the red nodes, in increasing order (smaller keys before larger ones). A node is red if the link to its parent is red.

Question 7 options:

Question 8 (2 points)

Consider the left-leaning red-black BST whose level-order traversal is:

43 28 76 19 35 70 88 68 71 56 ( red links = 70 56 )

What is the level order traversal of the red-black BST that results after inserting the following sequence of keys:

77 21 48

Simply list the 13 keys in level order, without indicating which are red.

Question 8 options:

Question 9 (2 points)

Given a binary search tree whose level order traversal is: 33 32 57 21 37 96 27 49 94 42 74 78, what is the level order traversal of the resulting binary search tree after Hibbard deleting the following 3 keys: 42 21 57 (Note: Hibbard deletion of a node with 2 children replaces that node with its successor from the right hand side!)

Question 9 options:

	a) 33 32 96 27 37 94 49 74 78
	b) 33 32 96 27 37 49 74 78 94
	c) 33 32 74 27 37 96 49 94 78
	d) 33 32 37 27 49 42 96 94 78