Test Bank Chapter 26 - A Binary Search Tree Implementation

Chapter 26 - A Binary Search Tree Implementation

True/False (8)

1. The shape of a binary search tree affects the efficiency of the simple recursive search algorithm.
2. You can create different binary search trees from the same data.
3. Binary search trees are not an efficient choice for searching if the data tends to remain stable.
4. Searching a binary search tree is like performing a binary search of an array.
5. Every addition to a binary search tree adds a new root.
6. When adding an entry to a binary search tree, the search ends at a leaf if the entry is not already in the tree.
7. For best performance, when you add entries to a binary search tree, you should add them in sorted order.
8. You can implement the ADT dictionary using a binary search tree.

Short Answer (11)

1. Why can’t the two setTree methods that are inherited from BinaryTree be used in the class BinrarySearchTree?
2. How does the class BinarySearchTree handle the two setTree methods that are inherited from BinaryTree?
3. Write a pseudo code algorithm for searching a binary search tree.

return false
else if (object being searched for is equal to the root of the tree)
return true
else if (object being searched for is less than the root of the tree)
recursively call the search algorithm on the left subtree
else
recursively call the search algorithm on the right subtree

1. Draw the binary search tree from the following input.
   4, 10, 12, 54, 19, 27, 7, 2

1. Given the following binary search tree, draw the tree after adding 3.
   

1. Given the following binary search tree, draw the tree after adding 9.
   

1. How do you remove a node that is a leaf in a binary search tree?
2. When you add entries to a binary search tree, if possible, you should not add them in sorted order. Explain.
3. Given the following binary search tree, draw the tree after deleting the node with the value 55.
   

1. Given the following binary search tree, draw the tree after deleting the node with the value 35.
   

1. Given the following binary search tree, draw the tree after deleting the node with the value 5.
   

Multiple Choice (27) WARNING: CORRECT ANSWERS ARE IN THE SAME POSITION AND TAGGED WITH . YOU SHOULD RANDOMIZE THE LOCATION OF THE CORRECT ANSWERS IN YOUR EXAM.

1. The data in a node’s _____ subtree are less than the data in a node’s _____ subtree.
   1. left, right
   2. right, left
   3. left, middle
   4. middle, right
2. In the interface SearchTreeInterface, what does the method getEntry return if the object being sought doesn’t exist?
   1. null
   2. false
   3. 0
   4. throws an exception
3. In the interface SearchTreeInterface, what does the method remove return if the object being sought doesn’t exist?
   1. null
   2. false
   3. 0
   4. throws an exception
4. In the interface SearchTreeInterface, what does the method add return if the object being added doesn’t exist?
   1. null
   2. false
   3. 0
   4. throws an exception
5. In the interface SearchTreeInterface, what does the method add return if the object being added already exists in the tree?
   1. the existing entry that matched the parameter
   2. true
   3. 1
   4. throws an exception
6. In the interface SearchTreeInterface, the method getEntry returns an object in the tree that matches the given entry according to the entry’s _____ method.
   1. compareTo
   2. equalTo
   3. equals
   4. same
7. In a binary search tree, the getInorderIterator inherited from the class BinaryTree sorts data
   1. in ascending order
   2. in descending order
   3. in striped order
   4. none of the above
8. Every addition to a binary search tree adds a new
   1. leaf
   2. parent
   3. ancestor
   4. root
9. If a node x is the inorder predecessor of node y then node x must appear in y’s _____ subtree.
   1. left
   2. right
   3. middle
   4. all of the above
10. If a node x is the inorder successor of node y then node x must appear in y’s _____ subtree.
    1. right
    2. left
    3. middle
    4. all of the above
11. The inorder predecessor of a node N is
    1. the largest entry in N’s left subtree
    2. the largest entry in N’s right subtree
    3. the smallest entry in N’s left subtree
    4. the smallest entry in N’s right subtree
12. The inorder successor of a node N is
    1. the smallest entry in N’s right subtree
    2. the smallest entry in N’s left subtree
    3. the largest entry in N’s right subtree
    4. the largest entry in N’s left subtree
13. The largest entry in a node N’s left subtree is
    1. the subtree’s rightmost node
    2. the subtree’s leftmost node
    3. the left child of N
    4. the right child of N
14. The largest entry in a node N’s right subtree is
    1. the subtree’s rightmost node
    2. the subtree’s leftmost node
    3. the left child of N
    4. the right child of N
15. The smallest entry in a node N’s left subtree is
    1. the subtree’s leftmost node
    2. the subtree’s rightmost node
    3. the left child of N
    4. the right child of N
16. The smallest entry in a node N’s right subtree is
    1. the subtree’s leftmost node
    2. the subtree’s rightmost node
    3. the left child of N
    4. the right child of N
17. When adding an entry to a binary search tree, when does the search end?
    1. when the item is found
    2. at a leaf if the entry is not already in the tree
    3. both a & b
    4. none of the above
18. Given a binary search tree with n nodes and height h, what is the maximum number of comparisons that each operation requires for the method add?
    1. O(h)
    2. O(n)
    3. O(log h)
    4. O(1)
19. Given a binary search tree with n nodes and height h, what is the maximum number of comparisons that each operation requires for the method remove?
    1. O(h)
    2. O(n)
    3. O(log h)
    4. O(1)
20. Given a binary search tree with n nodes and height h, what is the maximum number of comparisons that each operation requires for the method getEntry?
    1. O(h)
    2. O(n)
    3. O(log h)
    4. O(1)
21. The maximum possible height of a binary search tree with n nodes is
    1. n
    2. log n
    3. n²
    4. n-2
22. What is the worst-case performance of the add method in a binary search tree with linked nodes?
    1. O(n)
    2. O(1)
    3. O(log n)
    4. O(n2)
23. What is the worst-case performance of the remove method in a binary search tree with linked nodes?
    1. O(n)
    2. O(1)
    3. O(log n)
    4. O(n2)
24. What is the worst-case performance of the getEntry method in a binary search tree with linked nodes?
    1. O(n)
    2. O(1)
    3. O(log n)
    4. O(n2)
25. What is the worst-case performance of the add method in a full binary search tree with linked nodes?
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n2)
26. What is the worst-case performance of the remove method in a full binary search tree with linked nodes?
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n2)
27. What is the worst-case performance of the getEntry method in a full binary search tree with linked nodes?
    1. O(log n)
    2. O(n)
    3. O(1)
    4. O(n2)