056312409数据结构（C语言版）（夏燕张兴科）--习题答案--第9章

9.7.1 习题与上机操作

9.7.1习题

⒈ 选择题 ⑴ ⑻ B B ⑵ ⑼ C B ⑶ ⑽ C A ⑷ D ⑸ D ⑹ C ⑺ A ⒉ 填空题 ⑴ 哈希表查找法 ⑵ 15

⑶ log2?n??1

⑷ 结点数n，生成过程 ⑸ 越大，越小 ⑹ ASL?1(1?n) 2n?1(n?1)ASL?log2?1

n1nASL?(?s)?1

2s⑺ 顺序存储结构 有序的 ⑻ 右子树 ⑼ 素数 ⑽ n n+1 ⒊ 应用题

⑴ 顺序表类型定义

#define MAX 100 /* 顺序表长度*/ typedef int elemtype /* 关键字类型为整数*/

typedef struct

{ elemtype elem[MAX+1] ;

/*查找表数据元素存储空间基址，建表时按实际长度分配，0号单元留空*/ int length ; /*表中元素个数*/ ｝SStable ; /*顺序表类型*/ 顺序查找算法(监视哨设在高下标端) int SeqSearch(SStable ST, keytype kx) {int i ;

ST.elem[length+1].key=kx; /*设置哨兵*/ i=1;

while (ST.elem[i].key != kx ) /*从表尾开始查找*/ i++ ;

if (i == ST.length +1)

printf(“Searching Fail!\\n”); else

printf(“Searching Success!\\n”);

return( i ) ; /*找到，返回结点的序号，否则返回0*/

}

在等概率情况下, 表长为n：

查找成功的平均查找长度 ASL=

n?1 2查找不成功的平均查找长度 ASL=n+1

⑵ 对有序数据表（5，7，9，12，15，18，20，22，25，30，100），用折半查找方法查找关键字为12和28的数据。

① 查找关键字kx=12的过程：

1 5 ↑ low

2 7

3 9

4 12

5 15

6 18 ↑ mid

7 20

8 22

9 25

10 30

11 100 ↑ high

因为12＜18，修改high=mid-1=5，重新选择mid。

1 5 ↑ low 1 5 low

2 7 2 7

3 9 ↑ mid 3 9

4 12 4 12 ↑↑ low=mid

5 15 ↑ high 5 15 ↑ high

6 18 6 18

7 20 7 20

8 22 8 22

9 25 9 25

10 30 10 30

11 100 11 100

因为12＞9，修改low=mid+1=4，重新选择mid。

这时LAB.elem[mid].key=12即为所求，返回该mid值。 ② 查找关键字kx=28的过程：

1 5 ↑ low

2 7

3 9

4 12

5 15

6 18 ↑ mid

7 20

8 22

9 25

10 30

11 100 ↑ high

因为28＞18，修改low=mid+1=7，重新选择mid。

1 5

2 7

3 9

4 12

5 15

6 18

7 20 ↑ low

8 22

9 25 ↑ mid

10 30

11 100 ↑ high

因为28>25，修改low=mid+1=10，重新选择mid。

1 5

2 7

3 9

4 12

5 15

6 18

7 20 8 22

9 25

10 30 ↑↑

11 100 ↑

low＝mid high

因为28<30，修改high=mid-1=10，重新选择mid。

1 5

2 7

3 9

4 12

5 15

6 18

7 20

8 22

9 25

10 30 ↑↑↑ low=mid=high

11 100

因为28<30，修改high=mid-1=9，此时low＞high，说明表中没有关键字等于28的结点，查找不成功。

1 5

2 7

3 9

4 12

5 15

6 18

7 20

8 22

9 25 ↑ high

10 30 ↑↑ low=mid

11 100

⑶ 关键字为｛7，5，8，16，12，18，14，6，4，10，9，13，15，17，20｝的最佳二叉排序树（平均查找长度最小）如下

127546891013141517161820

含有相同结点的二叉排序树是不惟一的，因此有n个结点的二叉排序树的平均查找长度和树的结构有关。例如，当关键字递增有序时，按照二叉排序树构造方法产生的二叉排序树是一棵右单只树，在该树上进行查找就蜕变为顺序查找。最好情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度与log2n是等数量级的，所以需要将构造的二叉排序树转换为平衡的二叉排序树，即最佳二叉排序树。

⑷ 以二叉链表作为二叉查找树的存储结构，二叉链表结点的类型定义如下

typedef struct Bitnode

{elemtype elem; /*结点的值域*/ struct Bitnode *lchild, *rchild; /*左、右指针域*/ }Bitree; /*二叉链表结点类型*/

int DelNode(Bitree **t,keytype key)

{ Bitree *p,*q,*s,**f; /* p指针指向待删结点，双亲结点为f*/

int flag=0; p=t;

if (SearchB(*t,&p,&q,kx)) /* 调用二叉查找树查找算法*/ { flag=1; /* 查找成功，置删除成功标志*/ if (p==q) /* 待删结点为根结点*/ f=t;

else /*待删结点为非根结点*/ { f=&(p->lchild); if (kx>p->elem.key)

f=&(p->rchild); /* f指向待删结点的父结点的相应指针域*/ }

if (!q->rchild)

*f=q->lchild; /* 待删结点无右子树，以左子树替换待删除结点*/ else

{ if (!q->lchild)

*f=q->rchild; /*待删结点无左子树，以右子树替换待删除结点*/ else /* 待删结点既有左子树，又有右子树*/ { p=q->rchild; s=p;

while (p->lchild) /* 在右子树上搜索待删结点的后继p*/ { s=p; p=p->lchild; } *f=p;

s->lchild=q->lchild; /* 替换待删结点q，重接左子树*/ if (s != p) /* 待删结点的右孩子有左子树，则要重接右子树*/ { s->lchild=p->rchild; p->rchild=q->rchild; } } } delete q; } return flag; }

⑸ 解 根据题意，平方探测再散列法的下一地址计算公式为： d1=Hash(key)

d2j=(d1+j*j)%m

d2j+1=(d1-j*j)%m; j=1,2,? 计算函数

Hash(19)=19=6 Hash(1)=1=1 Hash(49)=49=10

Hash(23)=23=10 （发生冲突） Hash(23)=(10+1*1)=11

Hash(14)=14=1 （发生冲突） Hash(14)=(1+1*1)=2 Hash(55)=55=3 Hash(20)=20=7

Hash(84)=84=6 （发生冲突） Hash(84)=(6+1*1)=7 (仍发生冲突) Hash(84)=(6-1*1)=5

Hash(27)=27=1 （发生冲突） Hash(27)=(1+1*1)=2 (仍发生冲突) Hash(27)=(1-1*1)=0

Hash(68)=68=3 （发生冲突） Hash(68)=(3+1*1)=4

Hash(11)=11=11 （发生冲突） Hash(11)=(11+1*1)=12

Hash(10)=10=10 （发生冲突） Hash(10)=(10+1*1)=11 (仍发生冲突) Hash(10)=(10-1*1)=9

Hash(77)=77=12 （发生冲突） Hash(77)=(12+1*1)=13

采用开放定址法的平方探测再散列法处理冲突，构造的哈希表如下： 0 27 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 14 55 68 84 19 20 10 49 23 11 77 ⒋ 操作题

(1) 设计在二叉排序树中删除一个结点的算法。要求删除结点后的二叉树仍然有序。 编程提示：

设要删除结点由指针ps指示，其双亲结点由fa指示，并假设被删除结点是其双亲结点的右孩子，删除结点ps的操作是在其左子树中找一个最大结点max，用max替代ps。

void deletenode(Bitree *ps, Bitree *fa) { Bitree q,max;

if (ps->lchild == NULL) max=ps->rchild;

else

if (ps->rchild == NULL) max=p->lchild; else

{ q=ps;

max=q->lchild;

while (max->rchild != NULL) { q=max;

max=q->rchild; }

max->rchild=ps->rchild; if (q != ps)

{ q->rchild=max->lchild; max->lchild=q->lchild; } }

if (ps == fa->lchild) fa->lchild=max; else

fa->rchild=max; free(ps); }

(2) 设计一个用“开放定址法”解决冲突的哈希表上删除一个指定关键字的算法。 编程提示：

设哈希函数为Hash(key)=key % n

开放定址法的线性探测再散列法探测公式为 d0=Hash(key)

di=(di-1+1)% n (0≤i≤n-1)

对于要删除的关键字key，先求出所在的位置，将该位置赋值NULL，然后将后面关联的关键字前移。

void delkey(int Ha[ ], int n, int key) { int h,h0,h1; h=key % n;

while (Ha[h] != key) h=(h+1) % n; Ha[h]=NULL;

while ( h0 != (key%n)) { h=(h0+1)%n; Ha[h1]=Ha[h0]; Ha[h0]=NULL; h1=h0;

h0=(h0+1) % n; } }

else

if (ps->rchild == NULL) max=p->lchild; else

{ q=ps;

max=q->lchild;

while (max->rchild != NULL) { q=max;

max=q->rchild; }

max->rchild=ps->rchild; if (q != ps)

{ q->rchild=max->lchild; max->lchild=q->lchild; } }

if (ps == fa->lchild) fa->lchild=max; else

fa->rchild=max; free(ps); }

(2) 设计一个用“开放定址法”解决冲突的哈希表上删除一个指定关键字的算法。 编程提示：

设哈希函数为Hash(key)=key % n

开放定址法的线性探测再散列法探测公式为 d0=Hash(key)

di=(di-1+1)% n (0≤i≤n-1)

对于要删除的关键字key，先求出所在的位置，将该位置赋值NULL，然后将后面关联的关键字前移。

void delkey(int Ha[ ], int n, int key) { int h,h0,h1; h=key % n;

while (Ha[h] != key) h=(h+1) % n; Ha[h]=NULL;

while ( h0 != (key%n)) { h=(h0+1)%n; Ha[h1]=Ha[h0]; Ha[h0]=NULL; h1=h0;

h0=(h0+1) % n; } }

本文来源：https://www.bwwdw.com/article/ncwx.html