算法与数据结构C语言版课后习题答案第9.10章(3)

} else return (r); ∥返回*x结点的中序序号 return (0); ∥T树上无x结点 }∥结束算法Rank

算法2：本题的另一种解法是设r是以*x为根的中序序号。初始时，若x的左子树为空，r=1;否则，r=x->lchild->size+1。利用结点的双亲域，上溯至根结点，即可求得*x的中序序号。

int Rank(tree T，node *x) ∥在二叉排序树T上，求结点x的中序序号 { if(x->lchild)r=x->lchild->size+1; else r=1; ∥x的这个序号是暂时的 p=x; ∥p要上溯至根结点T，求出*x的中序序号 while(p!=T)

{ if(p==p->parents->rchild) ∥p是其双亲的右子女，

{ if(p->parents->lchild==null) r++; ∥p结点的双亲排在p结点的前面 else r=r+p->parent->lchild->size+1; ∥双亲及左子树均排在p前面 } p=p->parents; }∥while return (r); }∥Rank

9.34 已知某哈希表HT的装填因子小于1，哈希函数H(key)为关键字的第一个字母在字母表中的序号。 (1) 处理冲突的方法为线性探测再散列。编写按第一个字母的顺序输出哈希表中所有关键字的算法。 (2) 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。 【题目分析】 本题未直接给出哈希表表长，但已给出装填因子小于1，且哈希函数H(k)为关键字第一个字母在字母表中的序号，字母‘A’的序号为1，表长可设为n(n≥27)，而链地址法中，表长26。查找不成功是指碰到空指针为止(另一种观点是空指针不计算比较次数)。

(1)void Print(rectype h[])∥按关键字第一个字母在字母表中的顺序输出各关键字 { int i,j; for(i=1;i≤26；i++) ∥哈希地址1到26 { j=1；printf(“\\n”); while(h[j]!=null) ∥设哈希表初始值为null

{ if(ord(h[j])==i) ∥ord()取关键字第一字母在字母表中的序号 printf(“%s”，h[j])； j=(j+1)% n； }∥while }∥for }∥end

(2)int ASLHash(rectype h[]) ∥链地址解决冲突的哈希表查找不成功时平均查找长度 { int i,j; count=0; ∥记查找不成功的总的次数 LinkedList p; for(i=1;i<=26；i++) { p=h[i];j=1; ∥按我们约定，查找不成功指到空指针为止 while(p!=null) { j++; p=p->next; } count+=j; } return (count/26.0);

}

9.35 有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求用哈希表作存储结构。 （1）请设计一个哈希表

（2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对算法所需时间和用一维数组(每个分量存放一个非零元素的行值、列值和元素值)作存储结构时存取元素的算法进行比较。

【题目分析】非零元素个数是100，负载因子取0.8，表长125左右，取p为127，散列地址为0到126。哈希函数用H(k)=(3*i+2*j) % 127，i，j为行值和列值。

#define m 127

typedef struct {int i,j; ElemType v;}triple;

void CreatHT(triple H[m]) ∥生成稀疏矩阵的哈希表，表中元素值初始化为0 { for(k=0；k<100；k++) { scanf(&i,&j,&val); ∥设元素值为整型 h=(3*i+2*j)% m; ∥计算哈希地址

while(HT[h].v!=0)) h=(h+1) % m; ∥线性探测哈希地址 HT[h].i=i; HT[h].j=j; HT[h].v=val; ∥非零元素存入哈希表 }∥for

}∥算法CreatHT结束

ElemType Search(triple HT[m]，int i，int j)

{∥在哈希表中查找下标为i，j的非零元素，查找成功返回非零元素，否则返回零值 int h=(3*i+2*j) % m;

while((HT[h].i!=i || HT[h].j!=j) && HT[h].v!=0) h=(h+1)% m; return (HT[h].v); }∥Search

第10章 排序

一、 基础知识题

10.1 基本概念：内排序，外排序，稳定排序，不稳定排序，顺串，败者树，最佳归并树。

【解答】⑴内排序和外排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序适用于记录个数不多的文件，不需要访问外存，而外部排序适用于记录很多的大文件，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 ⑵稳定排序和不稳定排序 假设待排序记录中有关键字Ki=Kj（i≠j），且在排序前的序列中Ri领先于Rj。经过排序后，Ri与Rj的相对次序保持不变（即Ri仍领先于Rj），则称这种排序方法是稳定的，否则称之为不稳定的。

⑶顺串 外部排序通常经过两个独立的阶段完成。第一阶段，根据内存大小，每次把文件中一部分记录读入内存，用有效的内部排序方法（如快速排序、堆排序等）将其排成有序段，这有序段又称顺串或归并段。 ⑷败者树 败者树为提高外部排序的效率而采用的，是由参加比赛的n个元素作叶子结点而得到的完全二叉树。每个非叶（双亲）结点中存放的是两个子结点中的败者数据,而让胜者去参加更高一级的比赛。另外,还需增加一个结点,即结点0,存放比赛的全局获胜者。

⑸最佳归并树 在外部排序的多路平衡归并的k叉树中，为了提高效率减少对外存的读写次数，按哈夫曼

树构造的k叉树称最佳归并树。这棵树中只有度为0和度为k的结点。若用m表示归并段个数，用nk表示度为k的个数，若(m-1)%(k-1)=0，则不需增加虚段，否则应附加k-(m-1)%(k-1)-1个虚段（即第一个k路归并使用(m-1)%(k-1)+1个归并段）。

10.2设待排序的关键字序列为(15， 21， 6， 30， 23， 6′， 20， 17)， 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次比较。

(1) 直接插入排序 (2) 希尔排序(增量为5，2，1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 锦标赛排序 (7) 堆排序 (8) 二路归并排序 (9) 基数排序 【解答】

(1) 直接插入排序

初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接插入排序：【15，21】 第二趟直接插入排序：【6，15，21】 第三趟直接插入排序：【6，15，21，30】 第四趟直接插入排序：【6，15，21，23，30】 第五趟直接插入排序：【6，6′，15，21，23，30】 第六趟直接插入排序：【6，6′，15，20，21，23，30】 第七趟直接插入排序：【6，6′，15，17，20，21，23，30】 (2) 希尔排序(增量为5，2，1)

初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟希尔排序： 6′，20，6，30，23，15，21，17 第二趟希尔排序： 6′，15，6，17，21，20，23，30 第三趟希尔排序： 6′，6，15，17，20，21，23，30 (3) 起泡排序

初始关键字序列：15，21，6，30，23，6′，20，17 第一趟起泡排序：15，6，21，23，6′，20，17，30 第二趟起泡排序：6，15，21，6′，20，17，23，30 第三趟起泡排序：6，15，6′，20，17，21，23，30 第四趟起泡排序：6，6′，15，17，20，21，30，23 第五趟起泡排序：6，6′，15，17，20，21，30，23 (4) 快速排序

初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟快速排序： 【6′，6】15【30，23，21，20，17】 第二趟快速排序： 6′，6， 15【17，23，21，20】30 第三趟快速排序： 6′，6， 15，17【23，21，20】30 第四趟快速排序： 6′，6， 15，17，【20，21】23，30 第五趟快速排序： 6，6′，15，17，20，21，30，23 (5) 直接选择排序

初始关键字序列： 15，21，6，30，23，6′，20，17 第一趟直接选择排序： 6，21，15，30，23，6′，20，17 第二趟直接选择排序： 6，6′，15，30，23，21，20，17 第三趟直接选择排序： 6，6′，15，30，23，21，20，17 第四趟直接选择排序： 6，6′，15，17，23，21，20，30 第五趟直接选择排序： 6，6′，15，17，20，21，23，30

第六趟直接选择排序： 6，6′，15，17，20，21，23，30 第七趟直接选择排序： 6，6′，15，17，20，21，23，30 (6) 锦标赛排序

初始关键字序列： 15，21，6，30，23，6′，20，17 6 6 6’ 15 6 6’ 17 15 21 6 30 23 6’ 20 17 6’ 15 6’ 15 30

6’ 17 15 21 ∞ 30 23 6’ 20 17 15 15 23 15 30 23 17 15 21 ∞ 30 23

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法与数据结构C语言版课后习题答案第9.10章(3)在线全文阅读。