Deck 17: Tree Structures

Question 1

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

Answer 1

Nodes R and N form a subtree

Question 2

Which of the following statements about trees is NOT correct?
A.The height of a tree is based on the longest path from the root to a leaf.
B.Many tree properties are computed with recursive methods.
C.A simple implementation of a Tree class uses an instance variable for the root node and a nested Node class, which stores the node's data and its children.
D.A subtree rooted at node n is the tree formed by taking n as the root node and including all of its ancestors.

Answer 2

A subtree rooted at node n is the tree formed by taking n as the root node and including all of its ancestors.

Question 3

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

Answer 3

H is a descendant of M

Question 4

Consider the following tree diagram: Which of the following nodes are leaf nodes?

A)C
B)B
C)B and H
D)H

Question 5

Consider the following tree diagram: Which of the following is a path in the tree?
A.R, H, X
B.K, D, P
C.C, R, N, X
D.T, L, P, C

Question 6

Consider the following tree diagram: Which of the following is NOT a path starting with the node P in the tree?
A.P, L, T
B.P, K, D
C.P
D.P, B

Question 7

Given the Node class (partially shown below), select a statement to complete the recursive method descendants, which is designed to return the number of descendants of a node.
A.num = num + child.descendants();
B.num = num + child.descendants() + 1;
C.num = child.descendants();
D.num = num + child.children.size();

Question 8

Given the Node class (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.
A.children.size() == 0
B.children.get(0) == null
C.data == null
D.root == null

Question 9

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

Question 10

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

Question 11

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

Question 12

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

Question 13

Consider the following tree diagram: What is the height of this tree?
A.7
B.3
C.6
D.4

Question 14

Consider the following tree diagram: Which of the following nodes are root nodes?

A)R
B)P
C)C
D)R and P

Question 15

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

Question 16

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

Question 17

Consider the following tree diagram: What is the height of this tree?
A.5
B.7
C.3
D.4

Question 18

Consider the following tree diagram: What is the size of this tree?
A.5
B.6
C.4
D.13

Question 19

Consider the following tree diagram: Which of the following nodes are parent nodes?
A.R
B.N
C.M
D.B

Question 20

Which of the following statements about trees is NOT correct?
A.The root of the tree does not have a parent.
B.A tree is composed of nodes.
C.A node can have multiple parents.
D.A node can have multiple child nodes.

Question 21

Which of the following statements about balanced trees is NOT correct?
A.For a given height, a balanced tree can hold more nodes than an unbalanced tree.
B.In a balanced binary tree, each subtree has approximately the same number of nodes.
C.In a balanced tree, all paths from the root to the leaves have approximately the same length.
D.The efficiency of algorithms for balanced trees is better expressed using the size of the tree than the height of the tree.

Question 22

Which of the following is NOT an example of a binary tree?
A.A decision tree where each interior node contains a question and the two subtrees correspond to a yes or no answer.
B.An expression tree that shows the order of evaluation in an arithmetic expression.
C.The family tree of a person, which includes all descendants of a person.
D.A Huffman tree where the left and right turns on the paths to the leaves describe binary encodings.

Question 23

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

Question 24

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

Question 25

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)

Question 26

A balanced binary tree with 260 nodes has a height of approximately ____.
A.13
B.8
C.12
D.10

Question 27

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)

Question 28

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 (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.
A.maxChildHeight + 1
B.maxChildHeight + 2
C.maxChildHeight
D.maxChildHeight + height()

Question 29

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

Question 30

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

Question 31

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

Question 32

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

Question 33

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

Question 34

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

Question 35

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

Question 36

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

Question 37

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

Question 38

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

Question 39

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

Question 40

A completely filled binary tree with a height of 3 has ____ nodes.
A.12
B.6
C.7
D.8

Question 41

Consider the following binary search tree diagram: Consider the following pseudocode for the removal of a node n in a binary search tree:
if n has no children then
remove the node n
if n has only one child then
replace the node n with its child
if n has two children then
replace the node n with the smallest node of its right subtree
If node D is to be removed, which action should be taken?
A.Swap the values in C and D so that C has A as its left child, then remove the new D node.
B.Modify K to point to A as its left child, and modify A to point to F as its right child.
C.Modify K to make its left child null.
D.Modify K to point to F as its left child and modify F to point to A as its left child.

Question 42

Which of the following statements about a binary search tree is correct?
A.You can specify an insert position for inserting a node in the tree.
B.Locating an element in a balanced binary search tree takes O(n) time.
C.The speed of inserting or removing a node is dependent on the shape of the tree.
D.Adding elements that are already sorted will result in a balanced binary search tree.

Question 43

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

Question 44

Consider the following binary search tree diagram: Consider the following addNode method for inserting a newNode into a binary search tree:
public void addNode(Node newNode)
{
int comp = newnode.data.compareTo(data);
if (comp < 0)
{
if (left == null) {left = newNode;}
else { left.addNode(newNode); }
}
else
{
if (right == null) {right = newNode;}
else { right.addNode(newNode); }
}
}
Which of the following trees represents the correct result after inserting element B, calling addNode on the root of the tree?
A.III
B.IV
C.II
D.I

Question 45

Consider the following addNode method for inserting a newNode into a binary search tree: Which of the following sequences of insertions will result in a balanced tree? In each sequence, the first node inserted becomes the root of the tree on which the addNode method is called for the subsequent insertions.
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 and II only
B.I only
C.II only
D.I and III only

Question 46

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.all will be < 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.the root's left child value < 45, but the right child of the root's left child value is > 45

Question 47

Consider the following binary search tree diagram: Consider the following pseudocode for the removal of a node n in a binary search tree:
if n has no children then
remove the node n
if n has only one child then
replace the node n with its child
if n has two children then
replace the node n with the smallest node of its right subtree
If node Y is to be removed, which action should be taken?
A.Modify V's right reference to point to X.
B.Modify V to have a null right pointer.
C.Modify V's left reference to point to X.
D.Swap the values in V and X, and modify X's right reference to point to V.

Question 48

Consider the following binary search tree diagram: Consider the following pseudocode for the removal of a node n in a binary search tree:
if n has no children then
remove the node n
if n has only one child then
replace the node n with its child
if n has two children then
replace the node n with the smallest node of its right subtree
If node J is to be removed, to which node will H point to instead of J?
A.X
B.N
C.M
D.L

Question 49

Consider the following binary search tree diagram: Consider the following addNode method for inserting a newNode into a binary search tree:
public void addNode(Node newNode)
{
int comp = newnode.data.compareTo(data);
if (comp < 0)
{
if (left == null) {left = newNode;}
else { left.addNode(newNode); }
}
else
{
if (right == null) {right = newNode;}
else { right.addNode(newNode); }
}
}
Which nodes will be visited in order to insert the letter B into this tree, calling addNode on the root of the tree?
A.H, D, and A
B.H and D only
C.H only
D.H, D, and F

Question 50

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.some values will be > 45, but there may be a few values < 45
B.all will be > 45
C.the root's right child value > 45, but the left child of the root's right child key is < 45
D.approximately half the values are < 45, the other half are > 45

Question 51

A completely filled binary tree with a height of 4 has ____ nodes.
A.16
B.12
C.8
D.15

Question 52

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

Question 53

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

Question 54

Consider the following binary search tree diagram: Consider the following addNode method for inserting a newNode into a binary search tree:
public void addNode(Node newNode)
{
int comp = newnode.data.compareTo(data);
if (comp < 0)
{
if (left == null) {left = newNode;}
else { left.addNode(newNode); }
}
else
{
if (right == null) {right = newNode;}
else { right.addNode(newNode); }
}
}
Which nodes will be visited in order to insert the letter E into this tree, calling addNode on the root of the tree?
A.H only
B.H and D only
C.H, D, and A
D.H, D, and F

Question 55

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

Question 56

Given the BinaryTree class (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.
A.rightMostValue(n.left)
B.rightMostValue(root.right)
C.rightMostValue(n)
D.rightMostValue(n.right)

Question 57

Consider the following binary search tree diagram: Consider the following addNode method for inserting a newNode into a binary search tree:
public void addNode(Node newNode)
{
int comp = newnode.data.compareTo(data);
if (comp < 0)
{
if (left == null) {left = newNode;}
else { left.addNode(newNode); }
}
else
{
if (right == null) {right = newNode;}
else { right.addNode(newNode); }
}
}
Which of the following trees represents the correct result after inserting element T, calling addNode on the root of the tree?
A.II
B.I
C.IV
D.III

Question 58

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

Question 59

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

Question 60

Given the BinaryTree class (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.
A.n.right == null
B.n.left == null || n.right == null
C.n.left == null
D.n.left == null && n.right == null

Question 61

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

Question 62

What are the

Question 63

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

Question 64

You wish to traverse a binary search tree in sorted order.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.II, III, I
C.III, I, II
D.III, II, I

Question 65

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

Question 66

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

Question 67

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.Preorder traversal is used for removing file directories by removing subdirectories first.
D.Postorder traversal is used for copying file directories.

Question 68

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

Question 69

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

Question 70

Given the BinarySearchTree and Node classes (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.
A.right.smallest()
B.left.smallest()
C.Math.min(left.smallest(), right.smallest())
D.data.smallest()

Question 71

You wish to traverse a binary search tree 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.II, III, I
B.II, I, III
C.I, II, III
D.III, I, II

Question 72

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

Question 73

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

Question 74

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.III, II, I
B.I, III, II
C.III, I, II
D.I, II, III

Question 75

Which of the following statements about breadth-first and depth-first traversal is NOT correct?
A.Depth-first search goes deeply into the tree and then backtracks when it reaches the leaves.
B.Breadth-first and depth-first search only work on a binary tree.
C.Breadth-first search first visits all nodes on the same level before visiting the children.
D.Depth-first search uses a stack to track the nodes that it visits.

Question 76

Assuming that the variable t is instantiated to an empty BinarySearchTree, select a statement to complete the following code segment, so that the resulting binary search tree has a height of 4.
A.t.add("your");
B.t.add("the");
C.t.add("his");
D.t.add("my");

Question 77

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

Question 78

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".
A.data.toString().indexOf("007") > 0
B.data.equals("007")
C.data.toString().indexOf("007") >= 0
D.data.contains("007")

Question 79

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

Question 80

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./, +, 2, 8, 5
D./, +, 8, 2, 5