Be able to implement any of the functions from the Binary Search Tree
assignments (#s 10 & 11).
You should assume that class Bnode contains data members Left Child(LC), Right
Child(RC) and int Data.
Chapter 9
- What is the importance of the stopping case in recursive functions?
- Write a recursive function that has one parameter which is a size_t value
called x. The function prints x asterisks, followed by x exclamation points.
Do NOT use any loops. Do NOT use any variables other than x.
- In a single function declaration, what is the maximum number of statements
that may be recursive calls?
A. 1
B. 2
C. n (where n is the
argument)
D. There is no fixed
maximum W
- What is the maximum depth of recursive calls a function may make?
A. 1
B. 2
C. n (where n is the
argument)
D. There is no fixed
maximum
- Consider the following function:
void super_write_vertical(int
number)
// Postcondition: The digits
of the number have been written,
// stacked vertically.
If number is negative, then a negative
// sign appears on top.
// Library facilities used:
iostream.h, math.h
{
if
(number < 0)
{
cout << '-' << endl;
super_write_vertical(abs(number));
}
else
if (number < 10)
cout << number << endl;
else
{
super_write_vertical(number/10);
cout << number % 10 << endl;
}
}
What values of number are directly handled by the
stopping case?
A. number < 0
B. number < 10
C. number >= 0 &&
number < 10
D. number > 10
- Consider the following function:
void super_write_vertical(int
number)
// Postcondition: The digits
of the number have been written,
// stacked vertically.
If number is negative, then a negative
// sign appears on top.
// Library facilities used:
iostream.h, math.h
{
if
(number < 0)
{
cout << '-' << endl;
super_write_vertical(abs(number));
}
else
if (number < 10)
cout << number << endl;
else
{
super_write_vertical(number/10);
cout << number % 10 << endl;
}
}
Which call will result in the most recursive calls?
A. super_write_vertical(-1023)
B. super_write_vertical(0)
C. super_write_vertical(100)
D. super_write_vertical(1023)
- Consider this function declaration:
void quiz(int i)
{
if
(i > 1)
{
quiz(i / 2);
quiz(i / 2);
}
cout
<< "*";
}
How many asterisks are printed by the function call
quiz(5)?
A. 3
B. 4
C. 7
D. 8
E. Some other number
- In a real computer, what will happen if you make a recursive call without
making the problem smaller?
A. The operating system
detects the infinite recursion because of the "repeated state"
B. The program keeps
running until you press Ctrl-C
C. The results are
nondeterministic
D. The run-time stack
overflows, halting the program
- When the compiler compiles your program, how is a recursive call treated
differently than a non-recursive function call?
A. Parameters are all
treated as reference arguments
B. Parameters are all
treated as value arguments
C. There is no duplication
of local variables
D. None of the above
- When a function call is executed, which information is not saved in the
activation record?
A. Current depth of
recursion.
B. Formal parameters.
C. Location where the
function should return when done.
D. Local variables.
- Consider the following function:
void test_a(int n)
{
cout <<
n << " ";
if (n>0)
test_a(n-2);
}
What is printed by the call test_a(4)?
A. 0 2 4
B. 0 2
C. 2 4
D. 4 2
E. 4 2 0
- Consider the following function:
void test_b(int n)
{
if (n>0)
test_b(n-2);
cout <<
n << " ";
}
What is printed by the call test_b(4)?
A. 0 2 4
B. 0 2
C. 2 4
D. 4 2
E. 4 2 0
- Suppose you are exploring a rectangular maze containing 10 rows and 20 columns.
What is the maximum depth of recursion that can result if you start at the
entrance and call traverse_maze?
A. 10
B. 20
C. 30
D. 200
- What is the relationship between the maximum depth of recursion for traverse_maze
and the length of an actual path found from the entrance to the tapestry?
A. The maximum depth
is always less than or equal to the path length.
B. The maximum depth
is always equal to the path length.
C. The maximum depth
is always greater than or equal to the path length.
D. None of the above
relationships are always true.
- What technique is often used to prove the correctness of a recursive function?
A. Communitivity.
B. Diagonalization.
C. Mathematical induction.
D. Matrix Multiplication.
Chapter 10
Here is a small binary tree:
6
/ \
2 11
/ \ / \
1 3 10 30
/ /
7 20
- Circle all the leaves. Put a square box around the root. Draw a star around
each ancestor of the node that contains 10. Put a big X through every
descendant of the node the contains 10.
- Draw a full binary tree with at least 6 nodes.
- Draw a complete binary tree with exactly six nodes. Put a different value
in each node. Then draw an array with six components and show where
each of the six node values would be placed in the array (using the usual
array representation of a complete binary tree).
- Write a new struct definition that could be used for a node in a tree where:
(1) Each node contains int data, (2) Each node has up to four children,
and (3) Each node also has a pointer to its parent. Store the pointers to
the children in an array of four pointers.
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a function to meet the following specification.
Check as much of the precondition as possible. No recursion is needed.
void subswap(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a non-empty binary tree.
// Postcondition: The original left subtree has been
moved and is now the right
// subtree, and the original right subtree is now
the left subtree.
// Example original tree:
Example new tree:
//
1
1
//
/ \
/ \
//
2 3
3 2
// / \
/ \
// 4
5
4 5
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a recursive function to meet the following
specification. Check as much of the precondition as possible.
void flip(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a non-empty binary tree.
// Postcondition: The tree is now the mirror image
of its original value.
// Example original tree:
Example new tree:
//
1
1
//
/ \
/ \
//
2 3
3 2
// / \
/ \
// 4
5
5 4
- Here is a small binary tree:
14
/ \
2
11
/ \ / \
1 3 10 30
/ /
7 40
Write the order of the nodes visited in:
A. An in-order traversal:
B. A pre-order traversal:
C. A post-order traversal:
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a recursive function to meet the following specification. You do not
need to check the precondition.
void increase(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a binary tree.
// Postcondition: Every node of the tree has had
its data increased by one.
- Consider this BNode definition:
struct BNode
{
CString
data;
BNode
*left;
BNode
*right;
};
Write a recursive function to meet the following specification. You do not
need to check the precondition.
size_t many_nodes(BNode * root_ptr)
// Precondition: root_ptr is the root pointer of
a binary tree.
// Postcondition: The return value is the number
of nodes in the tree.
// NOTES: The empty tree has 0 nodes, and a tree
with just a root has
// 1 node.
- Consider this BNode definition:
struct BNode
{
CString
data;
BNode
*left;
BNode
*right;
};
Write a recursive function to meet the following specification. You do not
need to check the precondition.
int tree_depth(BNode *root_ptr)
// Precondition: root_ptr is the root pointer of
a binary tree.
// Postcondition: The return value is the depth of
the binary tree.
// NOTES: The empty tree has a depth of -1 and a
tree with just a root
// has a depth of 0.
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a function to meet the following specification. You do not need to check
the precondition.
size_t count42(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a binary tree (but
// NOT NECESSARILY a search tree).
// Postcondition: The return value indicates how
many times 42 appears
// in the tree. NOTE: If the tree is empty, the function
returns zero.
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a function to meet the following specification. You do not need to check
the precondition.
bool has_42(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a binary tree (but
// NOT NECESSARILY a search tree).
// Postcondition: The return value indicates whether
42 appears somewhere
// in the tree. NOTE: If the tree is empty, the function
returns false.
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a function to meet the following specification. You do not need to check
the precondition.
bool all_42(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a binary tree (but
// NOT NECESSARILY a search tree).
// Postcondition: The return value is true if every
node in the tree
// contains 42. NOTE: If the tree is empty, the function
returns true.
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a recursive function to meet the following specification. You do not
need to check the precondition.
int sum_all(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a binary tree.
// Postcondition: The return value is the sum of
all the data in all the nodes.
// NOTES: The return value for the empty tree is
zero.
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a function to meet the following specification. You do not need to check
the precondition. Make the function as efficient
as possible (do not visit nodes unnecessarily):
size_t count42(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a binary SEARCH tree.
// Postcondition: The return value indicates how
many times 42 appears
// in the tree.
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a function to meet the following specification. You do not need to check
the precondition. Make the function as efficient
as possible (do not visit nodes unnecessarily):
int max(BNode* root_ptr)
// Precondition: root_ptr is the root pointer of
a nonempty binary SEARCH
// tree.
// Postcondition: The return value is the largest
value in the tree.
- Consider this BNode definition:
struct BNode
{
int
data;
BNode
*left;
BNode
*right;
};
Write a function to meet the following specification. You do not need to check
the precondition.
void insert_one_42(BNode*& root_ptr)
// Precondition: root_ptr is the root pointer of
a binary SEARCH tree.
// Postcondition: One copy of the number 42 has been
added to the binary
// search tree.
===============================================================
14
/ \
2 11
/ \ / \
1 3 10 30
/ /
7 40 |
- For the tree in the box at the top of this section. How many leaves does
it have?
A. 2
B. 4
C. 6
D. 8
E. 9
- For the tree in the box at the top of this section. How many of the nodes
have at least one sibling?
A. 5
B. 6
C. 7
D. 8
E. 9
- For the tree in the box at the top of this section. What is the value stored
in the parent node of the node containing 30?
A. 10
B. 11
C. 14
D. 40
E. None of the above
- For the tree in the box at the top of this section. How many descendants
does the root have?
A. 0
B. 2
C. 4
D. 8
- For the tree in the box at the top of this section. What is the depth of
the tree?
A. 2
B. 3
C. 4
D. 8
E. 9
- For thea tree in the box at the top of this section. How many children does
the root have?
A. 2
B. 4
C. 6
D. 8
E. 9
- Consider the binary tree in the box at the top of this section. Which statement
is correct?
A. The tree is neither
complete nor full.
B. The tree is complete
but not full.
C. The tree is full
but not complete.
D. The tree is both
full and complete.
- What is the minimum number of nodes in a full binary tree with depth 3?
A. 3
B. 4
C. 8
D. 11
E. 15
- What is the minimum number of nodes in a complete binary tree with depth
3?
A. 3
B. 4
C. 8
D. 11
E. 15
- Select the one true statement.
A. Every binary tree
is either complete or full.
B. Every complete binary
tree is also a full binary tree.
C. Every full binary
tree is also a complete binary tree.
D. No binary tree is
both complete and full.
- Suppose T is a binary tree with 14 nodes. What is the minimum possible depth
of T?
A. 0
B. 3
C. 4
D. 5
- Select the one FALSE statement about binary trees:
A. Every binary tree
has at least one node.
B. Every non-empty
tree has exactly one root node.
C. Every node has at
most two children.
D. Every non-root node
has exactly one parent.
- Consider these definitions:
struct BNode
{
CString
data;
BNode
*left;
BNode
*right;
};
BNode *t;
Which expression indicates that t represents an empty
tree?
A. (t == NULL)
B. (t->data == 0)
C. (t->data == NULL)
D. ((t->left == NULL)
&& (t->right == NULL))
- In how many places does a recursive call usually occur in the implementation
of the tree_clear function for a binary tree?
A. 0
B. 1
C. 2
- For the tree in the box at the top of this section. What is the order of
nodes visited using
a pre-order traversal?
A. 1 2 3 7 10 11 14
30 40
B. 1 2 3 14 7 10 11
40 30
C. 1 3 2 7 10 40 30
11 14
D. 14 2 1 3 11 10 7
30 40
- For the tree in the box at the top of this section. What is the order of
nodes visited using
an in-order traversal?
A. 1 2 3 7 10 11 14
30 40
B. 1 2 3 14 7 10 11
40 30
C. 1 3 2 7 10 40 30
11 14
D. 14 2 1 3 11 10 7
30 40
- For the tree in the box at the top of this section. What is the order of
nodes visited using a post-order traversal?
A. 1 2 3 7 10 11 14
30 40
B. 1 2 3 14 7 10 11
40 30
C. 1 3 2 7 10 40 30
11 14
D. 14 2 1 3 11 10 7
30 40
Consider this binary search tree:
14
/ \
2
16
/ \
1 5
/
4
- Suppose we remove the root, replacing it with something from the left subtree.
What will be the new root?
A. 1
B. 2
C. 4
D. 5
E. 16
- Given the following sequence if Insert()'s into an empty BST, draw their
resulting tree (include the root pointer).
BST tree;
tree.Insert(10);
tree.Insert(12);
tree.Insert(5);
tree.Insert(10);
tree.Insert(7);
tree.Insert(11);
tree.Insert(15);
- Using the above tree, perform the following sequence of Delete()'s
tree.Delete(5); //Draw the resulting
tree-
tree.Delete(10); //Draw the resulting
tree-
tree.Delete(12); //Draw the resulting
tree-
- Given a BST, indicate which nodes must be visited if a Find(15) were to
be executed.
- Given a picture of a binary tree, be able to write the nodes of the tree
in any of the following orders: in, pre, post and level.
- Be able to write a function to do any of the following three traversals:
in-order, pre-order, post-order.
- Describe how a Stack can be used to aid in an in-order traversal.
- What is the Big-O for the following operations when issued on a BST: Insert,
Find, Delete, In-order Traversal (assume that the tree is "balanced").