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

…… 此处隐藏：2552字，全部文档内容请下载后查看。喜欢就下载吧 ……