Introduction to Java Programming and Data Structures, 12E, 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 25 Binary Search Trees


Section 25.2 Binary Search Tree Basics
25.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

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

25.3  The _______ of a node is the length of the path from the root to the node.
A. length
B. depth
C. height
D. degree

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

Section 25.3 Representing Binary Search Trees
25.5  Which of the following is correct to create a TreeNode for integer 50.
A. TreeNode<int> node = new TreeNode<int>(50);
B. TreeNode<Integer> node = new TreeNode<Integer>(50);
C. TreeNode<Integer> node = new TreeNode<>(50);
D. TreeNode<int> node = new TreeNode<>(50);

Section 25.4 Searching for an Element
25.6  What is the return type for the search function?
A. int
B. double
C. char
D. boolean

25.7  The time complexity for searching an element in a binary search tree is _______.
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n^2)

Section 25.5 Inserting an Element into a BST
25.8  A new element is always inserted into a leaf node.
A. True
B. False

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

Section 25.6 Tree Traversal
25.10  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

25.11  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

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

25.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?
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

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

25.15  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

25.16  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

25.17  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

Section 25.7 The BST Class
25.18  In the implementation of BST, which of the following are true?
A. Node is defined as an inner class inside BST.
B. Node is defined as a static inner class inside BST because it does not reference any instance data fields in BST.
C. Node has a property named left that links to the left subtree and a property named right that links to the right subtree and a property named element.
D. BST contains a property named root. If tree is empty, root is null.

Section 25.8 Deleting Elements from a BST
25.19  The time complexity for deleting an element from a binary search tree is _______.
A. O(n)
B. O(logn)
C. O(nlogn)
D. O(n^2)

Section 25.9 Tree Visualization and MVC
25.20  What is the signature of the recursive method in BTView.java?
A. displayTree()
B. displayTree(BST.TreeNode<Integer>, double, double, double)
C. displayTree(BST.TreeNode<String>, double, double, double)
D. displayTree(BST.TreeNode<Integer>, int, int, int)

25.21  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

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

Section 25.11 Case Study: Data Compression
25.23  A Huffman tree is constructed using a ____________ algorithm.
A. dynamic programming
B. divide-and-conquer
C. greedy
D. back-tracking