数据结构期末复习题汇总

九、（本题9分） 【解答】

（1）设第v层有u个结点(m

第1层有1个结点，第2层有m个结点，第3层有m2结点，用数学归纳法易知k层共有mk-1个结点。

mh?1（2）整棵树结点数=1+m+m+…+m=。

m?12

h-1

（3）设编号为i的结点双亲的结点编号为x，将编号为i的结点视为完全二叉树的最后一个结点，因此，此完全m叉树中至少有 x-l个度为 m的结点，而 x号结点的度 d（1≤d≤m），其余的结点均为叶子结点，而编号i就是此完全m又树的总结局数，于是有：

(x-1)m+d+1=i

所以有x?i?m?d?1，由于1≤d≤m，所以有：

mi?m?2i?mi?m?2 ?1??1?x?mmm可知：x??i?m?2?。

???m?设编号为i的第j个子结点为完全m叉树的最后一个结点n，此完全m叉树中有i-1个度为m的结点，

m+j+1 一个度为j的结点，其他结点均为叶子结点，可得：n=(i-l)×

十、（本题15分）

【解答】在理想情况下，可实现散列表查找、插入、删除操作的操作时间为O(1)，对于本题，由于已经知道了关键字的取值范和散列表的最大插入次数，可作理想化处理哈希方法：将查找与数据在一起的哈希表一分为二：采用两个数组ht和 elem，其中ht是从0到 m-1的整数数组（做索引用）；elem数组的数据类型为哈希表中各元素的类型，其元素个数为n（即最大的插入次数），两个数组都不需要初始化。使用计数器lastE表示上次所用到的elem中的位置，初值为-1。ht[k]中的值可能无效（用-1表示）也可能是elem的索引（用来寻找关键字为k的元素），如下图所示：

具体算法实现当如下：

// 文件路径名:exam8\\alg.h // 理想散列表类

template class IdealHashTable {

protected:

// 散列表的的数据成员:

int *ht; // 用作elem的索引 ElemType *elem; // 在放插入的哈希表的元素 int lastE; // 计数器，表示上次用到的elem位置 int n; // 最大插入次数 int m; // 关键字范围0~m-1

public:

// 理想散列表方法声明及重载编译系统默认方法声明: IdealHashTable(int maxInsertCount, int size); // 构造函数 ~IdealHashTable(); // 析造函数 void Traverse(void (*Visit)(const ElemType &)) const; // 遍历散列表 bool Search(const KeyType &key, ElemType &e) const; // 查寻关键字为key的元素 bool Insert(const ElemType &e); // 插入元素e bool Delete(const KeyType &key, ElemType &e);// 删除关键字为key的元素，用e返回元素值 IdealHashTable(const IdealHashTable ©); // 复制构造函数 IdealHashTable &operator= (const IdealHashTable ©); // 赋值语句重载 };

// 理想散列表类的实现部分

template

IdealHashTable::IdealHashTable(int maxInsertCount, int size)

// 操作结果: 构造最大插入次数为maxInsertCount, 关键字范围为0~size-1的空理想散列表 { n = maxInsertCount; // 最大插入次数 m = size; // 关键字范围为0~size-1 ht = new int[n]; // 为elem索引表分配存储空间 elem = new ElemType[m]; // 为元素分配存储空间 lastE = -1; // 初始化lastE for (int pos = 0; pos < n; pos++) { // 初始化ht ht[pos] = -1; } }

template

IdealHashTable::~IdealHashTable() // 操作结果: 销毁散列表 { delete []ht; // 释放ht delete []elem; // 释放elem }

template

void IdealHashTable::Traverse(void (*Visit)(const ElemType &)) const // 操作结果: 依次对散列表的每个元素调用函数(*visit) { for (int pos = 0; pos < m; pos++)

{ // 对散列表的每个元素调用函数(*visit) if (ht[pos] != -1) (*Visit)(elem[ht[pos]]); } }

template

bool IdealHashTable::Search(const KeyType &key, ElemType &e) const // 初始条件: 关键字key的范围为0~m-1，ht[key]的范围为0~lastE

// 操作结果: 查寻关键字为key的元素的值,如果查找成功,返回true,并用e返回元素的值, // 否则返回false { if (key < 0 || key >= m) { // 范围错 return false; // 查找失败 } else if (ht[key] < 0 || ht[key] > lastE || elem[ht[key]] != key) { // 表中没有要查找的元素 return false; // 查找失败 } else { // 存在要查找的元素 e = elem[ht[key]]; // 用e返回元素值 return true; //查找成功 } }

template

bool IdealHashTable::Insert(const ElemType &e) // 操作结果: 将元素插入到elem数组lastE位置，同时修改索引值 { KeyType key = e; // e的关键字 ElemType eTmp; // 临时变量 if (key < 0 || key >= m) { // 范围错 return false; // 插入失败 } else if (Search(key, eTmp)) { // 查找成功 return false; // 插入失败 } else if (lastE == n - 1) { // 超过最大插入次数 return false; // 插入失败 } else { elem[++lastE] = e; // 修改计数器，将元素插入到表中 ht[key] = lastE; // 索引表ht中ht[key]记录关键字为key的元素在elem中的位置 return true; // 插入成功 } }

template

bool IdealHashTable::Delete(const KeyType &key, ElemType &e)

// 操作结果: 删除关键字为key的数据元素,删除成功返回true,并用e返回元素值，否则返回false, // 通过将lastE位置元素移到删除位置，lastE指向倒数第二个元素，从逻辑上完成删除 { if (!Search(key, e)) { // 查找失败 return false; // 删除失败 } else { // 查找成功 e = elem[ht[key]]; // 用e返回被删除元素值 elem[ht[key]] = elem[lastE--]; // 将最后元素移到所删除处,将修改LastE指向新的末记录 int k = elem[ht[key]]; // 原最后元素的关键字 ht[k] = ht[key]; // 修改索引值 ht[key] = -1; // 修改ht[key]为-1，表示关键字为key的元素已初删除 return true; // 删除成功 } }

template

IdealHashTable::IdealHashTable( const IdealHashTable ©) // 操作结果：由散列表copy构造新散列表--复制构造函数 { n = copy.n; // 最大插入次数 m = copy.m; // 关键字范围为0~m-1 ht = new int[n]; // 为elem索引表分配存储空间 elem = new ElemType[m]; // 为元素分配存储空间 lastE = copy.lastE; // 计数器，表示上次用到的elem位置 int pos; // 临时变量 for (pos = 0; pos < m; pos++) { // 复制元素索引 ht[pos] = copy.ht[pos]; // 复制元素索引值 } for (pos = 0; pos < m; pos++) { // 依次复制数据元素 elem[pos] = copy.elem[pos]; // 复制元素值 } }

template

IdealHashTable &IdealHashTable:: operator=(const IdealHashTable ©) // 操作结果：将散列表copy赋值给当前散列表--赋值语句重载 { if (© != this)