Deck 19: Binary Trees

Question 1

Every node in a binary tree has at most ____ children.

A) one
B) two
C) three
D) four

Answer 1

B

Question 2

To delete an item from the binary search tree,you must do the following:
1.Find the node containing the item (if any)to be deleted.
2.Delete the node.

Answer 2

True

Question 3

A binary tree has a special node called the ____ node.

A) super
B) root
C) superparent
D) rootleaf

Answer 3

B

Question 4

A pointer to the root node of the binary tree is stored outside the binary tree in a pointer variable,usually called the ____.

A) node
B) parent
C) root
D) nodeType

Question 5

In a diagram of a binary tree,each node is represented as a(n)____.

A) line
B) triangle
C) circle
D) rectangle

Question 6

In C++,a function name without any parentheses is considered a pointer to the function.

Question 7

After deleting the desired item from a binary search tree,the resulting tree must be a binary search tree.

Question 8

In the diagram of a binary tree,an arrow is called a(n)____.

A) relation
B) path
C) directed line
D) directed branch

Question 9

The level of the root node of a binary tree is 1.

Question 10

Three lines at the end of an arrow in the diagram of a binary tree indicate that the subtree ____.

A) has three branches
B) has three children
C) is full
D) is empty

Question 11

All binary tree traversals start at the left-most child node.

Question 12

The operations to do inorder,preorder,and postorder traversals of a binary search tree are the same as those for a binary tree.

Question 13

A node in a binary tree is called a(n)____ if it has no left and right children.

A) edge
B) branch
C) leaf
D) path

Question 14

Duplicates are allowed in a binary search tree.

Question 15

For classes with pointer data members,you must explicitly overload the assignment operator and include the destructor.

Question 16

Consider that A is a binary tree,C and D are the subtrees of A.Which of the following statements is always true?

A) C and D are binary trees.
B) C and D are search binary trees.
C) C and D are empty trees.
D) A is empty.

Question 17

The item search,insertion,and deletion operations all require the binary tree to be traversed.

Question 18

Each link in a binary tree node points to a(n)____ of that node.

A) parent
B) child
C) value
D) sibling

Question 19

Every node in a binary tree has ____ pointers.

A) one
B) two
C) three
D) four

Question 20

In a binary tree,the branches go only from a child to a parent.

Question 21

When traversing a binary tree with the pointer current,the pointer current is initialized to ____.

A) NULL
B) llink
C) rlink
D) root

Question 22

The ____________________ of a path in a binary tree is the number of branches on that path.

Question 23

The sequence of operations in a postorder traversal is ____.

A) traverse left; traverse right
B) traverse left; traverse right; visit
C) visit; traverse left; traverse right
D) traverse left; visit; traverse right

Question 24

In copying a binary tree,if you use just the value of the pointer of the root node,you get a ____ copy of the data.

A) static
B) shallow
C) deep
D) local

Question 25

The listing of the nodes produced by the postorder traversal of a binary tree is called the ____.

A) postsequence
B) postorder sequence
C) postorder table
D) post-script

Question 26

The key of the right child below the root node of a search binary tree is 40.The value in the root node could be ____.

A) 30
B) 40
C) 50
D) 60

Question 27

In a binary search tree,the data in each node is ____ the data in the left child.

A) larger than
B) smaller than
C) equal to
D) larger or equal to

Question 28

A binary tree is empty if root is ____.

A) 0
B) 1
C) "zero"
D) NULL

Question 29

The three traversal algorithms discussed for binary trees are ____,____,and ____.

A) order, preorder, postorder
B) in, preorder, order
C) order, preorder, post
D) inorder, preorder, postorder

Question 30

A binary tree is also a(n)____.

A) stack
B) linked list
C) graph
D) array

Question 31

In a binary search tree,the data in each node is ____ the data in the right child.

A) equal to
B) smaller than
C) greater than
D) smaller or equal to

Question 32

The ____ of a node in a binary tree is the number of branches on the path from the root to the node.

A) height
B) level
C) width
D) size

Question 33

In a(n)____________________ traversal,the binary tree is traversed as follows:
1.Traverse the left subtree
2.Visit the node
3.Traverse the right subtree

Question 34

The listing of the nodes produced by the preorder traversal of a binary tree is called the ____________________.

Question 35

The most common operation performed on a binary tree is a(n)____.

A) insertion
B) deletion
C) search
D) traversal

Question 36

In a(n)____________________ traversal,the binary tree is traversed as follows:
1. Visit the node.
2.Traverse the left subtree.
3.Traverse the right subtree.

Question 37

In a binary tree,the level of the children of the root node is ____.

A) 0
B) 1
C) 2
D) 3

Question 38

The search function searches the binary search tree for a given item.If the item is found in the binary search tree,it returns ____.

A) true
B) false
C) a reference to the node where the item was found
D) 1

Question 39

The ____________________ of a binary tree is the number of nodes on the longest path from the root to a leaf.

Question 40

Assume the key of the left child below the root node of a binary search tree is 30.The value in the root node could be ____.

A) 0
B) 10
C) 30
D) 40

Question 41

When a class object is passed by value,the ____________________ constructor copies the value of the actual parameters into the formal parameters.

Question 42

Let T be a binary search tree with n nodes,in which n > 0.When T is linear,the search algorithm makes ____________________ key comparisons,in the unsuccessful case.

Question 43

The listing of the nodes produced by the inorder traversal of a binary tree is called the ____________________.

Question 44

Let T be a binary search tree with n nodes,in which n > 0.The average number of nodes visited in a search of T is approximately O(____________________).

Question 45

To destroy a binary tree,for each node,first we destroy its left subtree,then its right subtree,and then the node itself.We must then use the operator ____________________ to deallocate the memory occupied by the node.

Question 46

Let T be a binary search tree with n nodes,in which n > 0.The number of key comparisons is approximately O(____________________).

Question 47

After inserting an item in a binary search tree,the resulting binary tree must be a(n)____________________.

Question 48

In addition to the inorder,preorder,and postorder traversals,a binary tree can also be traversed level-by-level,which is also known as ____________________ traversal.

Question 49

1.current = root;
2.while (current is not NULL or stack is nonempty)
if (current is not NULL)
{
visit current node;
push current onto stack;
current = current->lLink;
}
else
{
current = stack.top();
pop stack;
current = current->rLink; //move to the right child
}

Question 50

The algorithm below describes the nonrecursive ____________________ traversal of a binary tree.
1.current = root;
2.while (current is not NULL or stack is nonempty)
if (current is not NULL)
{
push current onto stack;
current = current->lLink;
}
else
{
current = stack.top();
pop stack;
visit current; //visit the node
current = current->rLink;//move to right child
}