- When doing object-oriented programming, you typically find
that functions have one less parameter than do corresponding
functions that are used in procedural (non-object-oriented) computing.
For example, a classical function to test whether a value x is present
in a tree t has two parameters, x and t, but an
object-oriented function has only one parameter, x.
Explain why there is one less parameter.
In object-oriented programming, each function is part of an
object. The function can refer to the object in which it
resides implicitly, so that object is not an explicit parameter.
It is an implicit parameter.
- What is the purpose of a destructor for a class?
What is the destructor for class River called? Under what circumstances
is the destructor called?
A destructor recovers resources owned by an object. Typically,
it deletes memory that the object owns, but that is physically
outside the object.
The destructor for class River is called ~River.
The destructor is called any time an object is destroyed,
for any reason.
- Does using classes and object-oriented programming usually
make programs shorter than they would be using traditional methods?
No. Using object-oriented programming typically makes programs
larger and less efficient than if they had been designed by other
means. But that is compensated for because the programs are
better organized, easier to understand and easier to modify.
- Object-oriented programming in C++ can be used to
make it impossible to violate the abstraction of an
abstract data type.
- What feature of C++ makes this possible?
The class, and private members of classes.
- Programmers rarely deliberately sabotage their own work.
Since programmers are not supposed to violate
abstractions, why is it so important that a compiler
prevent them from doing so? Can't programmers police themselves?
Even good programmers make mistakes, and the compiler should
catch those mistakes wherever possible.
Programming teams often have some less experienced programmers
who are likely to violate abstractions if permitted to do so.
A compiler that disallows such violations gives the better
programmers confidence that the less experienced programmers
are not violating abstractions.
- Suppose that structure Polynomial
is defined as follows.
struct Polynomial {
int degree;
double* coef;
Polynomial(int n)
{
degree = n;
coef = new double[d+1];
}
};
Which of the following will create a polynomial with
degree 5?
- Polynomial P(5);
- Polynomial(5) P;
- Polynomial P; Polynomial(5);
- Polynomial P; P(5);
- Suppose that structure Polynomial and variable P are defined
as in the preceding problem.
Which of the following will set the coefficient of P at index 1
to hold 3.5?
- P[1].coef = 3.5;
- P.coef[1] = 3.5;
- P.(*coef)[1] = 3.5;
- (*P).coef[1] = 3.5;
- Suppose that you insert 25 into the following tree using
the algorithm that does rotations to keep the tree height-balanced.
What is the resulting tree?
81
/ \
20 100
/ \
16 65
81 65
/ \ / \
20 100 20 81
/ \ / \ \
16 65 16 25 100
/
25
before rotations after rotations
The answer is the tree on the right. It is obtained from the
tree on the left by doing a double rotation at the root.
- Consider the following tree with integer keys.
25
/ \
10 30
/ \
26 50
- Is this tree a binary search tree? That is, does it obey
the ordering requirements?
Yes.
- Ignoring the keys, is this tree height-balanced?
Yes.
- If you were to use the standard (unbalanced) binary search tree
insertion algorithm, show what this tree would look like after
inserting 40.
25
/ \
10 30
/ \
26 50
/
40
- Is the tree height-balanced after inserting 40, without
rebalancing?
No.
- Suppose that you use the connection manager discussed in
class to manage connections in a graph. Show how the pseudo-representative
array (called Rep here) changes as each of the following operations are
done.
Use the algorithm that does not do either of the improvements -- the
basic algorithm.
In the diagram, the connect function is abbreviated c. So, for
example c(2,4) indicates that we connect 2 and 4.
I presume that connect(A,B) tries to make A' point to B', rather
than making B' point to A', where A' is the representative of A
and B' is the representative of B.
i Rep[i] i Rep[i] i Rep[i] i Rep[i]
1 1 1 _5__ 1 _5__ 1 _5__
2 2 2 _2__ 2 _2__ 2 _4__
c(1,5) c(5,2) c(5,4)
3 3 --------> 3 _3__ --------> 3 _3__ --------> 3 _3__
4 4 4 _4__ 4 _4__ 4 _4__
5 5 5 _5__ 5 _2__ 5 _2__
- Using the type Node shown, write a
function called PrintEvens that prints the even numbers
in a binary search tree in
descending order, one number per line, skipping the odd numbers
in the tree. (n is even if n%2 == 0.)
For example, if t is the tree shown in problem 5, then
PrintEvens(t) would print the numbers 100, 20 and 16, one
per line, in that order.
The function should not destroy the tree.
struct Node {
int key;
Node* left;
Node* right;
Node(Node* l, int k, Node* r)
{
left = l;
key = k;
right = r;
}
};
void PrintEvens(Node* T)
{
if(T != NULL) {
PrintEvens(T->right);
if(T->key % 2 == 0) cout << T->key << endl;
PrintEvens(T->left);
}
}
- The binary search tree implementation that was discussed
in class was nonpersistent; the insert operation, for example,
changed the tree. It is possible to implement binary search trees
in a persistent way also, so that they compute new trees
from old ones.
Using the type Node of the previous problem,
write a function removeMin(t) that returns the
tree that would result from removing the smallest value from tree t, but
that does not alter tree t. If t is empty, then
removeMin(t) should return an empty tree. For example, if
t is the tree
81
/ \
20 100
\
65
/ \
50 70
then removeMin(t) should
return the following tree, without altering tree t.
81
/ \
65 100
/ \
50 70
Do not rebalance the tree.
The new tree that you construct can share
subtrees with t, as long as it does not change the subtrees.
Node* removeMin(Node* t)
{
if(t == NULL) return NULL;
else if(t->left == NULL) return t->right;
else return new Node(removeMin(t->left), t->key, t->right);
}