=========================preview======================
(comp151h)[2007](s)midterm~1712^_10139.pdf
Back to COMP151H Login to download
======================================================
COMP 151H: Object Oriented Programming (Honor Track)
Spring Semester 2007
Midterm Exam
Instructor: Chi Keung Tang
Monday, March 19, 2007
7:00 C 9:00pm
Room 3007

This is a CLOSED-BOOK-CLOSED-NOTES exam consisting of four (4) problems. Follow the instructions carefully. Please write legibly in the space provided. Keep the exam booklet stapled.
KEY


Problem
Points
your score




1 HASH TABLE AND TEMPLATES
5
2 staticAND constMEMBERS
3
3 POINTERS AND CLASS POINTERS
3
4 INTERFACE VS IMPLEMENTATION
4
Total
15
1 Hash Table and Templates
Assume the template class DoublyLinkedList is already de.ned (in Lish.h, shown below) and implemented (in List.cpp).
template<class ElemType> // ElemType must define the operator<
class DoublyLinkedList
{

public:
DoublyLinkedList();
.DoublyLinkedList();
DoublyLinkedList(const DoublyLinkedList& copy);
DoublyLinkedList& operator=(const DoublyLinkedList& assign);

// insert an element
void insert(const ElemType& element);

// clear the whole list
void clear();

// other member functions ...

private:
// other members ...
};

Notice: You must answer this question by making use of the above de.nition. Do not de.ne your own linked list and hash
table. However, you are free to use any member functions de.ned in class DoublyLinkedList.
The template class HashTable is also de.ned in HashTable.h.

#include "List.h"

template<class ElemType> // ElemType must define the operator<
class HashTable
{

public:
typedef unsigned int (*HashFunc) (const ElemType&);

// hashFunc must return an integer in-between 0 and (numBuckets-1)
HashTable(int numBuckets, HashFunc hashFunc); // (1)

HashTable(const HashTable& copy); // (2)
HashTable& operator=(const HashTable& assign); // (3)
.HashTable();

// insert an element
void insert(const ElemType& element);

// other member functions

private:
DoublyLinkedList<ElemType>* m_buckets; // buckets

unsigned int m_numBuckets; // number of buckets
HashFunc m_hashFunction; // hash function
};

Notice: You must answer this question by making use of the above de.nition. Do not de.ne your own linked list and hash table. However, you are free to use any member functions de.ned in class DoublyLinkedList.
2 (a) De.ne the following member functions
HashTable(int numBuckets, HashFunc hashFunc);
HashTable(const HashTable& copy);
HashTable& operator=(const HashTable& assign);

Solution:
// Note: CheckSufficientMemory() and SAFE_DEL_ARRAY() are helper functions
// and is clear from context.
// Students answering this question should implement this in answering this question,
// which is only a simple if-else.

template<class ElemType>
HashTable<ElemType>::HashTable<ElemType>(int numBuckets, HashFunc hashFunc)
{
m_buckets = new DoublyLinkedList<ElemType>[numBuckets];
CheckSufficientMemory(m_buckets);

m_numBuckets = numBuckets;
m_size = 0;
m_hashFunction = hashFunc;
}

template<c