《数据结构 - 用C语言描述》+课后题答案(5)

(2)

AUG

AUG APR R FEB JAN MAR L JUN MAY JUL (一) JAN MAR APR FEB JUN MAY R SEP L OCT JUL （二）

(三)

JAN R AUG MAR R APR FEB JUN OCT JUL MAY SEP NOV MARJAN COT

（四）

ASL=(1*1+2*2+4*3+4*4+1*5)/12=38/12 9.9 10 9.10

AUG JUG MAY SEP FEB APR DEC NOV 50 L 40 10 R 30 (LL型) 40 20 40 40 30 L 50 20 50 R L 10 30 L 55 (RL型) 40 60 90 (LR型) 20 20 55 55 50 60 10 R 30 50 70 30 70 R 60 80 (RR 型) 80 G C I M

（1）插入关键字B后，B-树的结点无变化 G K

A B C I M A B D E H J K N O D E H J L N O

（2）插入关键字L后，结点E 和G产生分裂

（3）插入关键字P后，结点H产生分裂

G K

C I

G K C I M O A B D E H J L N P M O A B D E H J L N P Q

（4）插入关键字Q后，结点不变

A B C G K O I M Q D E H J L N P R

（5）插入关键字R后，三个层次结点产生分裂，使B-树增高 9.11 hegtype hashdelete(hashtable ht,hegtype k)

//ht是拉链法解决冲突的散列表，本算法删除关键字 //为k的指定结点，若删除成功，返回K；否则 //返回null

{设I=H(heg);//I为关键字k用指定哈希函数计算的哈希地址

if(ht[i]=null) {printf(“ 没有关键字k”);return(null);}

else{p=ht[i];pre=p;while(p&&p->data!=k){pre=p;p=p->next;}

if(p= =null){printf(“没有关键字k”);return(null);}

else{pre->next=p->next;free(p);return(k);} }

}//hashdelete 9.12 （1）

0 1 2 3 4 5 6 7 8 9 10 11 12

14 1

01 2

68 1

27 4

55 3

19 1

20 84 79 23 1 3 9 1

11 1

10 3

H(19)=19=6 H(14)=14=1 H(23)=23=10

H(01)=01=1 冲突，2次成功 H(68)=68=3 H(20)=20=7

H(84)=84=6 冲突，3次成功 H(27)=27=1 冲突，4次成功 H(55)=55=3 冲突，3次成功 H(11)=11=11

H(10)=10=10 冲突，3次成功 H(79)=79=1 冲突，9次成功

成功时的平均查找长度=（1*6+1*2+3*3+1*4+1*9）/12=30/12

查找不成功时的平均查找长度=（1+13+12+11+10+9+8+7+6+5+4+3+2+1）/13=92/13 （2）

0 ^ 1 2 ^ 3 4 ^ 5 ^ 6 7 8 ^ 9 ^ 10 11 23 11 ^ 10 ^ 19 20 84 ^ 14 01 27 79 ^ 68 55 ^ 12 ^

查找成功时平均查找长度=（1*6+4*2+1*3+1*4）/12=21/12

查找不成功时的平均查找长度=（1*7+2*2+3*3+1*5）/13=25/13

9.13 各种查找方法均有优点和缺点，不能笼统地说某种方法的好坏。 顺序查找的时间为o（n），在n较小时使用较好，它对数据元素的排列没有要求；二

分查找时间为o（log2n），效率高但它要求数据元素有序排列；散查找时间为o（1），它只能按关键字随机查找（使用散列函数），不能顺序查找，也不能折半查找。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库《数据结构 - 用C语言描述》+课后题答案(5)在线全文阅读。