FINAL REVIEW
1)
int z(int k, int n)
{
if (n == k)
return k;
else
{
if (n > k)
return z(k, n-k);
else return z(k-n, n);
}
}
Based on the function defined above, what is the value
of z(6,8)? 2
2)
In the following recursive
function, which line(s) represent the base case? Which line(s) represent the general
(recursive) case?
void PrintIt(int
n ) //
Line 1
{ // Line 2
if (n == 0) // Line 3
cout
<< n << endl; //
Line 4
else // Line 5
{ // Line 6
cout << "Again"
<< endl;
// Line 7
PrintIt(n
- 1); // Line 8
}
}
Base case: 3-4
Recursive case: 7-8
3)
Given the
recursive function
void
PrintArr(const int arr[],
int first,
int last )
{
if
(first > last)
cout << "Done";
else
{
PrintArr(arr,
first + 1, last);
cout << arr[first];
}
}
which
code segment below produces the same output as the following function call?
PrintArr(arr, 0, 5);
A) for (i = 0; i < 6; i++)
cout << arr[i];
cout << "Done";
B) cout
<< "Done";
for (i = 0; i
< 6; i++)
cout << arr[i];
C) for (i = 0; i < 6; i++)
{
cout << arr[i];
cout << "Done";
D) for (i = 5; i >= 0; i--)
cout << arr[i];
cout << "Done";
E) cout << "Done";
for (i
= 5; i >= 0; i--)
cout
<< arr[i];
4)
The following questions
are based on this tree. The letters are labels, not values.
a) Which traversal generates the order: D G B H E I A C F ? inorder
b) Which node is the inorder predecessor of E? H
c) How would the tree look if we wished to delete node C?
A would point to F
d) If we inserted a node into this tree whose value was
smaller than any existing value in the tree, where would the node be placed? as a left child of D
5)
Examine the
following binary tree where the values in the nodes are shown.
a) Is this a binary search tree? NO
b) What is the advantage of using binary search trees
instead of lists? Searching is much faster, as the
number of comparisons depends on the depth of the tree instead of the length of
the list
6)
Given the
following array, Data:
|
12 |
1 |
9 |
23 |
17 |
11 |
a)
What is the state
of the array when Data[0]..Data[2] is sorted using the selection sort? 1 9 11 23 17 12
b)
What is the state
of the array when Data[0]..Data[2] is sorted using the insertion sort? 1 9 12 23 17 11
c)
What is the state of the array when Data[0]..Data[2] is sorted using the bubble sort? 1 9 11 12 17 23
7) Trace the following code. You may refer to the header files of stacks queues and trees. Show a picture of the stack, queue and tree at each iteration of the loop.
Input is: 0 5 2 1
QueType<int> Q;
StackType S;
TreeType T;
int
input;
for (int i = 0; i
<= 3; i++)
{
cin
>> input;
S.Push(input);
Q.Enqueue(input);
T.InsertItem(input);
if (input
< 4)
{
S.Push(input + 15);
Q.Dequeue(input);
}
else
{
Q.Enqueue(input+25);
T.InsertItem(input - 2);
}
}
|
i |
stack |
queue |
binary searchtree |
|
0 |
15 0 |
|
|
|
1 |
5 15 0 |
5 30 |
|
|
2 |
17 2 5 15 0 |
30 2 |
|
|
3 |
16 1 17 2 5 15 0 |
2 1 |
|
