Quiz — Vectors and i/o streams

---

This quiz tests you on the details of using the vector class (with one- and two-dimensional structures), on common applications of vector processing (e.g. search, insertion, deletion), and on the commands for initializing and using file and string streams.

Readings

A Computer Science Tapestry, sections 7.4, 7.4.1, 8.1 through 8.3, and 9.1 through 9.3. Astrachan's sections 9.2.2 and 9.2.3 contain the only good explanation of string streams among the three CS 9F textbooks. Astrachan's tvector class is just like the builtin vector class except that it incorporates checks for out-of-range subscript values. He only covers two-dimensional structures (in section 10.3; we don't use his tmatrix class) in the context of more advanced material.

i>C++ Program Design, sections 5.6 (files) and 6.7 (minimal coverage of string streams) plus chapter 10. C-style arrays are forbidden in CS 9F; thus you should ignore declarations in sections 10.2 and 10.12, instead using the vector class to build a two-dimensional structure.

Computing Fundamentals with C++, chapters 9 (files), 10 (vectors), and 19 (two-dimensional structures). Also skim chapters 12 and 13. Mercer does not cover string streams, and mentions structs only in the context of more advanced material. We don't use his matrix class; use vectors of vectors instead.

Miscellaneous information

Reminder: restrictions about using C constructs described in the section "C constructs to avoid" are in effect for this quiz.

Sample exercises

All exercises on files in chapter 7 of A Computer Science Tapestry, all exercises in chapter 8, and all exercises in chapter 9 except those involving operator overloading will be useful.

All exercises in chapter 10 of C++ Program Design except those involving C-style arrays will be useful.

All exercises in chapters 9, 10, and 19 of Computing Fundamentals with C++ including self-check exercises but not including programming projects, will be useful. Translate uses of the matrix class in the chapter 19 exercises to uses of vectors of vectors.

Sample quiz

1. Write a function that takes a vector of integers as argument and reverses its elements.
2. Write a program segment that, given a vector of vectors named vals and coordinates of one of its elements in row and col, prints the values that lie on the lower-left to upper-right diagonal of vals that contains the element with the given coordinates. The values should be printed one per line; it doesn't matter what order they are printed, except that you shouldn't print any element twice.
3. Complete the function below intended to play the game of "Treasure Hunt". In this game, you are given an initial clue, which leads you to the place of the next clue, which leads you to the next, and so on. Occasionally you will enter a loop, in which case you lose, and the function returns false. The "clues", for this problem, are index values in an 10-element vector; the value in a cell tells you the position of the next cell to look in. A position outside the vector means you win, and the function returns true.

   In the example vector below, starting at position 0 leads you to 2, then 7, then 3, then 1, and you win. Starting at position 9 leads you to 7, 3, 1, and a win. Starting at 5 leads you to 8, then 4, then 6, then 8 where you repeat the previous steps, so you lose.

   Sample treasure hunt vector:

	2	99	7	1	6	8	8	3	4	7

	bool TreasureHunt ( _____________ , int clue) {
		for (int numClues=1; numClues < 11; numClues++) {
			if (clue<0 || clue>9) {
				return true;
			} else {
				_________ ; // one statement goes here
			}
		}
		return false;  // more than 10 clues, so we must be in a loop.
	}

4. Consider a chess-playing program split into three files. One, in the file playchess.cpp, contains the code implementing the strategy for playing chess. A second, board.cpp, contains the code that implements the 8-by-8 board, using an 8-by-8 boolean vector of vectors, and the functions that move pieces and search the board. The third, board.h, declares the functions that board.cpp exports. Explain which of the three files might contain each of the following, and the context in which each might appear:

	Board b
	vector < vector<bool> > pieces
	vector < vector<bool> > pieces (8, 8)
	vector < vector<bool> > pieces [0][0]
	

5. Write a function that, given as argument a file of numbers open for input, reads and echoes all the values in the file to cout.

Solutions to sample quiz

	void Reverse (Vector<int> &v) {
		for (int k=0; k<v.size( )/2; k++) {
			int temp = v[k];
			v[k] = v[v.size( )-k-1];
			v[v.size( )-k-1] = temp;
		}
	}

	r = row; 
	c = col;
	while (r>=0 && c<vals[0].size()) {  // print values up from row,col
		cout << vals[r][c] << endl;
		r--;
		c++;
	}
	r = row + 1;
	c = col - 1;
	while (c>=0 && r<vals.size()) {  // print values down from row,col
		cout << vals[r][c] << endl;
		r++;
		c--;
	}

3. Add vector<int> clues to the function heading, and add the statement

		clue = clues[clue];

to the else clause.

4. Board b might appear as a definition in playchess.cpp. It might also appear as a parameter declaration in functions in any of the files (although not in the functions declared in board.h as Board member functions).

   vector < vector<bool> > pieces would most likely appear in board.h as part of the Board class declaration. It might also appear in function headers of private functions in board.cpp. It would probably not appear in playchess.cpp.

   vector < vector<bool> > pieces (8, 8) is illegal. The second argument to the vector constructor should be the value to be assigned to each element of the vector-here, another vector, not an integer.

   vector < vector<bool> > pieces [0][0] is illegal and wouldn't appear anywhere.

	void Echo (ifstream &filein) {
		int x;
		while (filein >> x) {
			cout << x;
		}
	}