Note: In a few places, some characters have been printed in an odd way. This has to do with the use of high-ASCII box-drawing characters in the original document.
Quiz 1 (15 points)
1. (1 point per blank) Match up these UNIX terms with their pur-
poses:
A. cd B. ls
C. man D. touch
E. mkdir F. rm
G. cp H. cat
____ will make a copy of a file.
____ will change directories.
____ will list the contents of a file on the screen.
____ will remove a file.
____ will change the time and date stamp on a file.
____ will list information about a UNIX topic on the screen.
____ will list the contents of a directory.
____ will create a new directory.
2. (2 points) Suppose I want to change the permissions on a file
called "resume" so anyone can read it but only I can write to
it or execute it. Write the UNIX command I need to do this.
3. (1 point each) Suppose I have the following UNIX command:
g++ program2.cc
(a) The command will create an executable file. What will
be its name?
(b) Suppose I want the executable file to be named "p2"
instead. What do I need to add to the command to make this
happen?
(c) Suppose I want the compiler to produce an object file
instead of an executable file. What do I need to add to the
command to make this happen?
(d) If I add the code as in part (c), what will be the name
of the object file?
(e) If I want the compiler to produce optimized code, what do
I need to add to the command to make this happen?
----------------------------------------------------------------------
Quiz 2 (15 points)
1. Suppose I have variables X and F:
int X = 97; // 97 in base 10 = 61 in base 16
bool F = true;
Suppose I want to print the values of X and F as in
cout << F << X;
(a) (2 points) If I use the cout statement as shown above, what
will be the output? (There is more space here than you need.
Write one character per space.)
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __
(b) (1 point) If I want X to be printed with a minimum width of
6 spaces, what do I need to include in the cout statement?
(c) (1 point) If I want X to be printed left-justified inside
the 6 spaces, what do I need to include in the cout statement?
(d) (1 point) If I want the value of X to be printed in base 16,
what do I need to include in the cout statement?
(e) (1 point) If I want to advance to a new line after X is
printed, what do I need to include in the cout statement?
(f) (1 point) If I want the value of F to be printed as true
instead of a number, what do I need to include in the cout
statement?
(g) (2 points) Write the revised cout statement using all of the
changes described in (b) -- (f).
(h) (2 points) What will be the output from the revised cout
statement? (There is more space here than you need. Write one
character per space.)
__ __ __ __ __ __ __ __ __ __ __ __ __ __ __
2. (1 point) If we print the value of a variable to be printed
inside a given number of spaces, and we do not do anything to
force the result to be printed left-justified or right-justified,
what is the default?
3. (1 point) Suppose I use the statements:
cout.width(8);
cout << X; // X is of type float
If I next want to print the value of some other variable Y, what
will be the minimum width used in printing Y?
4. (1 point) If we want to use these various I/O manipulators, what
library do we need to include?
5. (1 point) Suppose I want to read an input file. I need a
variable in my program to represent the file, as in:
________ DataFile;
What type of variable should DataFile be?
----------------------------------------------------------------------
Quiz 3 (15 points)
1. (3 points) Declare a 3 x 2 array of integers and initialize it
with 6 different integer values in the same statement.
2. (1 point per part) Suppose we have the following in our program:
int Q[8], M, *P;
for (M = 0; M < 8; M++) Q[M] = 3 * M - 2;
P = Q;
(a) At this point, what is the value of M ?
(b) At this point, what is the value of *P ?
(c) Now suppose we have the statement:
P += 2;
Now what is the value of *P ?
(d) Continuing from part (b), what is the value of P[3] ?
3. (2 points) Suppose our program includes a line
#define E 2.71828
Rewrite this without using #define.
4. (2 points per part) Suppose we have the following list of numbers:
17 34 -6 15 41 22 78 11
We want to sort the list in ascending order (left to right).
(a) What will this list look like after we make two passes
through it using Selection Sort?
(b) Suppose we are using Bubble Sort instead. What will
the list look like after we make one pass through it using
Bubble Sort?
(c) Suppose we are using Insertion Sort instead. What will
the list look like after we make two passes through it using
Insertion Sort?
----------------------------------------------------------------------
Quiz 4 (15 points)
Suppose we have a class called Time, storing a time of day. Its
definition might begin like this:
class Time
{
private:
int H; // H = hour
int M; // M = minute
int S; // S = second
public:
int GetHour(); // returns the value of H
int GetMinute(); // returns the value of M
int GetSecond(); // returns the value of S
... // more functions as well
};
1. We want to have a function called PrintTime which will print the
the time in the format H:M:S, such as 11:30:45. (We are not
overloading operator <<.) PrintTime has no return value.
(a) (3 points) Suppose PrintTime has to be a friend of the class
Time. Write the line we need to include in the class definition.
(b) (3 points) Now write the code for the PrintTime function.
(This is a heading plus about one line.)
(c) (3 points) If PrintTime is not a friend and not a member of the
class Time, what changes would we have to make in the code?
2. (6 points) Suppose we also want to overload the operator == so
we can determine whether two times are the same. We want the
function involved to be a member of the class Time.
Write the code for the function. (This is a heading plus about
one line.)
----------------------------------------------------------------------
Quiz 5 (15 points)
1. Consider the following function:
void Q(int N)
{
cout << N;
if (N == 0) cout << ' Boom!';
cout << endl;
if (N > 0) Q(N-1);
}
(a) (3 points) Suppose we execute Q(5). What will be printed?
(Be careful.)
(b) (2 points) When we execute Q(5), how many times is the
function Q actually executed?
(c) (2 points) What would happen if we tried to execute Q(-5)?
(d) (3 points) Suppose we rearrange the code:
void Q(int N)
{
if (N > 0) Q(N-1);
cout << N;
if (N == 0) cout << ' Boom!';
cout << endl;
}
What would this version of the function print when we execute
Q(5)?
2. Suppose we have (in our main program):
float * M;
(a) (2 points) We want to create an array of 28 float values, so
we can refer to M[0], M[1], M[2], ..., M[27].
Write the statement we need to do this.
(b) (2 points) Later we want to get rid of the array and give
back its memory to the operating system. Write the statement
we need to do this.
(c) (1 point) After (b), does the variable M still exist?
----------------------------------------------------------------------
Quiz 6 (15 points)
Use the following in questions 1 through 4:
struct Link
{
int Data;
Link * Next;
};
class List
{
private:
Link * Head;
public:
// various other things
};
1. (5 points) Suppose we have a variable P of type Link *, and
suppose P points to a link containing the value 38 somewhere in
the middle of a List:
ÚÄÄÄÄÂÄÄ¿ ÚÄÄÄÄÂÄÄ¿ ÚÄÄÄÄÂÄÄ¿
Head ÄÄÄ>...ÄÄÄ>³ 15 ³ ÄÅÄÄ>³ 38 ³ ÄÅÄÄ>³ 72 ³ ÄÅÄÄ>...ÄÄÄ> 0
ÀÄÄÄÄÁÄÄÙ ÀÄÄÄÄÁÄÄÙ ÀÄÄÄÄÁÄÄÙ
We want to insert a new link containing the value 47 immediately
after the link containing the value 38.
Write the code we need to do this. You do not need to write a
function heading or return a value.
2. (1 point) In the same situation as in problem 1, if we wanted to
insert the new link before the link containing the value 38, could
we do it using the pointer P?
3. (5 points) Suppose we want to search the list for a link contain-
ing the value X, which may or may not be present. We need a
member function called Search with the following heading:
Link * List::Search(const int& X) const
{
// code goes here
}
Search should return a pointer to the link containing X, or 0
if X is not present. Bear in mind the List might be empty.
Write the code for the Search function.
4. (4 points) Suppose we want to delete the first link in a List.
Assume the List has at least one link in it.
Write the code we need to do this. You do not need to write a
function heading or return a value.
----------------------------------------------------------------------
Quiz 7 (15 points)
Suppose we have a binary search tree implemented using pointers:
struct Node
{
char Data;
Node * Left;
Node * Right;
};
class BinTree
{
private:
Node * Root;
public:
// various things
};
Here is a specific tree:
Root
³
ÚÄÄÄ¿
³ M ³
ÀÄÄÄÙ
ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄ¿
ÚÄÄÄ¿ ÚÄÄÄ¿
³ G ³ ³ T ³
ÀÄÄÄÙ ÀÄÄÄÙ
ÚÄÄÄÄÄÙ ÀÄÄÄÄÄ¿ ÚÄÄÄÄÄÙ ÀÄÄÄÄÄ¿
ÚÄÄÄ¿ ÚÄÄÄ¿ ÚÄÄÄ¿ ÚÄÄÄ¿
³ D ³ ³ K ³ ³ P ³ ³ V ³
ÀÄÄÄÙ ÀÄÄÄÙ ÀÄÄÄÙ ÀÄÄÄÙ
ÚÄÙ ÀÄ¿ ÚÄÙ ÀÄ¿ ÚÄÙ
ÚÄÄÄ¿ ÚÄÄÄ¿ ÚÄÄÄ¿ ÚÄÄÄ¿ ÚÄÄÄ¿
³ A ³ ³ C ³ ³ I ³ ³ L ³ ³ N ³
ÀÄÄÄÙ ÀÄÄÄÙ ÀÄÄÄÙ ÀÄÄÄÙ ÀÄÄÄÙ
1. (1 point) Is this a full binary tree?
2. (1 point) Is this a complete binary tree?
3. (4 points) Suppose we print the contents of the tree using a
post-order traversal. We print all the characters on one line,
separated by spaces. What will be printed?
4. (2 points) Suppose we want to insert a node containing the value
'J'. Where will we attach the new node? Specifically, what value
is in the new node's parent node, and will the new node be a left
child or a right child?
5. (3 points) What will the tree look like if we delete the node
containing the value 'P'? Redraw the part of the tree that will
change. Use the technique described in class.
6. (4 points) Suppose we want to delete the node containing the
value 'G'. Redraw the part of the tree that will change. Use the
technique described in class.
----------------------------------------------------------------------
Quiz 8 (15 points)
1. (7 points) Suppose we have the following class:
class Bundle
{
private:
float Height;
int * List; // dynamically allocated array of int
int Size; // size of list
public:
Bundle();
Bundle(Bundle & Other);
// more stuff
};
We would also like to have an assignment operator. Here is some
code for it. Fill in the blanks.
____________ Bundle::operator =(const Bundle & Other)
{
if (_________________________)
{
List = __________________;
delete __________________;
for (int I = 0; I < ____________; I++)
{
________________________;
}
Height = Other.Height;
}
return _____________;
}
2. (3 points) Suppose we already have a basic constructor and an
assignment operator, and we implement a copy constructor as
follows:
First, call the basic constructor.
Second, call the assignment operator.
What is wrong with this approach?
3. (1 point) One of the problems in traversing a graph is that the
nodes are in no particular order, so we have to keep track of
which nodes we have already visited.
A. True B. False
4. (1 point) When we define a class as a template, as in
template
class OurClass
{
// stuff
}
the name T must be the name of a class defined somewhere and
cannot be the name of an elementary type such as int or char.
A. True B. False
5. (1 point) When we write the code for a recursive function, we
normally begin by testing for the condition that will end the
recursion.
A. True B. False
6. (2 points) Which of the following is not always provided as
a default for every class (even though the default version may
not be what we want)?
A. basic constructor
B. assignment operator
C. operator []
D. copy constructor
E. destructor
----------------------------------------------------------------------
Extra-Credit Take-Home Quiz (15 points)
Due on Monday, April 28, in class
1. (3 points) Suppose we have a class which provides stacks which
store values of type char. It is implemented as a dynamic array.
Here is part of the definition of the class:
class StackChar
{ private:
int Index; // Index = number of items in the stack
char * Array;
public:
StackChar();
StackChar(const &StackChar Old);
~StackChar();
void push(const char& X);
char pop();
bool empty() const;
bool full() const;
// probably other functions as well
};
Write the complete code for the copy constructor for StackChar.
2. At the right side of this page is some data. ³ Data:
³
(a) (3 points) Write the code that we need (not a ³ B
whole program) to create a variable of type StackChar, ³ K
read each letter (using "cin") and push it onto the ³ Q
stack. The end of the data occurs when the character ³ A
is a period. (Do not put the period on the stack.) ³ Z
You do not need to write the code for the StackChar ³ I
class. You do need to declare variables. ³ P
³ F
³ R
³ Y
³ C
³ D
³ T
³ L
³ .
(b) (1 point) Now suppose we pop each letter off the stack
and insert it into a binary search tree. What will the binary
search tree look like when we are done? Use the techniques
discussed in class.
3. Suppose we have a class which provides queues of values of type
int. It is implemented as a singly-linked list with Head and Tail
pointers. Here is part of the definition of the class:
struct Link
{ int Data;
Link * Next;
};
class QueueInt
{ private:
Link * Head;
Link * Tail;
public:
QueueInt();
~QueueInt();
void push(const int& N);
int pop();
bool empty() const;
bool full() const;
// probably other things as well
};
We would like to overload the != operator for this class. The
prototype should be:
friend operator !=(const QueueInt& First, const QueueInt& Second);
(4 points) Write the complete code for the function.
4. (4 points) Suppose we have a class which provides doubly-linked
lists of values of some type T. Here is part of the definition of the
class:
struct DLink
{ T Data;
DLink * Back;
DLink * Next;
};
class DList
{
private:
DLink * Head;
public:
// lots of other things as well
};
We want to have a bool-valued member function CheckList in the
DList class which checks the pointers to make sure that the list is
connected correctly. That is:
Suppose P and Q are DLink * variables (and neither is 0). Then
if P->Next = Q, then Q->Back should be P.
There are two special cases involving the first and last links.
If anything is wrong, the function should return false. Other-
wise, it should return true.
Write the complete code for the CheckList function.