Tree Structures Chapter 17 Complete Test Bank - Big Java Early Objects 5e Complete Test Bank by Cay S. Horstmann. DOCX document preview.
Course Title: Big Java, Early Objects
Chapter Number: 17 Tree Structures
Question type: Multiple Choice
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
Title: Which nodes are siblings?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: Which nodes are child nodes?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
3) Consider the following tree diagram:
Which of the following nodes are leaf nodes?
a) C
b) B
c) H
d) B and H
Title: Which nodes are leaf nodes?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
4) Consider the following tree diagram:
Which of the following nodes are root nodes?
a) C
b) R
c) P
d) R and P
Title: Which nodes are root nodes?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: Which nodes are parent nodes?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: Which nodes are child nodes?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: Which nodes are leaf nodes?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: Which nodes are interior nodes?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: Which statement about this tree structure is NOT correct?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: Which statement about this tree structure is NOT correct?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: Which statement about this tree structure is NOT correct?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
12) Consider the following tree diagram:
What is the height of this tree?
a) 3
b) 4
c) 6
d) 7
Title: What is the height of this tree?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
13) Consider the following tree diagram:
What is the height of this tree?
a) 3
b) 4
c) 5
d) 7
Title: What is the height of this tree?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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
Title: A tree class contains which of the following?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
15) Consider the following tree diagram:
What is the size of this tree?
a) 4
b) 5
c) 6
d) 13
Title: What is the size of this tree?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
16) Consider the following tree diagram:
What is the height of the subtree with root R?
a) 2
b) 3
c) 4
d) 6
Title: What is the height of this subtree?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
17) Consider the following tree diagram:
What is the size of the subtree with root R?
a) 2
b) 3
c) 4
d) 6
Title: What is the size of this subtree?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
18) Consider the following tree diagram:
What is the height of the subtree with root P?
a) 3
b) 4
c) 5
d) 6
Title: What is the height of this subtree?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
19) Consider the following tree diagram:
What is the size of the subtree with root P?
a) 3
b) 4
c) 5
d) 6
Title: What is the size of this subtree?
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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<Node> children;
. . .
public boolean isLeaf()
{
return _______________;
}
}
a) data == null
b) children.get(0) == null
c) children.size() == 0
d) root == null
Title: Select statement to complete method to determine if node is a leaf
Difficulty: Easy
Section Reference 1: 17.1 Basic Tree Concepts
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<Node> 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;
Title: Select statement to complete recursive method to compute the number of descendants of a node
Difficulty: Hard
Section Reference 1: 17.1 Basic Tree Concepts
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<Node> 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()
Title: Select expression to complete recursive method to compute the height of a tree rooted at a node
Difficulty: Medium
Section Reference 1: 17.1 Basic Tree Concepts
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)
Title: Select expression to complete recursive helper method to obtain rightmost value
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
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
Title: Select expression to complete recursive helper method to count number of leaf nodes
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
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.
Title: Which statement about binary trees is correct?
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
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
Title: Which of these are binary trees?
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
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)
Title: Which arithmetic expression is represented by this tree?
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
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)
Title: Which arithmetic expression is represented by this tree?
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
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
Title: Which tree represents the arithmetic expression 2 × 5 + 4?
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
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
Title: Which tree represents the arithmetic expression 2 + 5 × 4?
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
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
Title: Which tree represents the arithmetic expression (2 + 5) × 4?
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 7.2.1 Binary Tree Examples
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.
Title: Which statement about arithmetic expression trees is NOT correct?
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
33) Consider the following Huffman encoding tree:
The letter H will be encoded as ____.
a) 000
b) 011
c) 001
d) 010
Title: In this Huffman tree, the letter H will be encoded as ____.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
34) Consider the following Huffman encoding tree:
The letter K will be encoded as ____.
a) 10
b) 010
c) 001
d) 100
Title: In this Huffman tree, the letter H will be encoded as ____.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.1 Binary Tree Examples
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
Title: A binary tree with 520 nodes has a height of approximately ____.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.2 Balanced Trees
36) A binary tree with 260 nodes has a height of approximately ____.
a) 8
b) 10
c) 12
d) 13
Title: A binary tree with 520 nodes has a height of approximately ____.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.2 Balanced Trees
37) A binary tree of height h can have up to ____ nodes.
a) 2h - 1
b) 2h + 1
c) 2h - 1
d) 2h + 1
Title: A binary tree of height h can have up to ____ nodes.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.2 Balanced Trees
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)
Title: The height h of a completely filled binary tree with n nodes is ____.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.2 Balanced Trees
39) A completely filled binary tree with a height of 3 has ____ nodes.
a) 6
b) 7
c) 8
d) 12
Title: A completely filled binary tree with a height of 3 has ____ nodes.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.2 Balanced Trees
40) A completely filled binary tree with a height of 4 has ____ nodes.
a) 8
b) 12
c) 15
d) 16
Title: A completely filled binary tree with a height of 4 has ____ nodes.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.2 Balanced Trees
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
Title: Which of these trees is considered to be balanced?
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.2 Balanced Trees
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
Title: Which of these trees is considered to be balanced?
Difficulty: Easy
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.2 Balanced Trees
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
Title: If the child references of a binary tree node are both null, the node is ____.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.3 A Binary Tree Implementation
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
Title: If children of a binary tree node are non-null, it follows that the node must be ____.
Difficulty: Medium
Section Reference 1: 17.2 Binary Trees
Section Reference 2: 17.2.3 A Binary Tree Implementation
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
Title: In a binary search tree, where the rot node key = 45, what do we know about the values of all the descendants in the left subtree of the root?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.1 The Binary Search Property
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
Title: In a binary search tree, what do we know about all descendents in the right?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.1 The Binary Search Property
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
Title: Which Node references must be instance variables of any BinarySearchTree implementation?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.1 The Binary Search Property
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
Title: Which Node references must be instance variables of any Node implementation?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.1 The Binary Search Property
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
Title: Which tree operations benefit from implementing Comparable?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.1 The Binary Search Property
50) Consider the following tree diagrams:
Which are binary search trees?
a) I
b) II
c) I and II
d) Neither I nor II
Title: Which of these are binary search trees?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.1 The Binary Search Property
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
Title: Which of these are binary search trees?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.1 The Binary Search Property
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
Title: Which nodes will be visited in order to insert a new node into this tree?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.2 Insertion
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
Title: Which nodes will be visited in order to insert a new node into this tree?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.2 Insertion
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
Title: Which tree represents the correct result after inserting element B?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.2 Insertion
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
Title: Which tree represents the correct result after inserting element B?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.2 Insertion
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
Title: What does the left node reference of a newly inserted binary tree node get set to?
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.2 Insertion
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
Title: Which may occur as a result of an add operation, on a non-empty binary search tree?
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.2 Insertion
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
Title: Which sequence(s) of insertions will result in a balanced tree?
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.2 Insertion
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
Title: Which node should replace a removed node in this tree?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.3 Removal
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.
Title: Which action should be taken to remove a node from this binary search tree?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.3 Removal
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.
Title: Which action should be taken to remove a node from this binary search tree?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.3 Removal
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.
Title: Which action should be taken to remove a node from this binary search tree?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.3 Removal
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.
Title: Which action should be taken to remove a node from this binary search tree?
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.3 Removal
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.
Title: Which statement about a binary search tree is correct?
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.4 Efficiency of the Operations
65) Locating an element in a balanced binary search tree takes ____ time.
a) O(n)
b) O(log(n))
c) O(1)
d) O(n2)
Title: Locating an element in a balanced binary search tree takes ____ time.
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.4 Efficiency of the Operations
66) Adding an element to a balanced binary search tree takes ____ time.
a) O(n)
b) O(log (n))
c) O(1)
d) O(n2)
Title: Adding an element to a balanced binary search tree takes ____ time.
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.4 Efficiency of the Operations
67) Removing an element from a balanced binary search tree takes ____ time.
a) O(n)
b) O(log (n))
c) O(1)
d) O(n2)
Title: Removing an element from a balanced binary search tree takes ____ time.
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.4 Efficiency of the Operations
68) Locating an element in an unbalanced binary search tree takes ____ time.
a) O(n)
b) O(log (n))
c) O(1)
d) O(n2)
Title: Locating an element in an unbalanced binary search tree takes ____ time.
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.4 Efficiency of the Operations
69) Adding an element to an unbalanced binary search tree takes ____ time.
a) O(n)
b) O(log (n))
c) O(1)
d) O(n2)
Title: Adding an element to an unbalanced binary search tree takes ____ time.
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.4 Efficiency of the Operations
70) Removing an element from an unbalanced binary search tree takes ____ time.
a) O(n)
b) O(log (n))
c) O(1)
d) O(n2)
Title: Removing an element from an unbalanced binary search tree takes ____ time.
Difficulty: Medium
Section Reference 1: 17.3 Binary Search Trees
Section Reference 2: 17.3.4 Efficiency of the Operations
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");
Title: Select statement to complete code segment to build a binary search tree of height 4
Difficulty: Easy
Section Reference 1: 17.3 Binary Search Trees
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())
Title: Select expression to complete recursive method to find smallest value
Difficulty: Medium
Section Reference 1: 17.3 Basic Search Trees
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);
Title: Select statements to complete postorder traversal method
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
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")
Title: Select expression to complete method used to implement Visitor interface
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
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
Title: Arrange the actions to print a binary search tree in sorted order using inorder traversal.
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.1 Inorder Traversal
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
Title: Which scheme will print a binary search tree in sorted order?
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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.
Title: Which statement about traversal order of a tree is correct?
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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.
Title: Which statement about traversal order of a tree is correct?
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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
Title: Arrange the actions to print a binary search tree using preorder traversal.
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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
Title: Arrange the actions to print a binary search tree using postorder traversal.
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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
Title: Which sequence represents preorder traversal of this tree?
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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
Title: Which sequence represents postorder traversal of this tree?
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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
Title: Which sequence represents breadth-first traversal of this tree?
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.4 Depth-First and Breadth-First Search
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
Title: What are the differences between preorder, postorder, and inorder traversals?
Difficulty: Hard
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.4 Depth-First and Breadth-First Search
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
Title: If the postorder traversal visits the nodes in this order,,what is the root of the tree?
Difficulty: Hard
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.4 Depth-First and Breadth-First Search
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
Title: If postorder of a binary tree is this, what is the inorder traversal of the same tree?
Difficulty: Hard
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.3 The Visitor Pattern
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
Title: If the postorder traversal is 8, 2, +, 5, /, what is the result of that RPN expression?
Difficulty: Medium
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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
Title: If the postorder traversal is 8, 2, +, 5, /, what is the preorder traversal?
Difficulty: Hard
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.2 Preorder and Postorder Traversal
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
Title: If the postorder traversal is 8, 2, +, 5, /, what is inorder traversal?
Difficulty: Hard
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.4 Depth-First and Breadth-First Search
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<String> aTree = . . .
String first = iter.next();
String second = iter.next();
a) Iterator<String> iter = aTree.iterator<String>();
b) Iterator<String> iter = aTree.iterator();
c) Iterator<String> iter = String.iterator();
d) Iterator<TreeSet> iter = aTree.iterator();
Title: Complete the code to create a tree iterator.
Difficulty: Easy
Section Reference 1: 17.4 Tree Traversal
Section Reference 2: 17.4.5 Tree Iterators
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.
Title: Which of these is NOT a property of a red-black tree?
Difficulty: Easy
Section Reference 1: 17.5 Red-Black Trees
Section Reference 2: 17.5.1 Basic Properties of Red-Black Trees
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.
Title: Which statement about inserting a new node into a red-black tree is correct?
Difficulty: Easy
Section Reference 1: 17.5 Red-Black Trees
Section Reference 2: 17.5.2 Insertion
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.
Title: Which statement about inserting a new node into a red-black tree is NOT correct?
Difficulty: Easy
Section Reference 1: 17.5 Red-Black Trees
Section Reference 2: 17.5.2 Insertion
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(n2)
Title: What is the efficiency of locating an element in a red-black tree?
Difficulty: Easy
Section Reference 1: 17.5 Red-Black Trees
Section Reference 2: 17.5.3 Removal
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(n2)
Title: What is the efficiency of adding an element to a red-black tree?
Difficulty: Easy
Section Reference 1: 17.5 Red-Black Trees
Section Reference 2: 17.5.3 Removal
96) What is the efficiency of removing an element from a red-black tree?
a) O(1)
b) O(n)
c) O(n2)
d) O(log (n))
Title: What is the efficiency of removing an element from a red-black tree?
Difficulty: Easy
Section Reference 1: 17.5 Red-Black Trees
Section Reference 2: 17.5.3 Removal
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.
Title: Which of the following statements about a heap is NOT correct?
Difficulty: Easy
Section Reference 1: 17.6 Heaps
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
Title: A min-heap is a binary tree structure in which missing nodes may only occur where?
Difficulty: Easy
Section Reference 1: 17.6 Heaps
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
Title: If a min-heap has 15 nodes, what is known for certain?
Difficulty: Medium
Section Reference 1: 17.6 Heaps
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
Title: If a min-heap has 14 nodes, what is known for certain when we add a new node?
Difficulty: Medium
Section Reference 1: 17.6 Heaps
101) If a min-heap has 1024 nodes, what is its height?
a) 10
b) 11
c) 12
d) impossible to determine
Title: If a min-heap has 1024 nodes, what is its height?
Difficulty: Hard
Section Reference 1: 17.6 Heaps
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
Title: When we map a min-heap to an array, we place the root value at which array index?
Difficulty: Easy
Section Reference 1: 17.6 Heaps
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
Title: When we map a min-heap to array, the right child of the root is stored where?
Difficulty: Medium
Section Reference 1: 17.6 Heaps
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(n2)
Title: What is the complexity of adding an element to a heap?
Difficulty: Medium
Section Reference 1: 17.6 Heaps
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(n2)
Title: What is the complexity of removing an element from a heap?
Difficulty: Medium
Section Reference 1: 17.6 Heaps
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
Title: What is the maximum height increase associated with adding n elements to a heap?
Difficulty: Hard
Section Reference 1: 17.6 Heaps
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));
Title: Select statement to complete method that displays n smallest values
Difficulty: Medium
Section Reference 1: 17.6 Heaps
108) What is the efficiency of the heapsort algorithm?
a) O(1)
b) O(log (n))
c) O(n log (n))
d) O(n2)
Title: What is the efficiency of the heapsort algorithm?
Difficulty: Medium
Section Reference 1: 17.7 The Heapsort Algorithm
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
Title How many times during the heapsort algorithm does the fixHeap method need to be called for a max-heap with n elements?
Difficulty: Hard
Section Reference 1: 17.7 The Heapsort Algorithm
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
Title: Which action(s) will invalidate a min-heap?
Difficulty: Hard
Section Reference 1: 17.7 The Heapsort Algorithm