练习题8参考答案
更新时间:2024-01-01 18:23:01 阅读量: 教育文库 文档下载
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,int &max) { }
int i;
min=max=A[0]; for (i=1;i if (R[i] min=R[i]; max=R[i]; else if (R[i]>max) (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 (k bt=bt->lchild; bt=bt->rchild; //在左子树中查找 //在右子树中查找 //层数增1 else h++; 上机实验题8 假设二叉树的数据域为int类型,由其括号表示建立对应的二叉链存储结构,设计一个算法判断该二叉树是否为一棵二叉排序树。并用相关数据进行测试。 解:结合第6章的二叉树基本运算算法和二叉排序树的特点设计对应的程序如下: #include ElemType data; //数据域 //二叉树结点类型 //判断二叉树bt是否是一棵二叉排序树 //空树是BST struct tnode *lchild,*rchild; //指针域 //二叉树的data域设为int类型 } BTNode; BTNode *pre=NULL; //pre为全局变量,保存当前结点中序前驱结点地址,初值为NULL int judgeBST(BTNode *bt) { int b1,b2; if (bt==NULL) { return 1; b1=judgeBST(bt->lchild); if (b1==0) return 0; return 0; //pre指向当前访问的结点 //判断右子树是否为BST //返回右子树的判断结果 //左子树不是BST,整个二叉树也不是BST else if (pre!=NULL && pre->data>=bt->data) pre=bt; b2=judgeBST(bt->rchild); return b2;
正在阅读:
练习题8参考答案01-01
扎实推进落实岗位责任制04-19
《数字逻辑电路》期末考试试题03-01
海滩风光作文400字07-16
单片机实验指导书04-30
结构设计说明书05-07
人教版小学语文教材目录04-16
转供电协议书03-08
语音识别简介 10-02
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 练习题
- 答案
- 参考
- php基础知识笔记
- 新加坡与上海国际航运中心所得税制度的比较与借鉴
- 最新审定人教版一年级上册数学期末检测试卷(3)
- 北京理工大学珠海学院 08级 概率论与数理统计综合检测题(含答案)
- 超市店长竞聘书范文(共4篇)
- 职业教育和成人教育工作情况汇报范文四篇
- 读《红与黑》有感
- 新版室内厚型钢结构防火涂料施工工艺
- 韦博外贸英语邮件范文:商务谈判
- 教育法律法规试题及答案
- XK31CB1说明书 - 图文
- 汽车理论第五版 - 课后习题答案(正确)(1)
- 数星星的孩子
- 雷雨
- 二年级上美术教案奇妙的电话机 - 人教新课标
- 轧钢高线车间工艺操作规程
- 光的反射 折射练习题及答案
- 2015年高二数学选修2-1同步模块综合测试题3套(人教版带答案和解释)
- 2012年度述职报告-品管部
- 2015—2016专业技术人员心理健康与心理调适公需科目考试答案