C++ Week 22

Sample end-of-term tests

Test 1

Question 1

Write the output of the following main function. The boolalpha iostream manipulator makes the output of any subsequent boolean values appear as the words "true" or "false"; it does not itself produce any output. Write a few words of explanation for your answers for C to G.

int main( )
{	cout << boolalpha;
	cout << "A " << (0 < 1) << endl;
	cout << "B " << ('0' < '1') << endl;
	cout << "C " << ('0' < 1) << endl;
	cout << "D " << ('0' < '1' - '0') << endl;
	cout << "E " << ('0' < static_cast<char>(1)) << endl;
	cout << "F " << (string("0") < string("1")) << endl;
	cout << "G " << (static_cast<int>('0') < 1) << endl;
}

Question 2

If the following line were included in the above program, then, when run on the departmental Unix, it would output "true"

	cout << ("0" < "1") << endl;
but the following line also outputs "true":
	cout << ("1" < "0") << endl;

Why do you think this is? (Hint: think about parameter-passing.)

Question 3

Write down the output of this program fragment:

int f(int& x)
{	return ++x;
}

int main( )
{	vector<int>  v(4);
	for (int i = 1; i < v.size(); i++)
		v[i] = f(v[i-1]) + 2;
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << " ";
	cout << endl;
}

Question 4

Write down the output of this program fragment:

void f(int x, int y)
{	if (x <= 1 || y <= 1)
		cout << "* ";
	else
	{	cout << x << " " << y << " ";
		if (x < y)
		      f(x, y/x);
		else  f(x/y, y);
		cout << y << " " << x << " ";
	}
}

int main( )
{	f(24, 3);
}

Question 5

Write a program that reads a text file and, at the end, outputs the number of "words" that consisted entirely of strings of the same character. A word, for the purposes of this question, is just a string of non-space characters, so strings such as "2345", "Why?" "BBC", "e.g.", "??!!" all count as words. The following would count as words consisting entirely of the same character – "a", "ZZZZ", "???", "...", "********". You may read the file from standard input or by opening an ifstream, as you wish. Your program should read the file only once.

Question 6

Write a procedure that takes an integer as its parameter and which outputs a Christmas tree (well, a triangle of asterisks). If given the number 6, it would output the following (there are 11 stars in the bottom line):
     *
    ***
   *****
  *******
 *********
***********

If given a value below 1 or above 40, it does nothing.

Question 7

A researcher is trying to get a computer to read handwriting. Some lower-case letters, such as 'h' and 'k', have "ascenders", i.e. lines that stick up above the general height of the other letters, while others, such as 'g' and 'p', have "descenders"; many, such as 'a', 'c' and 's', have neither (no letter has both). He has the idea of recognizing a word by its overall pattern of ascenders and descenders. Write a procedure which takes a string as its parameter – you may assume that the string contains a single word entirely in lower-case – and writes out three lines showing the positions of the ascenders and descenders. For example, for "holly" it would produce the following:

| || 
|||||
    |
while it would produce the following for "plumpudding":
 |    ||   
|||||||||||
|   |     |
You may assume that the following array has been defined as a global:
const int ad[ ] = {0,1,0,1,0,1,-1,1,0,-1,1,1,0,0,0,-1,-1,0,0,1,0,0,0,0,-1,0};
The first element, set to 0, indicates that 'a' has neither ascender nor descender; the second element, set to 1, indicates that 'b' has an ascender. The third element is for 'c', the fourth for 'd', and so on. -1 indicates that the letter has a descender. You may also assume that you are able to call a function ctoi() which takes a char as its parameter and which, if the letter is lower-case, returns an int between 0 (for 'a') and 25 (for 'z').

Question 8

Write a function that takes a string containing a Christmas-present list, e.g. "Scooter CD Playstation Gloves Woolly_hat", and which returns a pointer to the head of a singly-linked list of nodes, each node containing a single item. The items in the original list are separated by spaces and any embedded spaces are represented by underscores (as in "Woolly_hat").

Question 9

The following shows parts of the class definitions for a Phone class and a Phonebook class that, together, store the staff telephone numbers.

class Phonebook;

class Phone
{ public:
	Phone(string nm, int nmb) : name(nm), number(nmb), l(NULL), r(NULL) {}
	string	name;
	int	number;
	Phone* l, *r;
  friend ostream& operator<<(ostream&, const Phone&);
};

class Phonebook
{ public:
	Phonebook() { root = NULL; }
	void addphone(Phone ph) { if (not there(root, ph)) addphone(root, ph); }
	bool there(Phone ph) const { return there(root, ph); }
	void listbyname() const { listbyname(root); }
	int getnumber(string nm) const { return getnumber(root, nm); }
	bool dupname() const  // a name appears more than once (someone has two or more numbers)
		{ return dupname(root); }
	bool dupnumber() const  // a number appears more than once (two or more people have the same number)
		{ return dupnumber(root); }
 private:
	Phone*	root;
	void addphone(Phone*&, Phone);
	bool there(Phone*, Phone) const;
	void listbyname(Phone*) const;
	int getnumber(Phone*, string) const;  // returns 0 if name not found
	bool dupname(Phone*) const;
	bool dupnumber(Phone*) const;
};
The entries are held as a binary search tree, ordered on name. Write the overloaded output operator function for Phone and the private functions for Phonebook. For dupnumber (which is harder than the rest), but not for the others, you may write an extra private function if you feel the need.

End of Test 1

Test 2

Question 1

When a constructor that takes arguments is called like this:

Date d(25,12);
why is a default constructor called like this:
Date d;
rather than like this:
Date d();

Question 2

Write the output of the following program:

#include <iostream>
using namespace std;

class B
{ public:
	B() : bx(0) { cout << "B's default constructor" << endl; }
	B(int x) : bx(x) { cout << "B's int constructor" << bx << endl; }
  private:
	int bx;
};

class A
{ public:
	A();
  private:
	B   b, c, d;
};

A::A() : c(2)
{	d = B(3);
	cout << "A's constructor" << endl;
}

class C : public A
{ public:
	C() : A() { cout << "C's default constructor" << endl; }
	C(int cx) : A() { cout << "C's int constructor" << cx << endl; }
};

C c;

int main( )
{ }

Question 3

Write the output of the following procedures, assuming that the call was proc(3);

void proc(int x, int y)
{	cout << string(x, static_cast<char>('A' + y));
}

void proc(int x)
{	if (x > 0)
	{	proc(x - 1);
		proc(x, x);
		proc(x - 1);
	}
}

Question 4

A course director has given an evaluation questionnaire to his students, asking them to rate each of the ten modules of the programme on a scale from 5 ("Module was absolutely fascinating") down to 0 ("Module was incredibly dull"). He has had their responses keyed into a data file, called ratings.dat, with each student's ten ratings on one line, separated by spaces, like this:

1 3 0 2 3 1 5 2 3 0
He wants the results for the ten modules presented as ten tables, one after another, with the student numbers also presented as percentages, to one decimal place. Supposing that there were 200 students, the results for the first two modules might look like this:
Module 1
0: 45 22.5%
1: 59 29.5%
2: 42 21.0%
3: 36 18.0%
4: 14  7.0%
5:  4  2.0%

Module 2
0: 22 11.0%
1: 45 22.5%
2: 40 20.0%
3: 16  8.0%
4: 33 16.5%
5: 44 22.0%
meaning that 45 of the students (22.5%) gave a rating of 0 to the first module, and so on. (The formula for x as a percentage of y is x/y*100. For example, 5 as a percentage of 20 is 5/20 (= 0.25) * 100 (= 25).)

If any line in the file has fewer than ten ratings, or more than ten, or if it contains non-numeric data, or if any of the ratings fall outside the range 0 to 5, he wants that line to be ignored - the results should be the same as they would have been if that line had been completely absent. The following are some examples of lines that should be ignored:

1 2 0 0 5 5 3 3 3 
2 4 3 1 1 5 0 3 0 0 5
6 4 5 3 3 0 3 5 4 2 
2 1 2 4 5 5 4 1 -3 0 
A 2 3 3 1 2 3 5 2 0
3 2 4 5 0 4 0 1 5 1 A
The following are parts of a program to read this data file and to output the tables (to standard output) in the required format:
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <fstream>
#include <iomanip>
using namespace std;

class Results
{ public:
	Results();
	void get_results();
	void show_results() const;
  private:
	vector<int> one_student;
	vector<vector<int> > results;
	int nstudents;		// number of valid lines of data
	static const int nmods = 10;	// 10 modules
	static const int maxresp = 5;	// each response 0 to 5
	bool get_next_student(istream& infile, bool& lineok);
	void add_to_results();
	void show_module(const vector<int>& v) const;
};

Results::Results()
{	one_student = vector(nmods);
	vector<int> one_module(maxresp+1);
	results = vector<vector<int> >(nmods, one_module);
	nstudents = 0;
};

Function definitions here

int main( )
{	Results res;
	res.get_results();
	res.show_results();
}

(a) Draw simple diagrams to show the arrangement of elements in one_student and results.

(b) Write get_next_student. It reads just one line from the data file and puts the ratings into the vector one_student. If the line is a valid one, it sets lineok to true, otherwise to false. It returns true, except at the end of file, when it returns false.

(c) Write get_results, which calls get_next_student and add_to_results It opens the data file and processes it line by line. The ratings from valid lines are accumulated in the results vector.

(d) Write add_to_results. It uses one_student to increment the appropriate elements of results.

(e) Write show_results and show_module to display the contents of results in the required format.

Question 5

A Linkvec object behaves in some ways like a vector, but actually stores its results in a singly linked list, with the tail node corresponding to element[0]. (I suggest you read that last part again to make sure you have taken it in.) nodes keeps a count of the number of nodes. Below are some fragments of the definition and of a program that uses a Linkvec object. Write:

lv.insert(2,99); means, "Insert 99 between lv[1] and lv[2]."

lv.erase(5); means, "Erase lv[5]."

Providing a non-existent element as argument to insert or to erase causes a BadSubscript exception.

Exception classes here
template <typename T>
class Linkvec
{ public:
	Interface prototypes here
	void display(ostream& os) const { display(os, head); }
  private:
	class Node;
	Node* head;
	int nodes;
	void display(ostream&, Node*) const;
};

template <typename T>
class Linkvec<T>::Node
{ public:
	T n;
	Node* link;
	Node(T x) : n(x), link(NULL) {}
};

template <typename T>
ostream& operator<<(ostream& os, const Linkvec<T>& lv)
{ 	lv.display(os);
	return os;
}

Function definitions here

int main( )
try {	Linkvec<int>	lv;
	lv.push_back(5);
	lv.push_back(6);
	lv.push_back(7);
	lv.push_back(8);
	lv.push_back(9);
	lv[lv.size()-1] += lv[0];
	cout << lv << endl;	// outputs 5 6 7 8 14
	lv.insert(2,99);		// lv is now 5 6 99 7 8 14
	lv.insert(0,100);		// lv is now 100 5 6 99 7 8 14
	lv.erase(5);		// lv is now 100 5 6 99 7 14
	lv.erase(5);		// lv is now 100 5 6 99 7
	cout << lv << endl;	// outputs 100 5 6 99 7
}
catch (BadSubscript b)
{	cerr << "Subscript out of bounds: " << b.getsubscript() << endl;
	exit(1);
}
catch (EraseFromEmpty)
{	cerr << "Cannot erase from empty structure" << endl;
	exit(2);
}

End of Test 2


Notes on R. Mitton's lectures by S.P. Connolly, edited by R. Mitton, 2000