Chase Trees Test Bank Docx Chapter 19 - Java Foundations 4th Edition | Test Bank with Answer Key by John Lewis by John Lewis, Peter DePasquale, Joe Chase. DOCX document preview.
Chapter 19: Trees
Multiple Choice Questions:
1) A user has designed an interface for a binary tree abstract data type (ADT). Which method below requires knowledge of the purpose and organization of the binary tree in order to design an implementation?
a) find
b) add
c) contains
d) isEmpty
e) size
2) 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
3) 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.
4) A full binary tree of height n has _________________ leaves.
a) 2n
b) 3n
c) 2n
d) 2(n+1)
e) 3(n+1)
5) 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
6) 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
7) 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
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) 2n and 22n
c) 2n+1 and 2n+2
d) n-1 and n-2
e) none of the above will work
9) 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
10) A balanced binary tree with m elements will have height ______________ .
a) 2m
b) 2m
c) logm 2
d) log2 m
e) none of the above
11) 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
12) 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
13) The find method to locate an element in a binary tree can be implemented
a) iteratively
b) recursively
c) independently
d) both a) and b) are correct
e) all of a), b), and c) are correct
14) Which of the following traversals never visits the root?
a) Preorder
b) Inorder
c) Postorder
d) Level-order
e) none of the above
15) 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
1) In a tree, a node that does not have any children is called a leaf.
2) The height of a tree and the depth of a tree are different.
3) A binary tree is a tree in which any node can have at most two children.
4) Since trees are nonlinear structures, it is impossible to implement them using an array.
5) The methods in the Binary Tree ADT all return references to elements.
6) There are four basic ways to traverse a tree, and they are all implemented recursively.
7) A decision tree cannot be used as the basis for an expert system.
8) In an inorder traversal, the elements of a tree are visited in order of their distance from the root.
9) In a postorder traversal, the root is the last element visited in the tree.
10) Recursive methods that work with binary trees are often implemented with a private support method.
1) How many leaves will be contained in a full binary tree of height 5?
2) What does it mean for a tree to be balanced?
3) If a tree has order 4, what does this mean?
4) Explain the implementation of a level-order traversal of a tree.
5) Explain the implementation of an postorder traversal.
6) 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?
7) Explain how a binary tree can be implemented using an array.
8) 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.
9) 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.
10) What is a decision tree?
11) What is the root of a tree?
12) What are the leaves of a tree?
13) What is a disadvantage of implementing a tree as an array using computed links?
14) What are the issues involved in implementing an add or a remove method for a binary tree?
15) What differences can there be between a complete binary tree and a full binary tree?
Document Information
Connected Book
Java Foundations 4th Edition | Test Bank with Answer Key by John Lewis
By John Lewis, Peter DePasquale, Joe Chase