(完整word版)练习题8参考答案(word文档良心出品)

1、3.简答题（1）简述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求。对长度 为n的表来说，三种查找法在查找成功时的平均查找长度各是多少？答：三种方法对查找的要求分别如下。 顺序查找法：表中元素可以任意次序存放。 折半查找法：表中元素必须按关键字递增或递减排列，且最好采用顺序存储结构。 分块查找法：表中元素每块内的元素可以任意次序存放，但块与块之间必须以关键 字的大小递增（或递减）排列，即前一块内所有元素的关键字都不能大（或小）于后一块内 任何元素的关键字。三种方法的平均查找长度分别如下。顺序查找法：折半查找法：（n+1）/2。log2（ n+1）-1。若用顺序查找确定所在的块，平均

2、查找长度为:查找成功的平均查找长度为查找成功的平均查找长度为-（-+s）+1 ;若用二 2 s分查找确定所在块，平均查找长度为log2（-+1）+-。其中，s为每块含有的元素个数。s 2（2）折半查找适不适合链表结构的序列，为什么？用折半查找的查找速度必然比线性 查找的速度快，这种说法对吗？答：不适合。虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其 存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。折半查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。（3）给定关键字序列为3,5,7,9,11

3、,13,15,17，回答以下问题：按表中元素的顺序依次插入一棵初始值为空的二叉排序树。画出插入完成后的二叉 排序树，并求其在等概率情况下查找成功的平均查找长度。答： 按输入顺序构造的二叉排序树如图8.1所示。在等概率情况下查找成功的平均查找长度为：1+2 +3 +4 +5 +6 +7 +8ASLsucc=4.5分块查找法:8由此可见在同样序列的查找中, 率要高。平衡二叉树比二叉排序树的平均查找长度要小,查找效图8.1一棵二叉排序树图8.2 一棵平衡二叉树（4）输入一个正整数序列40,28,6,72,100,3,54,1,80,91,38,建立一棵二叉排序树,然后删除结点72,分别画出该二叉树及

4、删除结点72后的二叉树。答：构造的二叉排序树如图8.3所示。为了删除结点72,在其左子树中找到最大结点，用其代替结点72。删除之后的二叉排序树如图8.4所示。二叉排序树图8.354 (只有一个结点)删除72后的二叉排序树图8.4(6) 对一个固定的数据集，用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么？如果要求时间复杂度更小，你采用什么方法？此方法的时间复杂度是多少？答：查找某个元素的时间复杂度下限，如果理解为最短查找时间， 则当关键字值与表头元素相同时，比较 1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是 0(1)。(7

5、) 设有一组关键字19,01,23,14,55,20,84,27,68,11,10,77，采用哈希函数： H(key)=key % 13采用开放地址法的线性探测法解决冲突，试在018的哈希地址空间中对该关键字序列构造哈希表，并求成功和不成功情况下的平均查找长度。解：依题意，m=19，线性探测法计算下一地址计算公式为：d1 =H(key)dj+1 =(d j+1) % m; j=1, 2,.其计算函数如下：H(19)=19 mod 13=6H(01)=01 mod 13=1H(23)=23 mod 13=10H(14)=14 mod 13=1冲突H(14)=(1+1) mod 19 =2H(55

6、)=55 mod 13=3H(20)=20 mod 13=7H(84)=84 mod 13=6冲突H(84)=(6+1) mod 19=7仍冲突H(84)=(7+1) mod 19=8H(27)=27 mod 13=1冲突H(27)=(1+1) mod 19=2冲突H(27)=(2+1) mod 19=3仍冲突H(27)=(3+1) mod 19=4H(68)=68 mod 13=3冲突H(68)=(3+1) mod 19=4仍冲突H(68)=(4+1) mod 19=5H(11)=11 mod 13=11H(10)=10 mod 13=10冲突H(10)=(10+1) mod 19=11仍冲

7、突H(10)=(11+1) mod 19=12冲突H(77)=77 mod 13=12H(77)=(12+1) mod 19=13因此，构建的哈希表如表8.1所示。表8.1 哈希表下标0123456789101112131415161718k011455276819208423111077探测次数121431131132ASL 成功=(1+2+1+4+3+1+1+3+1+1+3+2)/12=23/12ASL 不成功=(1+9+8+7+6+5+4+3+2+1+5+4+3)/13=58/13(8) 线性表的关键字集合87,25,310,08,27,132,68,95,187,123,70,63,4

8、7，共有 13 个元素, 已知哈希函数为：H(k) = k mod 13采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功和不成功情况下的平均 查找长度。解：依题意，得到：H(87)=87 mod 13=9H(25)=25 mod 13=12H(310)=310 mod 13=11H(08)=08 mod 13=8H(27)=27 mod 13=1H(132)=132 mod 13=2H(68)=68 mod 13=3H(95)=95 mod 13=4H(187)=187 mod 13=5H(123)=123 mod 13=6H(70)=70 mod 13=5H(63)=63 mod 1

9、3=11H(47)=47 mod 13=8采用拉链法处理冲突的哈希表如图8.7所示。成功查找的平均查找长度:ASL 成功=(1 >10+2 X3)/10=1.6ASL 不成功=(1 >+2 X3)/13=127A132A68A95A70123A10 11 12图8.7采用拉链法处理冲突的哈希表值。4. 算法设计题(1)对含有n个元素的整型数组 A,设计一个较优的算法同时找最大元素和最小元素。 解：通过一趟扫描并比较，可以找出最大元素max和最小元素 min。对应的算法如下:void MaxMin(int A,int n,int &min,int &max)int i

10、;min=max=A0;for (i=1;i<n;i+) if (Ri<min) min=Ri;else if (Ri>max) max=Ri;( 2)设计二分查找的递归算法。 解： 对应的递归算法如下：int BinSearch1( SqType R,KeyType k,int low,int high) int mid;if (low>high) return(-1);elsemid=(low+high)/2;if (k=Rmid.key)return(mid);else if (k>Rmid.key)return(BinSearch1(R,k,mid+1,h

11、igh);/ elsereturn(BinSearch1(R,k,low,mid-1); /在左子树中递归查找在右子树中递归查找3)假设二叉排序树 bt 的各元素值均不相同， 设计一个算法按递增次序输出所有结点解： 按中序序列遍历二叉排序树即按递增次序遍历，对应值的算法如下：void incrorder( BSTNode *bt)if (bt!=NULL)incrorder(bt->lchild); printf("%d ",bt->data); incrorder(bt->rchild);k 的关键字。左子树中所有结点( 4)设计一个递归算法，从大到小输

12、出二叉排序树中所有其值不小于 解：由二又排序树的性质可知， 右子树中所有结点值大于根结点值， 值小于根结点值。为了从大到小输出，要先遍历右子树，再访问根结点，后遍历左子树。对 应的算法如下：void Output( BSTNode *bt,KeyType k) if (bt!=NULL) Output(bt->rchild,k);if (bt->key>=k) printf("%d ",bt->key);Output(bt->lchild,k);(5)假设二叉排序树中所有结点关键字不同，设计一个算法，求出指定关键字的结点 所在的层次。解：设二叉

13、排序树采用二叉链存储结构。 找层次。对应的算法如下：BSTNode *bt, KeyType k)采用二叉排序树非递归查找算法， 用 h 保存查int level( int h=0;if (bt!=NULL)h+;while (bt->data!=k) if (k<bt->data) bt=bt->lchild;else/在左子树中查找bt=bt->rchild;h+;return h;/在右子树中查找层数增 1机实验题假设二叉树的数据域为 int 类型，由其括号表示建立对应的二叉链存储结构，设计一个 算法判断该二叉树是否为一棵二叉排序树。并用相关数据进行测试。解

14、：结合第 6 章的二叉树基本运算算法和二叉排序树的特点设计对应的程序如下：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef int ElemType; typedef struct tnode ElemType data;struct tnode *lchild,*rchild; BTNode ;BTNode *pre=NULL;/二叉树的 data 域设为 int 类型int judgeBST( BTNode *bt) int b1,b2;if (bt=NULL)return 1;else数

15、据域指针域二叉树结点类型/pre 为全局变量 , 保存当前结点中序前驱结点地址 , 初值为 NULL判断二叉树 bt 是否是一棵二叉排序树/空树是 BST b1=judgeBST(bt->lchild);if (b1=0) return 0;if (pre!=NULL && pre->data>=bt->data) return 0;pre=bt;b2=judgeBST(bt->rchild);return b2;/左子树不是 BST, 整个二叉树也不是 BST/pre 指向当前访问的结点 / 判断右子树是否为 BST / 返回右子树的判断结果vo

16、id CreateBTree(BTNode * &bt,char *str) BTNode *StMaxSize,*p=NULL; ElemType d; int top=-1,k,j=0; char ch; bt=NULL; ch=strj; while (ch!='0') / 建立的二叉树初始时为空/str未扫描完时循环/由str建立二叉链btswitch(ch)case '(':top+;Sttop=p; k=1; break;case ')':top-;break; case ',':k=2; break; def

17、ault:/为'(',其后结点为栈顶结点的左孩子当前子树结束 其后结点为栈顶结点的右孩子为')',为',',为数字符 , 提取数字并建相应的结点d=0;while (strj>='0' && strj<='9')/strj 为数字符 , 将数字串转换成数值 d d*=10;d+=strj-'0'j+;j-;p=(BTNode *)malloc(sizeof(BTNode); p->data=d; p->lchild=p->rchild=NULL; if

18、(bt=NULL)bt=p;else/ 后退一个字符/*p 为二叉树的根结点/ 已建立二叉树根结点 switch(k)case 1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;break;break;j+;ch=strj;void DestroyBTree(if (bt!=NULL)DestroyBTree(bt->lchild);DestroyBTree(bt->rchild); free(bt);BTNode *&bt)/销毁二叉树BTNode *bt)void DispBTree( if (bt!=NULL) printf("%d",bt->data);if (bt->lchild!=NULL | bt->rchild!=NULL)/输出二叉树printf("(");DispBTree(bt->lchild); if (bt->rchild!=NULL) printf(",");DispBTree(bt->rchild); printf(")");/有子树时输入 '(' 递归处理左子树 有右子树时输入 '.'递归处理