Complete Test Bank Chapter 20 Binary Search Trees

Chapter 20: Binary Search Trees

Multiple Choice Questions:

1) A _____________________ is a tree whose elements are organized to facilitate finding a particular element when needed.

a) full tree

b) complete tree

c) binary tree

d) search tree

e) none of the above

2) In a binary search tree, the elements in the right subtree of the root are __________________ the root element.

a) greater than

b) less than

c) greater than or equal to

d) less than or equal to

e) equal to

3) In a binary search tree, the elements in the left subtree of the root are __________________ the root element.

a) greater than

b) less than

c) greater than or equal to

d) less than or equal to

e) equal to

4) When adding a new element to a binary search tree, the element is added as a(n) ______________.

a) internal node

b) subtree

c) leaf

d) root

e) none of the above

5) A binary search tree that is highly unbalanced is called a ________________ tree.

a) full

b) complete

c) degenerate

d) unsearchable

e) none of the above

6) When removing an element from a binary search tree, we must always ______________________.

a) make sure that the new tree is a binary search tree

b) build a new tree

c) find its inorder successor

d) remove all of its children

e) An element should never be removed from a binary search tree.

7) When removing an element from a binary search tree that is a leaf, ______________ will ensure that the resulting tree is still a binary search tree.

a) replacing it with its only child

b) replacing it with its inorder successor

c) simply deleting it

d) all of the above

e) neither a, b, nor c

8) When removing an element from a binary search tree that has a single child, _____________________ will ensure that the resulting tree is still a binary search tree.

a) replacing it with its only child

b) replacing it with its inorder successor

c) simply deleting it

d) all of the above

e) neither a, b, nor c

9) When removing an element from a binary search tree that has two children, _______________________ will ensure that the resulting tree is still a binary search tree.

a) replacing it with its only child

b) replacing it with its inorder successor

c) simply deleting it

d) all of the above

e) neither a, b, nor c

10) Finding an element in a balanced binary search tree that contains n elements requires _____________________ comparisons.

a) O(1)

b) O(n)

c) O(2ⁿ)

d) O(log₂ n)

e) none of the above

11) In the worst case, a general binary search tree could require __________________ comparisons to find an element.

a) O(1)

b) O(n)

c) O(2ⁿ)

d) O(log₂ n)

e) none of the above

12) If a binary search tree becomes unbalanced after an element is added, it is sometimes possible to efficiently rebalance the tree by ___________________ .

a) using left and right rotations

b) selecting a leaf node to use as a new root

c) reconstructing the tree from scratch

d) all of the above

e) it is impossible to rebalance a tree efficiently

13) Adding an element to a binary search tree requires that the element must

a) be an int

b) have a value that is in between the smallest and the largest value already in the binary search tree

c) be Comparable

d) have a positive value

e) none of the above

14) What is returned when a node to be removed from a binary search tree is not present in a tree?

a) nothing

b) the root element

c) the element whose search value is closest to the one that should be removed.

d) the parent element of the node being removed

e) none of the above

15) The balance factor of a node in an AVL tree is

a) the number of nodes below it

b) the number of nodes above it

c) the height of its right subtree minus the height of its left subtree

d) the depth of the node from the root

e) always positive

1) A binary search tree is always a full tree.

2) Finding an element in a binary search tree always requires O(log₂ n) comparisons.

3) In a binary search tree, a new element is always added as a leaf.

4) In a balanced binary search tree, adding an element always requires approximately O(log₂ n) steps.

5) In a binary search tree, the elements in the right subtree of the root are always larger than the element stored at the root.

6) Left and right rotations can be used to rebalance an unbalanced binary search tree.

7) An AVL tree is often implemented so that a node contains a reference to its parent node.

8) An ordered set of elements can be maintained using a linked list or a binary search tree. It is generally faster to locate an element in a binary search tree than it is to locate an element in a linked list.

9) A Red/Black tree is often implemented so that a node contains a reference to its parent node.

10) The most efficient binary search trees are balanced.

1) What is a binary search tree?

2) Explain how to add an element to a binary search tree.

3) Describe how to find an element in a binary search tree. You may use English sentences or pseudocode.

4) Draw a binary search tree that results from inserting the following elements: 12, 16, 9, 1, 15, 13

5) What is the inorder successor of a node in a binary search tree?

6) What is special about the order in which the nodes are visited in an inorder traversal of a binary search tree?

7) Do the find and add operations on a binary search tree always require at most O(log₂ n) comparisons? If so, why? If not, why not?

8) What can make a balanced binary search tree become unbalanced?

9) In an AVL tree, each node keeps track of its own balance factor. What value(s) of the balance factor will trigger a rebalancing?

10) Explain the process of removing an element from a binary search tree.

11) Describe the steps involved in performing a right rotation on a node in a binary search tree.

12) Why is it important to keep a binary search tree balanced?

13) If a node in an AVL tree requires rebalancing, what other nodes in the tree may also require rebalancing?

14) Consider the following binary search tree.

12

/ \

9 16

/ / \

1 13 15

Show the tree that is the result of removing the following elements (in order): 13, 16, 12.

15) Suppose we have a class called BinaryTree that includes a find method. If we extend the class to create a BinarySearchTree class, should we override the find method or use it as is? Explain.