CSIS-10BMIDTERM SOLUTIONS Open Notes & Book
Solve the following problems (unless noted, all questions are 10 points)
Problems 1 through 2 use the following Node class:
class Node
{
public:
Node(int newData){ data=newData; next=0;}
int data;
Node* next;
};
1) Given the above linked list, show the output for each of the following statements or indicate why an error will happen:
OUTPUT
a) cout<(head->next->data);a) 45
b) Node * p=head->next;b) 12
p=p->next->next;
cout<(p->data);
c) Node* p=head->data;c) Error assigning head->data to p
cout<(p->data);(wrong type)
d) for (Node* p=head; p!=0; p=p->next)d) 23 45 17 12
cout<p->data;
2) Redraw the picture of the list above 2) after the following statements are performed.
Show the position of pointers p and q and draw an X through deleted nodes:
q->next=p->next;
delete q;
q=0; / Picture of list after code runs
a)
b)Node* p= head->next->next;
Node* q= head->next;
q->next=new Node(33);
q->next->next=p; / b)
3) Draw a picture of memory after these statements:
a) / Picture for a) / b) / Picture for b)int i, j, k;
int *p, *q, *r;
p = &k;
q = &i;
r=&j;
i=13;
*p=7;
*r=i; / / int i, j, k;
int *p, *q, *r;
p = &i;
r = p;
q = &k;
*q=5;
j = k; /
4) (30 points) the following code defines a phone number class (abreviated as Fonum) which is used to store a telephone number in terms of its 3-digit area code, 3-digit exchange, and 4-digit number. For example a Fonum object representing the number (831)555-1212 would have an area code of 831, exchange of 555 and number of 1212.
class Fonum
{
public:
Fonum (int ar=0, int ex=0, int nm=0);
// constructor: creates a new Fonum object with given or default params
void display(ostream& out);
// displays a Fonum to output stream using standard phone number
//formatting (831)555-1212
void read(istream& in);
// read a standard formatted Fonum from input stream,
// written as (area)exch-num
bool operator<(Fonum& right);
// return true if host is a ‘smaller’ Fonum than right
private:
int area, exch, num; // (831)555-1212 (area)exch-num
}
ostream& operator<( ostream& out, Fonum& f);
istream& operator>( istream& in, Fonum& f);
Example main application:
Fonum p(831,555,1212);cout<"My number is "<p<endl;
Fonum f();
cout<”originally, f is “<f<endl;
cout<”please input a phone number”<endl;
cout<”in standard (XXX)YYY-ZZZZ format<endl;
cin>f;
cout<”you entered “<f<endl;
if (f<p)
cout<f<” is lower than “<p<endl;
else
cout<f<” is not lower than “<p<endl; / My number is (831)555-1212
originally, f is (0)0-0
please enter…
…format
(831)333-4444 (entered)
you entered (831)333-4444
(831)333-4444 is lower than (831)555-1212
In the space below, write your
IMPLEMENTATION of constructor, display, read, and operator<
Fonum:: Fonum (int ar=0, int ex=0, int nm=0)
{ area=ar; exch=ex; num=nm;}
void Fonum:: display(ostream& out)
{
out<"("<area<")"<exch<"-"<num;
}
void Fonum::read(istream& in)
{ char paren, dash; // these hold the formating symbols (, ), -
in>paren>area>paren>exch>dash>num;
}
bool Fonum::operator(Fonum & right)
{
if (area < right.area ||
area == right.area & exch < right.exch ||
area == right.area & exch == right.exch & num < right.num)
return true;
else
return false;
}
class Person
{ public:
Person(string newName="***", int newBorn=0, int newDied=0);
string name() { return name; }
int born() { return yob; }
int died() { return yod; }
void print(ostream & out);
private:
string name;
int yob, yod;
};
5) Given the class definition above, please mark whether the following statements are legal or illegal in a client function. Assume author and year (and nothing else) are declared as shown in the first statement.
Person class is defined above.
Statement / Legal / IllegalPerson author; int year; / x
cout<name(); / X
year=author.born(); / X
author.print(cout); / X
name="Ralph Waldo Emerson"; / X
year=author.yob; / X
author.died(year); / X
cin>author.born(); / X
cin>author; / X
6) a) Suppose you use the Nyhoff dynamic array based List class in the following program segment. What will b's member variables look like after we execute these statements (assume typedef char ElementType:
List b(10);
b.insert('a',0);
b.insert('b',1);
b.insert('c',0);
b.insert('d',2);
(draw from 0 to mySize-1)
mySize__4__ myCapacity___10__ myArray __cadb______
b) Assuming List b at some point looks like:
mySize 10 myCapacity 10 myArray a b c d e f g h i j
what will the member variables hold after the following statements
while(!b.empty())
b.erase(0);
(draw from 0 to myCapacity-1)
mySize__0__ myCapacity__10__ myArrayarray will have all j’s in it
7) (15 Points) The goal for this problem is to create a function called removeAll in the array based List class that takes an argument indicating a value to be removed, and removes all occurences of it. For example, suppose you have a list dataList in which myArray contains many unwanted zero’s :
myArray / 40 / 13 / 0 / 0 / 12 / 8 / 9 / 0 / 17 / 19 / 23 / 0 / 0 / 0 / 0 / 11 / …..In order to clean up the list, a call to dataList.removeAll(0), will result in the following modification to myArray:
myArray / 40 / 13 / 12 / 8 / 9 / 17 / 19 / 23 / 11 / …..A natural approach to removeAll() is create another member function to help you accomplish this task. This is a function called find() that searches for an item in myArray and returns the cell in the array of the first occurrence of the item. Write the definition of find() using the shell below:
int List::find(ElementType target)
{ //Precondition: none
//Postcondition: if target is inside the valid part of myArray (0 to size-1)
returns the cell of the first occurrence
if target not found, returns -1
for(int k=0; k<mySize; k++)
{
if (myArray[k]==target)
return k;
}
return -1;
}
Using your find() function, and the erase function already defined for the class:
void List::erase(int pos);
// Remove the value at cell pos from myArray
Write the definition of removeAll( ) using the shell that follows:
void List:: removeAll (ElementType target)
{ //Precondition: none
//Postcondition: all instances of target in myArray (if any) are erased
int k=find(target);
while(k>=0)
{ erase(k);
k=find(target);
}
}
8) (5 Points Extra Credit) A more efficient (and more challenging) solution to problem 6 would be a self contained function that modifies the array directly, with a for loop, using no other functions. This approach involves repeated copying of one cell of the array to another, similar to the erase function, but more complex since the offset keeps shifting. Rewrite removeAll using this approach. (Hint, use two variables, for example, k and m, to keep track of the source and destination cell for each copy performed. In other words, myArray[k]=myArray[m]; where k and m are managed in the for loop.)
int List:: removeAll (ElementType target)
{ //Precondition: none
//Postcondition: all instances of target in myArray (if any) are erased
int k=0, m=0, newSize=0; // m is the cell in old list, k is the cell in new list
while(m<mySize)
{
while(myArray[m]==target & m<mySize) // advance m over any
m++; // cells with target in them
if (m<mySize) // if we haven't passed end of myArray
{
myArray[k]=myArray[m]; // copy from old position to new position
newSize++;
k++; // advance new position
m++; // advance old position
}
}
mySize=newSize;
}
ALTERNATIVE
{
for (int x=0; x< mySize; x++)
{
if (myArray[x]==target)
{
if (x+1 < mySize)
{
for (int y=x; y<mySize; y++)
myArray[y]=myArray[y+1];
}
mySize--;
x--;
}
}