a. As in Java, make the four data types all subclasses of one superclass which implements something like Comparable, and then override the comparison operator for each subclass. Use the superclass as the component data type in the sort.
b. Use a template for the sort, then instantiate it with each of the four data type classes.
c. Put the sort method in a header file and use #include to bring it into four source files, one for each component type. Use #define to equate the data type name used in the sort code successively to each of the four types, before the #include, thus (for example):
#define DataType int
#define Less(a,b) (a)<(b)
#include "MySort.h"
#define SortInt MySort
2. [20] In each of the program snippets below, tell what value it (finally) puts into x:
a. add(2,times(3,5)) = add(2,3+5) = 2*3+5 = 11
#define add(a,b) a*b
#define times(a,b) a+b
int x = add(2,times(3,5));
b. sizeof(tricky)/sizeof(int)
= max(sizeof(i,j,*p,q,a))/4 = sizeof(a)/4 = 20*4/4 = 20
union tricky {
int i, j;
int * p, q;
int a[20]; };
int x = sizeof(tricky)/sizeof(int);
c. In this null-terminated string,
c[5] is that null (no range-checking), so x = 0
char * c = "13957";
int x = c[5];
d. b = c+1;
so b[2] = '5' and *c = '3' therefore
x = '5' - '3' = 2
char * c = "13957";
char * b = ++c;
int x = b[2] - *c++;
e. Both &b
and *a are aliases for x = 3; so
b = b-*a = 0, which is calculated after fetching b
and before b++ writes back 4, which is then replaced by
b = 0; therefore x = 0. Some C compilers might
write back b++ = 4 before fetching *a, which
would give a value of x = -1. Programs that depend on compiler
execution order like this are badly formed.
void rex(int * a, int & b) {b = (b++) - *a;}
...
int x = 3;
rex(&x,x);
3. [20] The following program failed to compile. Why? Fix it so
it compiles.
void whammy() {p is type int**, so p[3] is type int*, but q is type int** again. Fixed by deleting the excess *
int ix;
int ** p = (int**)malloc(sizeof(int*)*7);
*p = (int*)malloc(sizeof(int)*9);
for (ix=0; ix<5; ix++) p[ix+1] = p[ix];
**p = 4;
int ** q = p[3];
free(q); free(p);
}
b. What else is wrong with this program? Fix it.
There are two malloc() calls, but only
one matching free(); this is a memory leak. Fixed by adding
free(p);
4. [10] Give an analysis of the running time for the following algorithm:
sum = 0;Considering each nested structure individually, as shown, the net effect is O(N2logN)
for (i=1; i<n;i++) <-- O(N)
for (j=1; j<i*i; j++) <-- O(N2)
if (j%i == 0) <-- O(N1/2)
for (k=j; k>0; k>>=1) sum++; <-- O(logN)
5. [5] What is the purpose of a header in a linked list?
Without a header node, insertions and deletions
at the front of the list requires special-case code, which if there are
multiple pointers to this list may be incomplete. The header makes it possible
to use the same code for all insertions (and correspondingly, deletions),
regardless of where in the list they occur.
6. [15] What classes do you need to specify in an object-oriented list structure?
Obviously you need to define a class for the Node, consisting of the data contained in the node, plus a (forward) link and (if necessary) the backward link.
An important feature of OOPS is encapsulation (hiding), so you should enclose that Node class within a List class, and expose only the accessor methods.
Without direct access to list nodes, and the fact
that you may need several of them to do certain list-structuring operations
such as re-arranging nodes, means that you need some kind of state-preserving
class like an Iterator that is exposed.
Rev. 2003 October 9