=========================preview======================
(COMP152)[2009](s)final~885^sol_10144.pdf
Back to COMP152 Login to download
======================================================
COMP 152 Fall 2009
Final Solutions
1. (a) Memory leak
(b)
Segmentation fault, dereference NULL pointer
(c)
Compilation error, modifying data members in a const function
(d)
iv
(e)
iv
2. (a) template <class T>
Matrix::Matrix(unsigned int m, unsigned int n){
if (m==0 || n==0){
_m = 0;
_n = 0;
_data = NULL;
}
else{
_m = m;
_n = n;
_data = new T*[m];
for (unsigned int i=0; i<m; i++)
_data[i] = new T[n];
}
}
(b) template <class T>
Matrix::Matrix(const Matrix& m){
if (m._data == NULL){
_m = 0;
_n = 0;
_data = NULL;
}
else{
_m = m._m;
_n = m._n;
_data = new T*[_m];
for (unsigned int i=0; i<_m; i++){
_data[i] = new T[_n];
for (unsigned int j=0; j<_n; j++) //<----
_data[i][j] = m._data[i][j]; //<----
}
}
}
(c) template <class T>
Matrix::~Matrix(){
if (_data != NULL){
for (unsigned int i=0; i<_m; i++)
delete [] _data[i];
delete [] _data;
}
2
}
(d) template <class T> const T& Matrix::getValue(unsigned int m, unsigned int n) const{
if (m<0 || m>=_m || n<0 || n>=_n){
cerr << "ERROR: Index out of range" << endl;
return T;
}
else
return _data[m][n];
}
(e) template <class T> bool Matrix::setValue(const T & value, unsigned int m, unsigned int n){
if (m>=0 && m<_m && n>=0 && n<_n){
_data[m][n] = value;
return true;
}
else
return false;
}
3. (a) This can be done similar to an insertion sort. For each element in the array, keep popping the top element from S to Temp stack until the top one is larger or equal to the element. Push the element into the stack S.Keep popping the elements in Temp and pushing them back to S.
After all the elements in the array are scanned and pushed this way, the stack S has the elements sorted in increasing order from the top.
(b) template<typename T>
stack<T> StackSort(const T A[], const int size) {
stack<T> S; // Use this stack to store the sorted result stack<T> Temp; // The other stack you can use
for (int i=0; i < size; i++){
while (!S.empty() && S.top() < A[i]){ Temp.push(S.top()); S.pop();
}
S.push(A[i]);
while (!Temp.empty()){
S.push(Temp.top());
Temp.pop();
}
}
return S;
}
4. (a) In order to make use of max\_num,the operator > should be over-loaded in template de.nition of MyNumber.
bool operator>(MyNumber<T> & second);
(b) The implementation is as follows:
template <class T> bool MyNumber<T>::operator>(MyNumber<T> & second){ if(data > second.data) return true; else return false; }
5. (a) SpellChecker::SpellChecker(string filename, int size){ ifstream fin; fin.open(fileword.data()); hash_table = vector<list<string> > (size, list<string>());
if (fin.fail()) {
cout << "cannot open" << endl;
exit(1);
}
while (!fin.eof()) { string word; fin>>word; hash_table[hash(word)].push_back( word );
}
fin.close();
}
(b) void SpellChecker::insert(string word){
int pos = hash(word);
list<string>::ite