Deck 17: Tree Structures

Question 1

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

Answer 1

D

Question 2

Consider the following tree diagram: What is the height of this tree?

A) 3
B) 4
C) 6
D) 7

Answer 2

B

Question 3

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.

Answer 3

B

Question 4

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

Question 5

Consider the following tree diagram: What is the size of this tree?

A) 4
B) 5
C) 6
D) 13

Question 6

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

Question 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

Question 8

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

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

Question 9

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

Question 10

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

Question 11

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

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

Question 12

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

Question 13

Consider the following tree diagram: What is the height of the subtree with root R?

A) 2
B) 3
C) 4
D) 6

Question 14

Consider the following tree diagram: What is the height of the subtree with root P?

A) 3
B) 4
C) 5
D) 6

Question 15

Consider the following tree diagram: What is the height of this tree?

A) 3
B) 4
C) 5
D) 7

Question 16

Consider the following tree diagram: What is the size of the subtree with root P?

A) 3
B) 4
C) 5
D) 6

Question 17

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

Question 18

Consider the following tree diagram: What is the size of the subtree with root R?

A) 2
B) 3
C) 4
D) 6

Question 19

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

Question 20

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

Question 21

A binary tree of height h can have up to ____ nodes.

A) 2h - 1
B) 2h + 1
C) 2^h - 1
D) 2^h + 1

Question 22

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 23

Consider the following tree diagram:
Which arithmetic expression is represented by this tree?

A) (2 + 3) + (5 $\times$ 4) $\times$ 6 $\times$ (- 1)
B) 2 + 3 + 5 $\times$ 4 - 6 - 1
C) (2 + 3) $\times$ (5 $\times$ 4) $\times$ (6 - 1)
D) [(2 + 3) + (5 $\times$ 4)] $\times$ (6 - 1)

Question 24

Consider the following tree diagram: Which arithmetic expression is represented by this tree?

A) 2 $\times$ 3 + 5 + 4 $\times$ 6 - 1
B) 2 $\times$ 3 + 5 + 4 - 6 - 1
C) 2 $\times$ (3 + 5 + 4) $\times$ (6 - 1)
D) [(2 $\times$ 3) + 5 + 4] $\times$ (6 - 1)

Question 25

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

Question 26

Consider the following Huffman encoding tree: The letter K will be encoded as ____.

A) 10
B) 010
C) 001
D) 100

Question 27

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.

Question 28

Consider the following Huffman encoding tree: The letter H will be encoded as ____.

A) 000
B) 011
C) 001
D) 010

Question 29

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

Question 30

Consider the following tree diagrams: Which of these trees is considered to be unbalanced?

A) I
B) II
C) III
D) II and III

Question 31

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

Question 32

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

Question 33

Consider the following tree diagrams:
Which tree represents the arithmetic expression 2 $\times$ 5 + 4?

A) I
B) II
C) Both I and II
D) Neither I nor II

Question 34

A completely filled binary tree with a height of 3 has ____ nodes.

A) 6
B) 7
C) 8
D) 12

Question 35

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

Question 36

Consider the following tree diagrams:
Which tree represents the arithmetic expression 2 + 5 $\times$ 4?

A) I
B) II
C) Both I and II
D) Neither I nor II

Question 37

A completely filled binary tree with a height of 4 has ____ nodes.

A) 8
B) 12
C) 15
D) 16

Question 38

A binary tree with 260 nodes has a height of approximately ____.

A) 8
B) 10
C) 12
D) 13

Question 39

Consider the following tree diagrams:
Which tree represents the arithmetic expression (2 + 5) $\times$ 4?

A) I
B) II
C) Both I and II
D) Neither I nor II

Question 40

A binary tree with 520 nodes has a height of approximately ____.

A) 9
B) 10
C) 12
D) 13

Question 41

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.

Question 42

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

Question 43

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

Question 44

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

Question 45

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

Question 46

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.

Question 47

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.

Question 48

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

Question 49

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.

Question 50

Consider the following tree diagrams: Which are binary search trees?

A) I
B) II
C) I and II
D) Neither I nor II

Question 51

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

Question 52

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

Question 53

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

Question 54

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

Question 55

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

Question 56

Locating an element in a balanced binary search tree takes ____ time.

A) O(n)
B) O(log(n))
C) O(1)
D) O(n²)

Question 57

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

Question 58

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

Question 59

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

Question 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.

Question 61

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

Question 62

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

Question 63

Adding an element to a balanced binary search tree takes ____ time.

A) O(n)
B) O(log (n))
C) O(1)
D) O(n²)

Question 64

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

Question 65

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

Question 66

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

Question 67

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

Question 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²)

Question 69

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.

Question 70

Adding an element to an unbalanced binary search tree takes ____ time.

A) O(n)
B) O(log (n))
C) O(1)
D) O(n²)

Question 71

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.

Question 72

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

Question 73

Removing an element from a balanced binary search tree takes ____ time.

A) O(n)
B) O(log (n))
C) O(1)
D) O(n²)

Question 74

Removing an element from an unbalanced binary search tree takes ____ time.

A) O(n)
B) O(log (n))
C) O(1)
D) O(n²)

Question 75

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

Question 76

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

Question 77

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

Question 78

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

Question 79

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

Question 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