本文格式为Word版，下载可任意编辑练习题8参考答案 3. 简答题 （1）简述依次查找法、折半查找法和分块查找法对被查找的表中元素的要求对长度为n的表来说，三种查找法在查找告成时的平均查找长度各是多少？ 答：三种方法对查找的要求分别如下 ① 依次查找法：表中元素可以任意次序存放 ② 折半查找法：表中元素务必按关键字递增或递减排列，且最好采用依次存储布局 ③ 分块查找法：表中元素每块内的元素可以任意次序存放，但块与块之间务必以关键字的大小递增（或递减）排列，即前一块内全体元素的关键字都不能大（或小）于后一块内任何元素的关键字 三种方法的平均查找长度分别如下 ① 依次查找法：查找告成的平均查找长度为(n+1)/2 ② 折半查找法：查找告成的平均查找长度为log2(n+1)-1 1n③ 分块查找法：若用依次查找确定所在的块，平均查找长度为：(+s)+1；若用二 2sns分查找确定所在块，平均查找长度为log2(+1)+其中，s为每块含有的元素个数 s2（2）折半查找适不适合链表布局的序列，为什么？用折半查找的查找速度必然比线性查找的速度快，这种说法对吗？ 答：不适合。
虽然有序的单链表的结点是按从小到大（或从大到小）依次排列，但因其存储布局为单链表，查找结点时只能从头指针开头逐步探寻，故不能举行折半查找 折半查找的速度在一般处境下是快些，但在特殊处境下未必快例如所查数据位于首位时，那么线性查找快；而二分查找那么慢得多 （3）给定关键字序列为{3,5,7,9,11,13,15,17}，回复以下问题： ① 按表中元素的依次依次插入一棵初始值为空的二叉排序树画出插入完成后的二叉排序树，并求其在等概率处境下查找告成的平均查找长度 答：① 按输入依次构造的二叉排序树如图8.1所示在等概率处境下查找告成的平均查找长度为： 1?2?3?4?5?6?7?8ASLsucc==4.5 8由此可见在同样序列的查找中，平衡二叉树比二叉排序树的平均查找长度要小，查找效率要高 3 5 7 9 11 13 15 17 57 图8.1 一棵二叉排序树 图8.2 一棵平衡二叉树 （4）输入一个正整数序列{40,28,6,72,100,3,54,1,80,91,38}，建立一棵二叉排序树，然后 删除结点72，分别画出该二叉树及删除结点72后的二叉树。
答：构造的二叉排序树如图8.3所示为了删除结点72，在其左子树中找到最大结点54（只有一个结点），用其代替结点72删除之后的二叉排序树如图8.4所示 28 6 3 1 38 54 40 72 100 80 91 1 3 6 28 38 40 54 100 80 91 图8.3 二叉排序树 图8.4 删除72后的二叉排序树 （6）对一个固定的数据集，用对比两个元素大小的方法在一个给定的序列中查找某个元素的时间繁杂度下限是什么？假设要求时间繁杂度更小，你采用什么方法？此方法的时间繁杂度是多少？ 答：查找某个元素的时间繁杂度下限，假设理解为最短查找时间，那么当关键字值与表头元素一致时，对比1次即可要想降低时间繁杂度，可以改用Hash查找法此方法对表内每个元素的对比次数都是O(1) （7）设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77}，采用哈希函数： H(key)=key % 13 采用开放地址法的线性探测法解决冲突，试在0～18的哈希地址空间中对该关键字序列构造哈希表，并求告成和不告成处境下的平均查找长度。
解：依题意，m=19，线性探测法计算下一地址计算公式为： d1=H(key) dj+1=(dj+1) % m; j=1, 2, ... 其计算函数如下： H(19)=19 mod 13=6 H(01)=01 mod 13=1 H(23)=23 mod 13=10 H(14)=14 mod 13=1 H(14)=(1+1) mod 19 =2 H(55)=55 mod 13=3 H(20)=20 mod 13=7 H(84)=84 mod 13=6 H(84)=(6+1) mod 19=7 H(84)=(7+1) mod 19=8 H(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=4 H(68)=68 mod 13=3 H(68)=(3+1) mod 19=4 H(68)=(4+1) mod 19=5 H(11)=11 mod 13=11 H(10)=10 mod 13=10 H(10)=(11+1) mod 19=12 冲突 仍冲突 H(10)=(10+1) mod 19=11 冲突 仍冲突 冲突 冲突 仍冲突 冲突 仍冲突 冲突 H(77)=77 mod 13=12 H(77)=(12+1) mod 19=13 冲突 因此，构建的哈希表如表8.1所示。
表8.1 哈希表 下标 k 探测次数 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 23 11 10 77 1 1 3 2 01 14 55 27 68 19 20 84 1 2 1 4 3 1 1 3 ASL告成=(1+2+1+4+3+1+1+3+1+1+3+2)/12=23/12 ASL不告成=(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,47}，共有13个元素，已知哈希函数为： H(k) = k mod 13 采用拉链法处理冲突设计出这种链表布局，并计算该表的告成和不告成处境下的平均查找长度 解：依题意，得到： H(87)=87 mod 13=9 H(25)=25 mod 13=12 H(310)=310 mod 13=11 H(08)=08 mod 13=8 H(27)=27 mod 13=1 H(132)=132 mod 13=2 H(68)=68 mod 13=3 H(95)=95 mod 13=4 H(187)=187 mod 13=5 H(123)=123 mod 13=6 H(70)=70 mod 13=5 H(63)=63 mod 13=11 H(47)=47 mod 13=8 采用拉链法处理冲突的哈希表如图8.7所示。
告成查找的平均查找长度： ASL告成=(1×10+2×3)/10=1.6 ASL不告成=(1×7+2×3)/13=1 0 ^ 1 2 3 4 5 6 8 9 27 ^ 132 ^ 68 ^ 95 ^ 70 187 ^ 123 ^ 08 47 ^ 7 ^ 87 ^ 63 310 ^ 10 ^ 11 12 25 ^ 图8.7 采用拉链法处理冲突的哈希表 4. 算法设计题 （1）对含有n个元素的整型数组A，设计一个较优的算法同时找最大元素和最小元素 解：通过一趟扫描并对比，可以找出最大元素max和最小元素min对应的算法如下： void MaxMin(int A[],int n,int min=max=A[0]; for (i=1;imax) （2）设计二分查找的递归算法 解：对应的递归算法如下： int BinSearch1(SqType R[],KeyType k,int low,int high) { } int mid; if (low>high) { } return(-1); mid=(low+high)/2; if (k==R[mid].key) return(mid); return(BinSearch1(R,k,mid+1,high));//在左子树中递归查找 return(BinSearch1(R,k,low,mid-1)); //在右子树中递归查找 else if (k>R[mid].key) else else （3）假设二叉排序树bt的各元素值均不一致，设计一个算法按递增次序输出全体结点值。
解：按中序序列遍历二叉排序树即按递增次序遍历，对应值的算法如下： void incrorder(BSTNode *bt) { } if (bt!=NULL) { } incrorder(bt->lchild); printf(\incrorder(bt->rchild); （4）设计一个递归算法，从大到小输出二叉排序树中全体其值不小于k的关键字 解：由二又排序树的性质可知，右子树中全体结点值大于根结点值，左子树中全体结点值小于根结点值为了从大到小输出，要先遍历右子树，再访问根结点，后遍历左子树对应的算法如下： void Output(BSTNode *bt,KeyType k) { if (bt!=NULL) { Output(bt->rchild,k); if (bt->key>=k) printf(\Output(bt->lchild,k); } } （5）假设二叉排序树中全体结点关键字不同，设计一个算法，求出指定关键字的结点所在的层次 解：设二叉排序树采用二叉链存储布局采用二叉排序树非递归查找算法，用h保存查找层次。
对应的算法如下： int level(BSTNode *bt, KeyType k) { } int h=0; if (bt!=NULL) { } h++; while (bt->data!=k) { } return h; if (kdata) bt=bt->lchild; bt=bt->rchild; //在左子树中查找 //在右子树中查找 //层数增1 else h++; 上机测验题8 假设二叉树的数据域为int类型，由其括号表示建立对应的二叉链存储布局，设计一个算法判断该二叉树是否为一棵二叉排序树并用相关数据举行测试 解：结合第6章的二叉树根本运算算法和二叉排序树的特点设计对应的程序如下： #include #include #define MaxSize 100 typedef int ElemType; typedef struct tnode { ElemType data; //数据域 //二叉树结点类型 //判断二叉树bt是否是一棵二叉排序树 //空树。