- Searching/sorting:
One of the sorting algorithms we considered was mergesort,
in which we recursively sorted two halves of an array then used
a merge routine to combine the results:
mergesort(float arr[], int lowPosition, int highPosition)
if lowPosition < highPosition
midpt = (lowPosition + highPosition) / 2
mergesort(arr, lowPosition, midpt)
mergesort(arr, midpt+1, highPosition)
merge(arr, lowPosition, midpt, highPosition)
This assumes the availability of a suitable merge routine,
for which we proposed the following:
merge(float arr[], int low, int mid, int high)
numElements = (high + 1) - low
allocate temp[numElements]
pos = 0
pos1 = low
pos2 = mid
while pos1 <= mid AND pos2 <= high
if arr[pos1] < arr[pos2]
temp[pos] = arr[pos1]
pos1++
else
temp[pos] = arr[pos2]
pos2++
pos1++
temp[pos] = min(arr[pos1], arr[pos2])
copy temp contents back into arr
deallocate temp
This left out the details of how to copy temp back into the correct
spots in the array.
Write a short code segment to carry out the copy step.
- Linked lists:
Suppose we have a struct-based linked list using the two following structs:
- for the individual nodes in the list:
struct node {
int data1, data2, data3;
node *next;
node *prev;
};
- for the list overall:
struct list {
node* front;
node* back;
node* recent; // used to keep track of the most recently "used" node
};
Assuming the list is unsorted, implement the search function described below:
// searching from front to back,
// find the first element of L whose data1, data2, or data3 value equals d
// and set L's recent to point to that node (set to NULL if no match exists)
void search(list L, int d)
- Binary search trees:
(i) Suppose we have a binary search tree that permits duplicate keys,
with values <= the current key going into the left subtree and larger values
going into the right subtree.
Sketch the tree structure after we insert values into a (previously empty)
tree in the following order: 120 (root), 203, 187, 93, 104, 600, 1, 120
(ii) We considered inorder tree traversals (current node in the middle,
like print), postorder traversals (current node last, like deallocate),
and preorder traversals (current node first).
Suppose we wish to double the values in every node of the tree,
but maintain a valid binary search tree structure as we did so.
A viable approach would be:
doubleVals(node* treenode)
if treenode isn't null
call doubleVals on treenode's left subtree
double treenode's key
call doubleVals on treenode's right subtree
Show the order in which the key values would actually change
if we were to run doubleVals on the tree from part (i)
(i.e. call doubleVals on the tree's root node).
- Constructors/operators:
Suppose we have a class whose data fields include a dynamically allocated
character array e.g.
class Practice {
protected:
char* array;
int arrSize;
public:
Practice(int size = 0); // initializes arr as an array of the given size
~Practice(); // deallocates the array
Practice(char text[]); //initializes arr as a copy of text
// various public methods
};
(i) Provide a copy constructor for the class (carrying out a suitable deep copy).
(ii) Provide an overload of the << operator to display the array content
(Reminder: for character arrays things like cout << arrayname works fine as long as
the array isn't null.)
- Inheritance:
Suppose we have a new class, derived from Practice above,
in which we create a second array of the same size.
class Organized: public Practice {
protected:
char* sortedArr;
public:
Organized(int sz = 0): Practice(size);
Organized(char text[]): Practice(text);
~Organized();
// various public methods
};
The sortedArr in the new class contains the same values as the
original array, but with the contents rearranged in sorted (ascending) order.
(i) Describe what (if any) additional actions the two Organized constructors would need to
take to ensure the array, sortedArr, and arrSize fields were correctly initialized.
(ii) Describe what actions (if any) the ~Organized destructor would need to take
to ensure both arrays were correctly deallocated.
- Polymorphism/dynamic binding:
Suppose we want Practice and Organized to each provide their own print method,
and we want calls to print to be dynamically bound.
For each of the two classes, provide a definition of the print method
(i.e. what the print definition would look like within the class definition)
and an implementation of the method. (The Practice version should print the size
and the array content, the Organized version should print the size and then
each array's content.)
- Standard template library:
One of the supported STL classes is queue, e.g. we can create a queue of
doubles using syntax like
queue<double> myQ;
Some of the key queue methods include:
- size() // returns the number of elements in the queue
- front() // returns a copy of the front element
- pop_front() // removes and discards the front element
- push_back(v) // inserts the value at the back of the queue
Suppose our main routine declared myQ as shown above,
then inserted a series of user-supplied numbers into myQ.
Write a code segment that declares a second queue, posQ,
and goes through myQ one element at a time, removing values from
myQ, putting the removed value into posQ if it is greater
than zero and putting it back (at the end) of myQ otherwise.
- Exceptions:
For the try/catch code segment shown below:
- provide a user input value that would not result in any exceptions being thrown,
and show the complete output that would result from this test case
- provide a user input value that would result in an exception being caught by
the first catch and show the complete output that would result from this test case
- provide a user input value that would result in an exception being caught by
the last catch, show the complete output that would result from this test case,
and describe why that catch wouldn't be caught by any other catches
class myE {
public:
int eval;
myE(int e = 0) { eVal = e; }
};
try {
char userval;
string s = "unknown";
cout << "Enter a character" << endl;
cin >> userval;
if (userval == 's') {
throw s;
}
if (userval == 'i') {
throw myE(5);
}
cout << "you entered " << userval << endl;
if (userval == 'f') {
throw exception();
}
if (userval == 'x') {
throw 42;
}
}
catch (int e) {
cout << "type 1 exception: " << e << endl;
}
catch (myE& e) {
cout << "type 2 exception: " << e.eVal << endl;
}
catch (exception& e) {
cout << "type 3 exception" << endl;
}
catch (string e) {
cout << "type 4 exception: " << e << endl;
}