NOTE: ONE HALF OF THE EXAM POINTS WILL COME FROM WRITING C++ FUNCTIONS. THE OTHER ONE HALF WILL BE FROM THE MULTIPLE CHOICE QUESTIONS
Be able to implement any of the functions from the Binary Search Tree assignments (#s 10 & 11).
You should assume that class Bnode contains pure virtual functions
operator<(), operator==() and show() and data items Left Child(LC)
and Right Child(RC). Further, the application using this BST derives
a class myData : public Bnode. class myData contains appropriate
code for the inherited virtual functions and a data item of type CString.
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
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:
14
/
\
2
11
/ \
/ \
1 3 10
30
/ /
7 40
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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a function to meet the following specification.
Check as much of the precondition as possible. No recursion is needed.
void subswap(BinaryTreeNode* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a recursive function to meet the following
specification. Check as much of the precondition as possible.
void flip(BinaryTreeNode* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a recursive function to meet the following
specification. You do not need to check the precondition.
void increase(BinaryTreeNode* 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 BinaryTreeNode definition:
template <class
Item>
struct BinaryTreeNode
{
Item data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a recursive function to meet the following
specification. You do not need to check the precondition.
template <class Item>
size_t many_nodes(BinaryTreeNode<Item>*
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 BinaryTreeNode definition:
template <class
Item>
struct BinaryTreeNode
{
Item data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a recursive function to meet the following
specification. You do not need to check the precondition.
template <class Item>
int tree_depth(BinaryTreeNode<Item>* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a function to meet the following specification.
You do not need to check the precondition.
size_t count42(BinaryTreeNode* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a function to meet the following specification.
You do not need to check the precondition.
bool has_42(BinaryTreeNode* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a function to meet the following specification.
You do not need to check the precondition.
bool all_42(BinaryTreeNode* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a recursive function to meet the following
specification. You do not need to check the precondition.
int sum_all(BinaryTreeNode* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *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(BinaryTreeNode* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *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(BinaryTreeNode* 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 BinaryTreeNode definition:
struct BinaryTreeNode
{
int data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
Write a function to meet the following specification.
You do not need to check the precondition.
void insert_one_42(BinaryTreeNode*& 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:
template <class
Item>
struct BinaryTreeNode
{
Item data;
BinaryTreeNode *left;
BinaryTreeNode *right;
};
BinaryTreeNode *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
20.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 print the tree in any of the following orders: in, pre, post.
Be able to write a function to do any of the following four 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").