CIS-3333 Test Information


1st Midterm -- 2003 October 9

1. [30] You have a large program to write, which needs a QuickSort that operates on each of four different data types. Describe three different  ways to code the sort program once in C++, using the same source code for all four data types.

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;

3. [20] The following program failed to compile. Why? Fix it so it compiles.

 void whammy() {
   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);
p is type int**, so p[3] is type int*, but q is type int** again. Fixed by deleting the excess *

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;
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)
Considering each nested structure individually, as shown, the net effect is O(N2logN)

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