Revel for Liang C++, Fourth Edition, Y. Daniel Liang

This quiz is for students to practice. A large number of additional quiz is available for instructors using Quiz Generator from the Instructor's Resource Website. Videos for Java, Python, and C++ can be found at https://yongdanielliang.github.io/revelvideos.html.

Chapter 21 Binary Search Trees


Section 21.2 Binary Search Trees
21.1  A __________ (with no duplicate elements) has the property that for every node in the tree the value of any node in its left subtree is less than the value of the node and the value of any node in its right subtree is greater than the value of the node.
A. binary tree
B. binary search tree
C. list
D. linked list

21.2  The _______ of a nonempty tree is the length of the path from the root node to its furthest leaf.
A. length
B. depth
C. height
D. degree

21.3  The height of an empty tree is _______.
A. -1
B. 0
C. 1
D. 2

21.4  The ________ of a path is the number of the edges in the path.
A. length
B. depth
C. height
D. degree

21.5  The height of a tree that contains a single node is _______.
A. -1
B. 0
C. 1
D. 2

21.6  The ________ is to visit the left subtree of the current node first, then the current node itself, and finally the right subtree of the current node.
A. inorder traversal
B. preorder traversal
C. postorder traversal
D. breadth-first traversal

21.7  The _________ is to visit the left subtree of the current node first, then the right subtree of the current node, and finally the current node itself.
A. inorder traversal
B. preorder traversal
C. postorder traversal
D. breadth-first traversal

21.8  The _________ is to visit the current node first, then the left subtree of the current node, and finally the right subtree of the current node.
A. inorder traversal
B. preorder traversal
C. postorder traversal
D. breadth-first traversal

21.9  The _________ is to visit the nodes level by level. First visit the root, then all children of the root from left to right, then grandchildren of the root from left to right, and so on.
A. inorder traversal
B. preorder traversal
C. postorder traversal
D. breadth-first traversal

21.10  Suppose the keys 3, 4, 45, 21, 92, 12 are inserted into a BST in this order. What is the inorder traversal of the elements?
A. 3 4 12 21 45 92
B. 3 4 45 21 12 92
C. 12 21 92 45 4 3
D. 4 45 21 12 92 3
E. 4 21 12 92 45 3

21.11  Suppose the keys 3, 4, 45, 21, 92, 12 are inserted into a BST in this order. What is the preorder traversal of the elements?
A. 3 4 12 21 45 92
B. 3 4 45 21 12 92
C. 12 21 92 45 4 3
D. 4 45 21 12 92 3
E. 4 21 12 92 45 3

21.12  Suppose the keys 3, 4, 45, 21, 92, 12 are inserted into a BST in this order. What is the postorder traversal of the elements?
A. 3 4 12 21 45 92
B. 3 4 45 21 12 92
C. 12 21 92 45 4 3
D. 4 45 21 12 92 3
E. 4 21 12 92 45 3

21.13  Suppose the keys 3, 4, 45, 21, 92, 12 are inserted into a BST in this order. What is the preorder traversal of the elements after inserting 2 into the tree?
A. 3 2 4 12 21 45 92
B. 3 2 4 45 21 12 92
C. 12 2 21 92 45 4 3
D. 4 2 45 21 12 92 3
E. 4 2 21 12 92 45 3

21.14  Suppose the keys 3, 4, 45, 21, 92, 12 are inserted into a BST in this order. What is the preorder traversal of the elements after deleting 45 from the tree?
A. 3 4 12 21 92
B. 3 4 21 12 92
C. 12 21 92 45 4 3
D. 4 21 12 92 3
E. 4 21 12 92 3

21.15  If a set of the same elements is inserted into a binary tree in two different orders, which of the following statements are true?
A. The two corresponding binary trees look the same.
B. The inorder traversal generate the same sequence of nodes.
C. The preorder traversal generate the same sequence of nodes.
D. The postorder traversal generate the same sequence of nodes.

21.16  If you insert 4, 5, 1, 2, 9, 3 into a binary search tree in this order, what the inorder traversal of this tree?
A. 4, 5, 1, 2, 9, 3
B. 3, 9, 2, 1, 5, 4
C. 1, 2, 3, 4, 5, 9
D. 2, 5, 1, 4, 9, 3

21.17  A new element is always inserted into a leaf node.
A. True
B. False

Section 21.3 Deleting Elements from a BST
21.18  The time complexity for searching an element in a binary search tree is _______ in the worst case.
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n^2)

21.19  The time complexity for inserting an element into a binary search tree is _______ in the worst case.
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n^2)

21.20  The time complexity for deleing an element into a binary search tree is _______ in the worst case.
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n^2)

Section 21.4 Iterators
21.21  True or False? You can traverse the elements in a BST using a foreach loop.
A. True
B. False