# Quiz 17: Tree Structures

Computing

Q 1Q 1

Consider the following tree diagram: Which of the following nodes are siblings?
A) D and U
B) H and M
C) D and B
D) L and T

Free

Multiple Choice

C

Q 2Q 2

Consider the following tree diagram: Which of the following nodes are child nodes?
A) C
B) C and X
C) P and X
D) C and P

Free

Multiple Choice

C

Q 3Q 3

Consider the following tree diagram: Which of the following nodes are leaf nodes?
A) C
B) B
C) H
D) B and H

Free

Multiple Choice

B

Q 4Q 4

Consider the following tree diagram: Which of the following nodes are root nodes?
A) C
B) R
C) P
D) R and P

Free

Multiple Choice

Q 5Q 5

Consider the following tree diagram: Which of the following nodes are parent nodes?
A) C
B) C and R
C) R and D
D) C, R, and D

Free

Multiple Choice

Q 6Q 6

Consider the following tree diagram: Which of the following nodes are child nodes?
A) C
B) C and R
C) R and D
D) C, R, and D

Free

Multiple Choice

Q 7Q 7

Consider the following tree diagram: Which of the following nodes are leaf nodes?
A) H
B) N
C) H and P
D) H, N, and P

Free

Multiple Choice

Q 8Q 8

Consider the following tree diagram: Which of the following nodes are interior nodes?
A) C
B) N
C) C and P
D) C, N, and P

Free

Multiple Choice

Q 9Q 9

Consider the following tree diagram: Which of the following statements is NOT correct?
A) N is a descendant of R
B) N is a descendant of C
C) L is a descendant of C
D) H is a descendant of M

Free

Multiple Choice

Q 10Q 10

Consider the following tree diagram: Which of the following statements is NOT correct?
A) R is an ancestor of N
B) C is an ancestor of N
C) D is an ancestor of P
D) H is an ancestor of M

Free

Multiple Choice

Q 11Q 11

Consider the following tree diagram: Which of the following statements is NOT correct?
A) Nodes D and K form a subtree
B) Nodes H, M, and X form a subtree
C) Nodes R and N form a subtree
D) Nodes L and T form a subtree

Free

Multiple Choice

Free

Multiple Choice

Free

Multiple Choice

Q 14Q 14

As implemented in the textbook, a tree class contains which of the following?
I Node class
II Root node
III List of child nodes
A) I
B) I and II
C) II and III
D) I and III

Free

Multiple Choice

Free

Multiple Choice

Q 16Q 16

Consider the following tree diagram: What is the height of the subtree with root R?
A) 2
B) 3
C) 4
D) 6

Free

Multiple Choice

Q 17Q 17

Consider the following tree diagram: What is the size of the subtree with root R?
A) 2
B) 3
C) 4
D) 6

Free

Multiple Choice

Q 18Q 18

Consider the following tree diagram: What is the height of the subtree with root P?
A) 3
B) 4
C) 5
D) 6

Free

Multiple Choice

Q 19Q 19

Consider the following tree diagram: What is the size of the subtree with root P?
A) 3
B) 4
C) 5
D) 6

Free

Multiple Choice

Q 20Q 20

Given the Node class discussed in section 17.1 (partially shown below), select an expression to complete the isLeaf method, which is designed to return true if the node is a leaf, false otherwise. class Node
{
Public Object data;
Public List children;
) . .
Public boolean isLeaf()
{
Return _______________;
}
}
A) data == null
B) children.get(0) == null
C) children.size() == 0
D) root == null

Free

Multiple Choice

Q 21Q 21

Given the Node class discussed in section 17.1 (partially shown below), select a statement to complete the recursive method descendants, which is designed to return the number of descendants of a node. class Node
{
Public Object data;
Public List children;
) . .
Public int descendants()
{
Int num = 0;
For (Node child : children)
{
_____________________________
}
Return num;
}
}
A) num = child.descendants();
B) num = num + child.descendants();
C) num = num + child.children.size();
D) num = num + child.descendants() + 1;

Free

Multiple Choice

Q 22Q 22

The height of a tree can be obtained by recursively computing the heights of its subtrees, while keeping track of the height of the deepest subtree. Given the Node class discussed in section 17.1 (partially shown below), select an expression to complete the recursive method height, which is designed to return the height of the tree rooted at a node. class Node
{
Public Object data;
Public List children;
) . .
Public int height()
{
Int maxChildHeight = 0;
For (Node child : children)
{
Int childHeight = child.height();
If (childHeight > maxChildHeight)
MaxChildHeight = childHeight;
}
Return _________________;
}
}
A) maxChildHeight
B) maxChildHeight + 1
C) maxChildHeight + 2
D) maxChildHeight + height()

Free

Multiple Choice

Q 23Q 23

Given the BinaryTree class discussed in section 17.2 (partially shown below), select an expression to complete the static recursive helper method rightMostValue, which is designed to return the data value in the rightmost node of the tree rooted at node n. public class BinaryTree
{
Private Node root;
Public BinaryTree()
{
Root = null;
}
Public BinaryTree(Object rootData, BinaryTree left, BinaryTree right)
{
Root = new Node();
Root.data = rootData;
Root.left = left.root;
Root.right = right.root;
}
Class Node
{
Public Object data;
Public Node left;
Public Node right;
}
Public Object rightMostValue()
{
If (root == null)
{
Return null;
}
Else
{
Return rightMostValue(root);
}
}
Public static Object rightMostValue(Node n)
{
If (n.right == null)
{
Return n.data;
}
Else
{
Return ______________________;
}
}
}
A) rightMostValue(n.right)
B) rightMostValue(n.left)
C) rightMostValue(n)
D) rightMostValue(root.right)

Free

Multiple Choice

Q 24Q 24

Given the BinaryTree class discussed in section 17.2 (partially shown below), select an expression to complete the static recursive helper method countLeaves, which returns the number of leaf nodes in the binary tree rooted at node n. public class BinaryTree
{
Private Node root;
Public BinaryTree()
{
Root = null;
}
Public BinaryTree(Object rootData, BinaryTree left, BinaryTree right)
{
Root = new Node();
Root.data = rootData;
Root.left = left.root;
Root.right = right.root;
}
Class Node
{
Public Object data;
Public Node left;
Public Node right;
}
Public int countLeaves()
{
Return countLeaves(root);
}
Public static int countLeaves (Node n)
{
If (n == null)
{
Return 0;
}
Else if (_____________________)
{
Return 1;
}
Else
{
Return countLeaves(n.left) + countLeaves(n.right);
}
}
}
A) n.left == null
B) n.right == null
C) n.left == null && n.right == null
D) n.left == null || n.right == null

Free

Multiple Choice

Q 25Q 25

Which of the following statements about binary trees is correct?
A) Each node in a binary tree has at least two child nodes.
B) Each node in a binary tree has at most two child nodes.
C) The number of child nodes for each node in a binary tree is any power of two.
D) If divided down the middle from top to bottom, a binary tree must be symmetrical.

Free

Multiple Choice

Q 26Q 26

Consider the following tree diagrams: Which of the above are binary trees?
A) I
B) II
C) I and II
D) Neither I nor II

Free

Multiple Choice

Q 27Q 27

Consider the following tree diagram: Which arithmetic expression is represented by this tree?
A) 2 3 + 5 + 4 6 - 1
B) 2 3 + 5 + 4 - 6 - 1
C) 2 (3 + 5 + 4) (6 - 1)
D) [(2 3) + 5 + 4] (6 - 1)

Free

Multiple Choice

Q 28Q 28

Consider the following tree diagram: Which arithmetic expression is represented by this tree?
A) (2 + 3) + (5 4) 6 (- 1)
B) 2 + 3 + 5 4 - 6 - 1
C) (2 + 3) (5 4) (6 - 1)
D) [(2 + 3) + (5 4)] (6 - 1)

Free

Multiple Choice

Q 29Q 29

Consider the following tree diagrams: Which tree represents the arithmetic expression 2 5 + 4?
A) I
B) II
C) Both I and II
D) Neither I nor II

Free

Multiple Choice

Q 30Q 30

Consider the following tree diagrams: Which tree represents the arithmetic expression 2 + 5 4?
A) I
B) II
C) Both I and II
D) Neither I nor II

Free

Multiple Choice

Q 31Q 31

Consider the following tree diagrams: Which tree represents the arithmetic expression (2 + 5) 4?
A) I
B) II
C) Both I and II
D) Neither I nor II

Free

Multiple Choice

Q 32Q 32

You are using a tree to show the evaluation order of arithmetic expressions. Which of the following statements is NOT correct?
A) Leaves contain numbers.
B) Interior nodes contain numbers.
C) The root contains an operator.
D) Every level of the tree must contain an operator.

Free

Multiple Choice

Q 33Q 33

Consider the following Huffman encoding tree: The letter H will be encoded as ____.
A) 000
B) 011
C) 001
D) 010

Free

Multiple Choice

Q 34Q 34

Consider the following Huffman encoding tree: The letter K will be encoded as ____.
A) 10
B) 010
C) 001
D) 100

Free

Multiple Choice

Q 35Q 35

Consider a balanced binary tree with 520 nodes. The average length of all paths from the root to the leaves is approximately ____.
A) 9
B) 10
C) 12
D) 13

Free

Multiple Choice

Free

Multiple Choice

Q 37Q 37

A binary tree of height h can have up to ____ nodes.
A) 2h - 1
B) 2h + 1
C) 2

^{h}- 1 D) 2^{h}+ 1Free

Multiple Choice

Q 38Q 38

The height h of a completely filled binary tree with n nodes is ____.
A) h = log2(n) - 1
B) h = log2(n) + 1
C) h = log2(n - 1)
D) h = log2(n + 1)

Free

Multiple Choice

Free

Multiple Choice

Free

Multiple Choice

Q 41Q 41

Consider the following tree diagrams: Which of these trees is considered to be balanced?
A) I
B) I and II
C) II and III
D) I and III

Free

Multiple Choice

Q 42Q 42

Consider the following tree diagrams: Which of these trees is considered to be unbalanced?
A) I
B) II
C) III
D) II and III

Free

Multiple Choice

Q 43Q 43

If the child references of a binary tree node are both null, the node is ____.
A) a root node
B) a leaf node
C) a parent node
D) an interior node

Free

Multiple Choice

Q 44Q 44

If both of the child references of a binary tree node are non-null, it follows that the node must be ____.
A) a root node
B) a leaf node
C) a child node
D) an interior node

Free

Multiple Choice

Q 45Q 45

In a binary search tree, where the root node data value = 45, what do we know about the data values of all the descendants in the left subtree of the root?
A) the root's left child value < 45, but the right child of the root's left child value is > 45
B) some values will be < 45, but there may be a few values > 45
C) approximately half the values are < 45, the other half are > 45
D) all will be < 45

Free

Multiple Choice

Q 46Q 46

In a binary search tree, where the root node data value = 45, what do we know about the values of all the descendants in the right subtree of the root?
A) the root's right child value > 45, but the left child of the root's right child key is < 45
B) some values will be > 45, but there may be a few values < 45
C) approximately half the values are < 45, the other half are > 45
D) all will be > 45

Free

Multiple Choice

Q 47Q 47

A binary search tree is made up of a collection of nodes organized with smaller data values on the left and greater values on the right, relative to any node. Which of the following Node references must be instance variables of any implementation of a BinarySearchTree class?
I root
II left
III right
A) I
B) II and III
C) I and II
D) I, II and III

Free

Multiple Choice

Q 48Q 48

A binary search tree is made up of a collection of nodes organized with smaller data values on the left and greater values on the right relative to any node. Which of the following Node references must be instance variables of any implementation of a Node class?
I root
II left
III right
A) I
B) II and III
C) I and II
D) I, II and III

Free

Multiple Choice

Q 49Q 49

The nodes in our binary search tree implement the Comparable interface. Which tree operations benefit from this design decision?
I add
II search
III delete
A) I
B) II
C) I and III
D) I, II and III

Free

Multiple Choice

Q 50Q 50

Consider the following tree diagrams: Which are binary search trees?
A) I
B) II
C) I and II
D) Neither I nor II

Free

Multiple Choice

Q 51Q 51

Consider the following tree diagrams: Which of the above are binary search trees?
A) I
B) II
C) I and II
D) Neither I nor II

Free

Multiple Choice

Q 52Q 52

Consider the following binary search tree diagram: Which nodes will be visited in order to insert the letter B into this tree?
A) H
B) H and D
C) H, D, and F
D) H, D, and A

Free

Multiple Choice

Q 53Q 53

Consider the following binary search tree diagram: Which nodes will be visited in order to insert the letter E into this tree?
A) H
B) H and D
C) H, D, and F
D) H, D, and A

Free

Multiple Choice

Q 54Q 54

Consider the following binary search tree diagram: Which of the following trees represents the correct result after inserting element B?
A) I
B) II
C) III
D) IV

Free

Multiple Choice

Q 55Q 55

Consider the following binary search tree diagram: Which of the following trees represents the correct result after inserting element T?
A) I
B) II
C) III
D) IV

Free

Multiple Choice

Q 56Q 56

What does the left node reference of a newly inserted binary search tree node get set to?
A) depends where the node is inserted
B) it gets set to the left child of the new node, if one exists
C) always null
D) it gets set to the left child of the root, if it exists

Free

Multiple Choice

Q 57Q 57

Which of the following may occur as a result of an add operation, on a non-empty binary search tree?
I a new root is created
II the new node becomes the left child of the root
III the new node has a right child upon insertion
A) I
B) II
C) III
D) II and III

Free

Multiple Choice

Q 58Q 58

Which of the following sequences of insertions will result in a balanced tree?
I 12 , 7, 25, 6, 9, 13, 44
II 12 , 7, 25, 44, 13, 6, 9
III 12, 25, 44, 13, 6, 9, 7
A) I
B) II
C) I and II
D) I and III

Free

Multiple Choice

Q 59Q 59

Consider the following binary search tree diagram: If node J is to be removed, which node should be copied into its location?
A) M
B) L
C) X
D) N

Free

Multiple Choice

Q 60Q 60

Consider the following binary search tree diagram: If node M is to be removed, which action should be taken?
A) Replace M with the smallest value in its left subtree.
B) Replace M with the smallest value in its right subtree.
C) Replace M with the largest value in its left subtree.
D) Replace M with the largest value in its right subtree.

Free

Multiple Choice

Q 61Q 61

Consider the following binary search tree diagram: If node F is to be removed, which action should be taken? Use the technique presented in the textbook.
A) Move C into the right subtree of D.
B) Move C into the left subtree of A.
C) Replace F with D's value and replace D with C's value.
D) Modify D to have a null right reference.

Free

Multiple Choice

Q 62Q 62

Consider the following binary search tree diagram: If node Y is to be removed, which action should be taken? Use the technique presented in the textbook.
A) Modify the V's left reference to point to X.
B) Modify the V's right reference to point to X.
C) Swap the values in V and X, and modify X's right reference to point to V.
D) Modify V to have a null right pointer.

Free

Multiple Choice

Q 63Q 63

Consider the following binary search tree diagram: If node D is to be removed, which action should be taken? Use the technique presented in the textbook.
A) Modify K to point to A as its left child, and modify A to point to F as its right child.
B) Modify K to make its left child null.
C) Swap the values in C and D so that C has A as its left child, then remove the new D node.
D) Modify K to point to F as its left child and modify F to point to A as its left child.

Free

Multiple Choice

Q 64Q 64

Which of the following statements about a binary search tree is correct?
A) Adding elements that are already sorted will result in a balanced binary search tree.
B) Nodes must be moved when a node is removed from the middle of a subtree.
C) The speed of inserting or removing a node is dependent on the shape of the tree.
D) The speed of inserting or removing a node is dependent on the number of subtrees.

Free

Multiple Choice

Q 65Q 65

Locating an element in a balanced binary search tree takes ____ time.
A) O(n)
B) O(log(n))
C) O(1)
D) O(n

^{2})Free

Multiple Choice

Q 66Q 66

Adding an element to a balanced binary search tree takes ____ time.
A) O(n)
B) O(log (n))
C) O(1)
D) O(n

^{2})Free

Multiple Choice

Q 67Q 67

Removing an element from a balanced binary search tree takes ____ time.
A) O(n)
B) O(log (n))
C) O(1)
D) O(n

^{2})Free

Multiple Choice

Q 68Q 68

Locating an element in an unbalanced binary search tree takes ____ time.
A) O(n)
B) O(log (n))
C) O(1)
D) O(n

^{2})Free

Multiple Choice

Q 69Q 69

Adding an element to an unbalanced binary search tree takes ____ time.
A) O(n)
B) O(log (n))
C) O(1)
D) O(n

^{2})Free

Multiple Choice

Q 70Q 70

Removing an element from an unbalanced binary search tree takes ____ time.
A) O(n)
B) O(log (n))
C) O(1)
D) O(n

^{2})Free

Multiple Choice

Q 71Q 71

Given the BinarySearchTree class discussed in section 17.3, select a statement to complete the following code segment, so that the resulting binary search tree has a height of 4. BinarySearchTree t = new BinarySearchTree();
T)add("a");
T)add("day");
T)add("in");
__________________
T)add("life");
A) t.add("my");
B) t.add("his");
C) t.add("the");
D) t.add("your");

Free

Multiple Choice

Q 72Q 72

Given the BinarySearchTree and Node classes discussed in section 17.3 (partially shown below), select an expression to complete the recursive method smallest in the Node class. The method returns the smallest data value in the binary search tree rooted at a node. public class BinarySearchTree
{
Private Node root;
Public BinarySearchTree() {...}
Public void add(Comparable obj) {...}
Public Comparable smallest()
{
If (root == null)
Throw new NoSuchElementException();
Else
Return root.smallest();
}
Class Node
{
Public Comparable data;
Public Node left;
Public Node right;
Public Comparable smallest()
{
If (left == null)
Return data;
Else
Return _______________;
}
}
}
A) left.smallest()
B) right.smallest()
C) data.smallest()
D) Math.min(left.smallest(), right.smallest())

Free

Multiple Choice

Q 73Q 73

Given the BinarySearchTree class discussed in section 17.3 (partially shown below), select a sequence of statements to complete the recursive postorder method. The method performs a postorder traversal of the binary search tree rooted at node n. public class BinarySearchTree
{
Private Node root;
Public BinarySearchTree() {...}
Public void postorderTraversal()
{
Postorder(root);
}
Private static void postorder(Node n)
{
If (n != null)
{
____________________
____________________
____________________
}
}
) . .
}
A) postorder(n.right);
Postorder(n.left);
System.out.print(n.data + " ");
B) postorder(n.left);
Postorder(n.right);
System.out.print(n.data + " ");
C) postorder(n.left);
System.out.print(n.data + " ");
Postorder(n.right);
D) postorder(n.right);
System.out.print(n.data + " ");
Postorder(n.left);

Free

Multiple Choice

Q 74Q 74

Given the Visitor interface discussed in section 17.4 (shown below), select a statement to complete the class CodeFinder. The class is to be used when traversing a binary tree while displaying every data value that contains the code "007". public interface Visitor
{
Void visit(Object data);
}
Class CodeFinder implements Visitor
{
Public void visit(Object data)
{
If (______________________________)
{
System.out.println(data);
}
}
}
A) data.toString().indexOf("007") >= 0
B) data.toString().indexOf("007") > 0
C) data.equals("007")
D) data.toString().contains("007")

Free

Multiple Choice

Q 75Q 75

You wish to traverse a binary search tree in sorted order using inorder traversal. Arrange the following actions in the correct order to accomplish this.
I Print the right subtree recursively
II Print the root
III Print the left subtree recursively
A) I, II, III
B) III, II, I
C) II, III, I
D) III, I, II

Free

Multiple Choice

Q 76Q 76

You wish to traverse a binary search tree in sorted order. Which of the following schemes will accomplish this?
I inorder traversal
II preorder traversal
III postorder traversal
A) I
B) II
C) III
D) II and III

Free

Multiple Choice

Q 77Q 77

Which of the following statements about the three tree traversal schemes studied is correct?
A) Inorder traversal is used for evaluating arithmetic expression trees on a stack-based calculator.
B) Postorder traversal is used for copying file directories.
C) Inorder traversal is used for copying file directories.
D) Postorder traversal is used for removing file directories by removing subdirectories first.

Free

Multiple Choice

Q 78Q 78

Which of the following statements about the three tree traversal schemes studied, is correct?
A) Preorder traversal is used for evaluating arithmetic expression trees on a stack-based calculator.
B) Postorder traversal is used for evaluating arithmetic expression trees on a stack-based calculator.
C) Postorder traversal is used for copying file directories.
D) Preorder traversal is used for removing file directories by removing subdirectories first.

Free

Multiple Choice

Q 79Q 79

You wish to traverse a binary search tree in sorted order using preorder traversal. Arrange the following actions in the correct order to accomplish this.
I Print the right subtree recursively
II Print the root
III Print the left subtree recursively
A) I, II, III
B) III, II, I
C) II, III, I
D) III, I, II

Free

Multiple Choice

Q 80Q 80

You wish to traverse a binary search tree using postorder traversal. Arrange the following actions in the correct order to accomplish this.
I Print the right subtree recursively
II Print the root
III Print the left subtree recursively
A) I, II, III
B) III, II, I
C) II, III, I
D) III, I, II

Free

Multiple Choice

Q 81Q 81

Consider the following binary search tree: Which of the following sequences correctly represents preorder traversal of this tree?
A) J, E, M, A, G, P, C, H, N
B) A, C, H, G, E, N, P, M, J
C) J, E, A, G, C, H, M, P, N
D) A, C, E, G, H, J, M, N, P

Free

Multiple Choice

Q 82Q 82

Consider the following binary search tree: Which of the following sequences correctly represents postorder traversal of this tree?
A) J, E, M, A, G, P, C, H, N
B) A, C, H, G, E, N, P, M, J
C) J, E, A, G, C, H, M, P, N
D) A, C, E, G, H, J, M, N, P

Free

Multiple Choice

Q 83Q 83

Consider the following binary search tree: Which of the following sequences correctly represents breadth-first traversal of this tree?
A) J, E, M, A, G, P, C, H, N
B) A, C, H, G, E, N, P, M, J
C) J, E, A, G, C, H, M, P, N
D) A, C, E, G, H, J, M, N, P

Free

Multiple Choice

Q 84Q 84

What are the differences between preorder, postorder, and inorder traversals?
A) The order in which we visit the left and right subtrees
B) Preorder only visits the left subtree
C) Postorder only visits the right subtree
D) The order of the root visit

Free

Multiple Choice

Q 85Q 85

If the postorder traversal visits the nodes of a binary tree storing character values in the order of U, G, T, R, A, I, what is the value of the root of the tree?
A) I
B) U
C) T
D) cannot be determined

Free

Multiple Choice

Q 86Q 86

If the postorder traversal visits the nodes of a binary tree storing character values in the order of U, G, T, R, A, I, what is the visit order for an inorder traversal of the same binary tree?
A) I, G, U, A, T, R
B) R, G, U, I, T, A
C) G, U, I, T, A, R
D) cannot be determined

Free

Multiple Choice

Q 87Q 87

If the postorder traversal of an expression tree is 8, 2, +, 5, /, what is the numeric result of that Reverse Polish Notation expression?
A) 15
B) 8
C) 7
D) 2

Free

Multiple Choice

Q 88Q 88

If the postorder traversal of an expression tree is 8, 2, +, 5, /, what is the preorder traversal?
A) +, /, 8, 2, 5
B) /, +, 8, 2, 5
C) 8, +, 2, /, 5
D) /, +, 2, 8, 5

Free

Multiple Choice

Q 89Q 89

If the postorder traversal of an expression tree is, 8, 2, +, 5, /, what is the result of an inorder traversal?
A) +, /, 8, 2, 5
B) /, +, 8, 2, 5
C) 8, +, 2, /, 5
D) /, +, 2, 8, 5

Free

Multiple Choice

Q 90Q 90

Insert the missing code in the following code fragment. This fragment is intended to create an iterator to be used to process elements of a tree. TreeSet aTree = . . .
String first = iter.next();
String second = iter.next();
A) Iterator iter = aTree.iterator();
B) Iterator iter = aTree.iterator();
C) Iterator iter = String.iterator();
D) Iterator iter = aTree.iterator();

Free

Multiple Choice

Q 91Q 91

Which of the following is NOT a property of a red-black tree?
A) All nodes must be red or black.
B) All child nodes of a red node must be black.
C) The root is black.
D) All paths from root to null have the name number of nodes.

Free

Multiple Choice

Q 92Q 92

Which of the following statements about inserting a node into a red-black tree is correct?
A) If it is the first node, it must be red.
B) Color the new node black.
C) If the parent of the new node is red, no other actions are required.
D) If a double-red situation results, you must correct this.

Free

Multiple Choice

Q 93Q 93

Which of the following statements about inserting a node into a red-black tree is NOT correct?
A) If it is the first node, it must be black.
B) Color the new node red.
C) If the parent of the new node is red, no other actions are required.
D) A double-red result can occur in a left subtree or a right subtree.

Free

Multiple Choice

Q 94Q 94

What is the efficiency of locating an element in a red-black tree?
A) O(n)
B) O(log (n))
C) O(1)
D) O(n

^{2})Free

Multiple Choice

Q 95Q 95

What is the efficiency of adding an element to a red-black tree?
A) O(n)
B) O(log (n))
C) O(1)
D) O(n

^{2})Free

Multiple Choice

Q 96Q 96

What is the efficiency of removing an element from a red-black tree?
A) O(1)
B) O(n)
C) O(n

^{2}) D) O(log (n))Free

Multiple Choice

Q 97Q 97

Which of the following statements about a heap is NOT correct?
A) A heap is a form of binary tree.
B) The shape of a heap is very regular.
C) A heap is always completely filled at all levels.
D) In a heap, both the right and left subtrees of any node store elements that are at least as large as the node value.

Free

Multiple Choice

Q 98Q 98

A min-heap is a binary tree structure in which missing nodes may only occur where?
A) bottom level, left side
B) bottom level, right side
C) anywhere in the bottom two levels
D) left child of the root

Free

Multiple Choice

Q 99Q 99

If a min-heap has 15 nodes, what is known for certain?
I every level of the tree is fully occupied
II at least one level is missing a node
III the root contains the smallest element
A) I
B) II
C) I and III
D) II and III

Free

Multiple Choice

Q 100Q 100

If a min-heap has 14 nodes, what is known for certain when we add a new node?
I every level of the tree will be fully occupied
II the tree does not grow a new level
III the root contains the smallest element
A) I
B) I and II
C) I and III
D) I, II and III

Free

Multiple Choice

Q 101Q 101

If a min-heap has 1024 nodes, what is its height?
A) 10
B) 11
C) 12
D) impossible to determine

Free

Multiple Choice

Q 102Q 102

When we map a min-heap with n elements to an array with n + 1 elements, we ignore array element 0, and place the root value at which array index?
A) 1
B) 2
C) n
D) n+1

Free

Multiple Choice

Q 103Q 103

When we map a min-heap with n elements to an array with n + 1 elements, the right child of the root is stored at which array index?
A) 1
B) 2
C) 3
D) 4

Free

Multiple Choice

Q 104Q 104

What is the complexity of adding an element to a heap?
A) O(1)
B) O(log (n))
C) O(n log (n))
D) O(n

^{2})Free

Multiple Choice

Q 105Q 105

What is the complexity of removing an element from a heap?
A) O(1)
B) O(log (n))
C) O(n log (n))
D) O(n

^{2})Free

Multiple Choice

Q 106Q 106

If we have a heap with n elements, and we add another n elements to it, what is the maximum increase of height associated with the binary tree representation of the heap?
A) 1
B) 2
C) n-1
D) n

Free

Multiple Choice

Q 107Q 107

Given the MinHeap class discussed in section 17.6, select the statement(s) needed to complete the following method, which displays the n smallest values in the parameter array. public static void nSmallestValues(Comparable[] array, int n)
{
MinHeap h = new MinHeap();
For(Comparable value : array)
{
H)add(value);
}
System.out.print(n + " smallest value(s): ");
For(int i = 0; i < n; ++i)
{
___________________________
}
}
A) System.out.println(h.remove());
B) System.out.println(h.peek());
C) System.out.println(array[i]);
D) System.out.println(h.elements.get(i));

Free

Multiple Choice

Q 108Q 108

What is the efficiency of the heapsort algorithm?
A) O(1)
B) O(log (n))
C) O(n log (n))
D) O(n

^{2})Free

Multiple Choice

Q 109Q 109

How many times during the heapsort algorithm does the fixHeap method need to be called for a max-heap with n elements?
a) log(n)
b) n-1
c) n
d) n+1

Free

Essay

Q 110Q 110

Which action(s) will invalidate a min-heap so that, it may no longer have the properties of a min-heap?
I change the value of the root node
II remove the lowest level, right-most node
III remove the lowest level, left-most node
A) III
B) I and II
C) II and III
D) I and III

Free

Multiple Choice