Binary search trees/Recursion

False

True/False: The number of nodes in a binary tree is the number of nodes in its left subtree plus the number of nodes in its right subtree.

root pointer

The ________ in a binary tree is analogous to the head pointer in a linked list.

A) null pointer

B) binary pointer

C) root pointer

D) leaf pointer

E) None of the above

True

True/False: A subtree is the collection of some node, together with all its descendants.

nodes in a binary tree have two successors instead of one.

The main difference between a binary tree and a linked list is that

A) a linked list can be empty, but a binary tree cannot.

B) recursion is useful on binary trees, but not on linked lists.

C) nodes in a binary tree have two successors instead of one.

D) a binary tree can be empty, but a linked list cannot.

E) None of the above

NULL .

If a node has no successor, the corresponding pointer is set to

A) point to its parent node.

B) NULL .

C) the root of the tree.

D) a leaf.

E) None of the above

the root of the tree.

Implementing a binary tree in a class requires a structure for representing the nodes of the binary tree, as well as a pointer to the structure as a class member. This pointer will be set to

A) the root of the tree.

B) the first leaf node.

C) the leftmost child node.

D) the deepest leaf node.

E) None of the above

Both A and B, but not C

Recursion can be used to

A) compute factorials.

B) find the greatest common divisor of two integers (GCD).

C) program things that cannot be programmed without recursion.

D) All of the above

E) Both A and B, but not C

does not correctly handle its base case.

The function

int fact(int k)

{

return k*fact(k-1);

if (k==0) return 1;

}

A) returns the value 1 if it is passed a value of 0 for the parameter k.

B) works for all non-negative values of k, but not for negative numbers.

C) computes the factorial on an integer k passed to it as parameter.

D) does not correctly handle its base case.

E) None of the above

determined by the order in which values are inserted.

The shape of a binary search tree is

A) determined by the order in which values are inserted.

B) always triangular.

C) determined by the programmer.

D) always balanced.

E) None of the above

D) All of the above

One method of traversing a binary tree is

A) preorder traversal.

B) postorder traversal.

C) inorder traversal.

D) All of the above

E) None of the above

True

True/False: Deleting a leaf node from a binary search tree is not difficult. Deleting a non-leaf node requires several steps.

True

True/False: There exists a binary tree with a hundred nodes, but only one leaf.

True

True/False: The preorder method of traversing a binary tree involves processing the root node's

data, traversing the left subtree, and then traversing the right subtree.

recursion.

Inorder, preorder, and postorder traversals can be accomplished using

A) recursion.

B) no pointers.

C) no parameters.

D) no arguments.

E) None of the above.

True

True/False: In a binary search tree where all the stored values are different, the node holding the largest value cannot have two children.

True

True/False: The smallest number of levels that a binary tree with three nodes can have is two.

three levels.

A tree with a height of three must have

A) three levels.

B) six nodes.

C) three subtrees.

D) one root and three nodes with two children each.

E) None of the above

True

True/False: The width of a tree is the largest number of nodes at the same level.

True

True/False: In a binary search tree, all nodes to the right of a node hold values greater than the node's value.

False

True/False: In certain types of binary trees, the number of leaves can be greater than the number of

nodes.

True

True/False: Binary trees are commonly used to organize key values that index database records.

D) All of the above

An operation that can be performed on a binary search tree is

A) insertion of new value.

B) removing a value stored in the tree.

C) searching the tree for the occurrence of a given value.

D) All of the above

E) None of the above

two pointers, one for the left child and one for the right child.

A binary tree can be created using a structure containing a data value and

A) two pointers, one for the left child and one for the right child.

B) a pointer to the last child node.

C) a pointer to the first child node.

D) two data nodes.

E) None of the above

its root node.

A program keeps track of a binary tree using a pointer to

A) its root node.

B) one of its leaves.

C) the node in the tree holding the smallest value.

D) the node in the tree holding the biggest value.

E) None of the above

its left and right child.

Every node in a binary tree can have pointers to

A) its left and right child.

B) its end nodes.

C) binary nodes.

D) its left and right parent.

E) None of the above

in database applications

Binary search trees are commonly used

A) with arrays of integers.

B) in linear data communication processes.

C) in database applications.

D) A and C

E) None of the above

left, node's

Values are commonly stored in a binary search tree so that a node's ________ child holds data that is less than the ________ data, while the node's data is less than the data in the other child.

A) left, right child's

B) left, node's

C) right, node's

D) right, left child's

E) None of the above

is hardest when the node has two children.

Deleting a node from a binary search tree node

A) is hardest when the node is a leaf.

B) is easiest when the node is the root.

C) is hardest when the node has two children.

D) is hardest when the node has one child.

E) None of the above

False

True/False: Output will be the same if you use inorder, postorder, or preorder traversals to print the values stored in a binary tree.

True

True/False: The height of a binary tree describes how many levels there are in the tree.

traversing the tree.

Visiting all nodes of a binary tree in some methodical fashion is known as

A) walking through tree.

B) climbing the tree.

C) branching out along the tree.

D) traversing the tree.

E) None of the above

D) All of the above

Binary search trees may be implemented as templates, but any data types used with them should support the ________ operator.

A) >

B) <

C) ==

D) All of the above

E) None of the above

to expedite the process of searching large sets of information.

A strong reason to use a binary search tree is

A) it is more flexible than the unary search tree.

B) aesthetics and program design.

C) to expedite the process of searching large sets of information.

D) to enhance code readability.

E) None of the above

True

True/False: Binary trees are called "trees" because they resemble an upside-down tree.

root node.

A binary tree node with no parent is called the

A) head pointer.

B) pointer node.

C) root node.

D) binary node.

E) None of the above

leaf node

A node that has no children is a

A) head node.

B) root node.

C) pure binary node.

D) leaf node.

E) None of the above

E) None of the above

A child node that has no parent is

A) a rootless node.

B) a leaf node.

C) an orphan node.

D) A or C

E) None of the above

True

True/False: The inorder method of traversing a binary tree involves traversing the left subtree,

processing the data in the root, and then traversing the right subtree.

binary search tree.

When a binary tree is used to facilitate a search, it is referred to as a

A) binary queue.

B) binary search tree.

C) sort algorithm.

D) binary ordered deque.

E) None of the above

the root node.

When an application begins searching a binary search tree, it starts at

A) the middle node, halfway between the root and the longest branch.

B) the outermost leaf node.

C) the rightmost child of the root node.

D) the root node.

E) None of the above

E) both A and D

The advantage of a linear search is that

A) it can be used on unordered data.

B) it is efficient.

C) it is fast.

D) it is simple.

E) both A and D

A) binary, linear

A(n) ________ search is more efficient than a(n) ________ search.

A) binary, linear

B) string, double

C) integer, double

D) linear, binary

E) None of the above. All searches are equally efficient

A) middle

A binary search begins by examining the ________ element of an array.

A) middle

B) last

C) smallest

D) first

E) largest

A) selection, bubble

The ________ sort usually performs fewer exchanges than the ________ sort.

A) selection, bubble

B) linear, bubble

C) linear, binary

D) bubble, selection

E) binary, linear

C) 50

To find a value that is in an unordered array of 100 items, linear search must examine an average of ________ values.

A) 7

B) 10

C) 50

D) 100

E) 101

B) 5 3 7 2 6 9

If a bubble sort is used to arrange the numbers 7 5 3 9 2 6 in ascending order, what order will the data be in after the first pass?

A) 5 7 3 9 2 6

B) 5 3 7 2 6 9

C) 2 5 3 9 7 6

D) 2 3 5 6 7 9

E) none of the above

A) 2 5 3 9 7 6

If a selection sort is used to arrange the numbers 7 5 3 9 2 6 in ascending order, what order will the data be in after the first pass?

A) 2 5 3 9 7 6

B) 2 3 5 6 7 9

C) 5 7 3 9 2 6

D) 5 3 7 2 6 9

E) none of the above

B) 7

If a binary search is used to search for the number 4 in the 11-element array shown below, which value will the 4 be compared to first? 1 2 3 4 6 7 8 9 10 12 17

A) 1

B) 7

C) 8

D) 9

E) 17

A) 6 4 8 3 7 9

If a bubble sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed?

A) 6 4 8 3 7 9

B) 6 8 4 9 3 7

C) 3 4 6 7 8 9

D) 3 6 4 9 8 7

E) None of the above

B) 3 6 4 9 8 7

If a selection sort is used to arrange the numbers 8 6 4 9 3 7 in ascending order, what order will the data be in after the first pass of the sort is completed?

A) 6 4 8 3 7 9

B) 3 6 4 9 8 7

C) 3 4 6 7 8 9

D) 6 8 4 9 3 7

E) None of the above