| Question | Mark |
| 1. Arrays of structs [10 marks] | |
| 2. Command line arguments and file i/o [10 marks] | |
| 3. Searching and sorting [10 marks] | |
| 4. Pointers and dynamic allocation [10 marks] | |
| Exam Total [40 marks] |
Question 1: Arrays of structs [10]
Given the struct and array definitions below, and assuming the fill function has already been implemented and works correctly and appropriate libraries included/namespaces used, provide an implementation for the findHottest function, ensuring that its behaviour matches the description given.
struct City {
string name;
float temperature;
};
// fills the array with the data for N cities
void fill(City arr[], int N);
// returns the name of the city with the highest temperature
// (in the event of ties it returns the first city with that highest temperature,
// returns "" if N < 1)
string findHottest(City arr[], int N);
int main()
{
int size = 5;
City* data = new City[size];
fill(data, size);
string hottest = findHottest(data, size);
cout << "The hottest city is " << hottest << endl;
delete [] data;
}
|
Sample solution
string findHottest(City arr[], int N)
{
// error check for no data available
if (N < 1) {
return "";
}
// track hottest so far (array position and temperature)
// starting with whatever is in the first position
int hotpos = 0;
float hottemp = arr[hotpos].temperature;
// check against each subsequent city
for (int c = 1; c < N; c++) {
if (arr[c].temperature > hottemp) {
hotpos = c;
hottemp = arr[hotpos].temperature;
}
}
// return name of hottest city
return arr[hotpos].name;
}
|
Question 2: Command line arguments and file i/o [10]
Write a main routine that correctly uses argc and argv to accept a filename as a command line argument, opens the file for reading, and reads the file contents one word at a time until end-of-file, skipping whitespace and displaying the words on screen as it goes. (Any block of non-whitespace characters can be treated as a word, it doesn't need to check for valid dictionary-style words.)
Sample solution
int main(int argc, char* argv[])
{
// make sure they did actually provide a command line argument
if (argc < 2) {
cerr << "Error: expected filename as command line argument" << endl;
return 0;
}
// open the file, quit if it fails
ifstream inf;
inf.open(argv[1]);
if (!inf.is_open()) {
cerr << "Error: could not open " << argv[1] << endl;
return 0;
}
// read/display words until end of file
do {
string w;
inf >> w;
if (!inf.eof()) {
cout << w; // note that this does not print any whitespace in between words in the output,
// you probably want to add spaces or newlines in between
}
} while (!inf.eof());
// close and exit
inf.close();
return 0;
}
|
Question 3: Searching and sorting [10]
(i) Briefly explain the purpose of the partition function in quicksort and how the choice of a pivot is typically considered to be 'good' or 'bad'.
(ii) Add comments to the partitioning routine below to explain the purpose of each of the loops. (It's based on our lab2, where ItemRank has fields for an item's name and its rank.)
int partition(ItemRank rankings[], int low, int high)
{
if (low >= high) {
return low;
} else if (low < 0) {
low = 0;
}
int pivotRank = rankings[low].rank;
int lowpos = low+1;
int highpos = high;
do {
while ((lowpos < highpos) && (rankings[lowpos].rank <= pivotRank)) {
lowpos++;
}
while ((highpos > lowpos) && (rankings[highpos].rank >= pivotRank)) {
highpos--;
}
if (lowpos < highpos) {
swap(rankings[lowpos], rankings[highpos]);
lowpos++;
highpos--;
}
} while (lowpos < highpos);
int pivotPos = highpos;
if (pivotRank <= rankings[pivotPos].rank) {
pivotPos--;
}
if (low != pivotPos) {
swap(rankings[low], rankings[pivotPos]);
}
return pivotPos;
}
|
Sample solution
(i) Partition takes the specified array segment (positions low through high) and rearranges them
into higher and lower values, based on some chosen 'pivot' value that winds up at the border
between the higher and lower values. (This allows the recursive quicksort routine to keep
rearranging smaller and smaller array segments until the results are eventually fully sorted.)
A good pivot winds up closer to the middle of the array segment after partitioning,
reducing the number of recursive quicksort calls and hence the overall runtime,
while a poor pivot winds up closer to one end of the array segment,
leading to a maximal number of layers of recursion.
(The differences in pivot choices can cause the overall behaviour to range from
being proportional to N^2 to being proportional to N log(N), for an N-element array.)
(ii) comments added to the loops below (you didn't need to recopy, just write directly onto the code above)
int partition(ItemRank rankings[], int low, int high)
{
if (low >= high) {
return low;
} else if (low < 0) {
low = 0;
}
int pivotRank = rankings[low].rank;
int lowpos = low+1;
int highpos = high;
// the outer do-while loop keeps the partitioning cycle going until low and high
// have met in the middle of the array somewhere, where the pivot will belong
do {
// the first loop moves 'right' from the low position, looking for the first value
// on the wrong side of the pivot (i.e. < pivot)
// (or stopping if low/high have met somewhere in the middle)
while ((lowpos < highpos) && (rankings[lowpos].rank <= pivotRank)) {
lowpos++;
}
// the second loop moves 'left' from the high position, looking for the first value
// on the wrong side of the pivot (i.e. > pivot)
// (or stopping if low/high have met somewhere in the middle)
while ((highpos > lowpos) && (rankings[highpos].rank >= pivotRank)) {
highpos--;
}
// once the two loops have completed, if low/high haven't met/crossed,
// lowpos and highpos represent two values on opposing wrong sides of the pivot,
// so we can fix both by swapping them
if (lowpos < highpos) {
swap(rankings[lowpos], rankings[highpos]);
lowpos++;
highpos--;
}
} while (lowpos < highpos);
int pivotPos = highpos;
if (pivotRank <= rankings[pivotPos].rank) {
pivotPos--;
}
if (low != pivotPos) {
swap(rankings[low], rankings[pivotPos]);
}
return pivotPos;
}
|
Question 4: Pointers and dynamic allocation [10]
(i) Briefly explain the purpose of the & and * symbols in each place they are used in the program below.
(ii) As precisely as possible, show the output from the program below assuming the user types in 10 and 5.6 as the input for the two cin's.
(iii) The main routine currently does not explicitly deallocate the dynamically allocated memory, provide the command that would be needed to do so and show where in the main routine that command would belong.
#include <iostream>
using namespace std;
struct stuff {
int i;
float f;
};
void dostuff(stuff* s)
{
cout << (*s).i << endl;
cout << s->f << endl;
}
void otherstuff(stuff &s)
{
cout << "Enter an integer then a real number" << endl;
cin >> s.i;
cin >> s.f;
}
int main()
{
stuff mystuff;
otherstuff(mystuff);
dostuff(&mystuff);
stuff *stuffptr = new stuff;
*stuffptr = mystuff;
dostuff(stuffptr);
}
|
Sample solution
(i) and (iii) are answered in the modified code segment below
(ii) The output from the run will look like
Enter an integer then a real number
10 << these two lines are just showing what the user is typing as input
5.6
10 << these two lines are from the first call to dostuff, with mystuff's data
5.6
10 << these two lines are from the second call to dostuff, with the new item's data
5.6
#include <iostream>
using namespace std;
struct stuff {
int i;
float f;
};
// dostuff expects to be passed a pointer to a struct (the address of it)
void dostuff(stuff* s)
{
// the (*s) dereferences s, i.e. gets the actual struct pointed to by s
// so the .i correctly looks up the int field
cout << (*s).i << endl;
cout << s->f << endl; // the -> syntax is an alias for the * . syntax
}
// here the &s means s is passed by reference, i.e. otherstuff can alter the struct content
void otherstuff(stuff &s)
{
cout << "Enter an integer then a real number" << endl;
cin >> s.i;
cin >> s.f;
}
int main()
{
stuff mystuff;
otherstuff(mystuff);
// &mystuff passes the address of mystuff, essentially a pointer to mystuff
dostuff(&mystuff);
// stuffptr is a pointer for stuff items,
// new stuff returns a pointer to a newly allocated item,
// and we're storing that in stuffptr
stuff *stuffptr = new stuff;
// *stuffptr refers to the actual struct that stuffptr points to
// so this copies the two data fields of mystuff into the two data fields of the
// newly allocated item (so now we have two different structs with matching data)
*stuffptr = mystuff;
dostuff(stuffptr);
delete stuff; // **part (iii) answer**
}
|