Deck 13: Trees

Question 1

The height of a tree and the depth of a tree are different.

Answer 1

False
Explanation: Height and depth are synonyms in the context of trees.

Question 2

Which of the following traversals visits the nodes that are closer to the top of the tree before visiting those that are closer to the bottom?

A) Preorder
B) Inorder
C) Postorder
D) Level-order
E) none of the above

Answer 2

D
Explanation: The level-order traversal visits each node at each level of the tree from the top to the bottom.

Question 3

What property of the tree does its order specify?

A) maximum height
B) maximum number of leaves
C) maximum number of internal nodes
D) maximum number of edges
E) maximum number of children per node

Answer 3

E
Explanation: The order of a tree represents the maximum number of children per node.

Question 4

In a full tree, all leaves are at the same level.

Question 5

Which of the following traversals visits the root after visiting the left and right subtrees?

A) Preorder
B) Inorder
C) Postorder
D) Level-order
E) none of the above

Question 6

Since trees are nonlinear structures, it is impossible to implement them using an array.

Question 7

In a tree, a node that does not have any children is called a leaf.

Question 8

One method of implementing a tree using an array involves storing the child of the element at the index n in the array at indexes ______________________________ .

A) n+1 and n+2
B) 2ⁿ and 2²ⁿ
C) 2n+1 and 2n+2
D) n-1 and n-2
E) none of the above will work

Question 9

A tree in which every node can have at most n children is referred to as a __________________ tree.

A) binary
B) ternary
C) n-ary
D) general
E) graph

Question 10

A full binary tree of height n has _________________ leaves.

A) 2ⁿ
B) 3n
C) 2n
D) 2(n+1)
E) 3(n+1)

Question 11

Which of the following best describes a balanced tree?

A) A balanced trees has all nodes at exactly the same level.
B) A balanced tree has no nodes at exactly the same level.
C) A balanced tree has half of the nodes at one level and half the nodes at another level.
D) A balanced tree has all of the nodes within one level of each other.
E) none of the above correctly describe a balanced tree.

Question 12

Which of the following traversals never visits the root?

A) Preorder
B) Inorder
C) Postorder
D) Level-order
E) none of the above

Question 13

A balanced binary tree with m elements will have height ______________ .

A) 2m
B) 2^m
C) log_m 2
D) log₂ m
E) none of the above

Question 14

A _________________ can be used as the basis for an expert system.

A) queue
B) stack
C) ternary tree
D) 4-ary tree
E) decision tree

Question 15

Which of the following traversals visits the root before visiting the left and right subtrees?

A) Preorder
B) Inorder
C) Postorder
D) Level-order
E) none of the above

Question 16

Which of the following traversals is implemented using a queue as a supporting data structure?

A) Preorder
B) Inorder
C) Postorder
D) Level-order
E) none of the above are implemented using a queue

Question 17

Which of the following tree traversals traverses the subtrees from left to right and then visits the root?

A) Preorder
B) Inorder
C) Postorder
D) Level-order
E) none of the above

Question 18

Which of the following traversals is not easily implemented recursively?

A) Preorder
B) Inorder
C) Postorder
D) Level-order
E) all of the above are easily implemented recursively

Question 19

A _________________ is a nonlinear structure in which elements are organized into a hierarchy.

A) graph
B) tree
C) queue
D) stack
E) linked-list

Question 20

A binary tree is a tree in which any node can have at most two children.

Question 21

Suppose we are implementing a binary tree as a linked structure of BinaryTreeNode objects. Write a method that will print out all of the nodes of tree via an inorder traversal. You may assume that the class has a reference to a BinaryTreeNode object called root. In addition, your method may take a reference to a BinaryTreeNode object as a parameter.

Question 22

In an inorder traversal, the root is the first element to be visited in the tree.

Question 23

How many leaves will be contained in a full binary tree of height 5?

Question 24

A decision tree cannot be used as the basis for an expert system.

Question 25

What does it mean for a tree to be balanced?

Question 26

In a postorder traversal, the root is the last element visited in the tree.

Question 27

What is a disadvantage of implementing a tree as an array using computed links?

Question 28

Suppose we are implementing a binary tree as a linked structure of BinaryTreeNode objects. Write a method that will print out all of the nodes of tree via a preorder traversal. You may assume that the class has a reference to a BinaryTreeNode object called root. In addition, your method may take a reference to a BinaryTreeNode object as a parameter.

Question 29

Explain how a binary tree can be implemented using an array.

Question 30

In an inorder traversal, the elements of a tree are visited in order of their distance from the root.

Question 31

What are the leaves of a tree?

Question 32

If a tree has order 4, what does this mean?

Question 33

What might be the difference between a complete binary tree and a full binary tree?

Question 34

Explain the implementation of an postorder traversal.

Question 35

There are four basic ways to traverse a tree, and they are all implemented recursively.

Question 36

What is a decision tree?

Question 37

Explain the implementation of a level-order traversal of a tree.

Question 38

Consider the following tree structure.
A
/ \
B C
/ \ \
D E F
In what order will the nodes be visited using a postorder, a preorder, an inorder, and a level-order traversal?

Question 39

What is an internal node in a tree?

Question 40

What is the root of a tree?