画出对长度为10的有序表进行折半查找的判定树
1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
2. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。
3.已知如下所示长度为12的表：
（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）
(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，
并求其在等概率的情况下查找成功的平均查找长度。
(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成
功的平均查找长度。
(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长
度。
4. 选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。
5．假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树；
（2）若查找元素54，需依次与哪些元素比较？
（3）若查找元素90，需依次与哪些元素比较？
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
6. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。
K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：
（10，24，32，17，31，30，46，47，40，63，49）
造出Hash表，试回答下列问题：
（1）画出哈希表的示意图；
（2）若查找关键字63，需要依次与哪些关键字进行比较？
（3）若查找关键字60，需要依次与哪些关键字比较？
（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
7. 选取哈希函数Ｈ（key）=key mod 7, 用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。
8. 已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
9．对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，做：
（1）设计哈希函数；（2）画出哈希表；
（3）计算查找成功和查找失败的平均查找长度
10．试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。并请验证你造的哈希表的实际平均查找长度是否满足要求。（CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,W ANG,CAO,YUN,CHANG,YANG）
11. 设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。
（1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。
写出上述各关键字在表中位置。
第九章查找复习题.docx
第九章：查找复习题 一、选择题 1、顺序查找一个共有n个元素的线性表，其时间复杂度为（）,折半査找一个具有n个元素的有序表，其时间复杂度为（）。 A^ 0（n） B、O（log2n） C、0（n2） D、O（nlog2n） 2、在对长度为n的顺序存储的有序表进行折半杏找，对应的折半杳找判定树的高度为（）。 A、n B、［log2nj C、［log2（n+l）J D、rlog2（n+l） 3、采用顺序查找方式查找长度为n的线性表时，平均查找长度为（） A、n B、n/2 C、（n+l）/2 D、（n-l）/2 4、采用折半查找方法检索长度为n的有序表，检索每个元素的平均比较次数（）对应判定树的高度（设高度大于等于2）。 A、小于 B、大于 C、等于 D、大于等于 5、已知有序表（13, 18, 24, 35, 47, 50, 62, 83, 90, 115, 134）,当折半查找值为90 的元素时，杏找成功的比较次数为（）。 A、1 B、2 C、3 D、4 6、对线性表进行折半查找吋，要求线性表必须（）o A、以顺序方式存储 B、以链接方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链接方式存储，且结点按关键字有序排序 7、顺序查找法适合于存储结构为（）的线性表。 A、散列存储 B、顺序或链接存储 C、压缩存储 D、索引存储 8、采用分块查找时，若线性表屮共有625个元素，杏找每个元素的概率相同，假设采用顺序查找來确定结点所在的块时，每块应分（）个结点最佳。 A、10 B、25 C、6 D、625 9、从键盘依次输入关键字的值:t,u,r,b,o,p,a,s,c,l,建立二叉排序树，则其先序遍历序列为（）, 中序遍历序列为（）o A、abcloprstu alcpobsrut C、trbaoclpsu D、trubsaocpl 10、折半查找和二叉排序树的时间性能（）o A、相同 B、不相同 11、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因了均为（），则该树共有（）个结点。 A、2k_I-l B、2k_l C、2k', + l D、2k-l 12、利用逐点插入法建立序列｛50, 72, 43, 85, 75, 20, 35, 45, 65, 30｝对应的二叉排序 树以后，查找元素35要进行（）元索间的比较。 A、4 次 B、5 次 C、7 次 D、10 次 13、设Hash地址空间为0到m-1,哈希函数为h（k）=k%p,为了减少发生冲突的可能性，一 般取p为（）0 A、小于m的最大奇数 B、小于m的最大素数 C、小于m的最大偶数 D、小于m的最大合数。
画出对长度为10的有序表进行折半查找的判定树
第九章 查找 作业： =============================================================================== ◆② 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成 功的平均查找长度。 参考答案： 等概率查找时查找成功的平均查找长度为 ASL succ =(1*1+2*2+3*4+4*3)/10 = 【 ◆③ 已知含12个关键字的有序表及其相应权值为： 优查找树，并计算它的PH 值； ￥ (2)画出对以上有序表进行折半查找的判定树，并计算它的PH 值。 参考答案： (1) < (2) 折半查找的判定树的PH 值为156。 对BCD 调整后的次优查找树：其PH 值为134
《 对次优查找树的调整操作的分析（以下摘自刘文予老师回复邮件） 分析： 什么是次最优并没有一个严格的定义，与我们的实际工程的要求有关。 1. 调整是必须的，否则按书上算法的构造方法构造的查找树离次最优有距离，但是，调整的工作量不能太大，否则，我们可以直接构造最优查找树（用次最优查找树是为了降低构造最优查找树的时间复杂度），显然调整的结果与最优查找树的误差精度与时间复杂度有关，精度越高，时间复杂度越大。书上所说的“适当”比较模糊，没有统一的说法，根据实际的要求选择一个“适当”的调整标准。 2. 书上的参考答案是133，非唯一的标准答案，134也是可取的答案。它是只对根结点进行调整，而书上的方法是对所有的子树的根结点进行调整，显然书上的方法精度更优，但是时间复杂度增大，具体，结果134的方法是O(log2n),书上的方法是O(n*log2n)，但我们注意构造次最优查找树的时间复杂度是O(n*log2n)，即我们对所有的子树的根结点进行调整不会增加构造算法的时间复杂度（会增加一些时间，如增加30％），说明对所有的子树的根结点进行调整是可行的。需强调一点，两种方法都是正确的，没有标准的答案。 检验自己得到的PH 值究竟是不是最小没有意义，最小是最优查找树，已证明不可能在O(n*log2n)的复杂度下构造出。同理，精确的判知哪一步调整哪一步不调整也是没有意义的，我们已有最优的构造算法。但是我们可以讨论几种常用的调整方法以及他们的特点。 \ 3. 我的一些想法 a ）数据结构中的一些问题没有标准答案，需要根据具体的要求进行设计，很多算法时间和空间复杂度是相互制约的，一个减小，另一个会增大，这就需要我们根据实际的情况进行综合设计和平衡。这也是数据结构课程的特点。 b ）算法的复杂度是非常重要的，否则，你不能得出正确的分析结果。 c ）除了上面的2种调整方法，我还可以提出一种新的方法，把根结点与查找树中的最大PH 值结点调整一次，他的时间复杂度是O(n),介于2种方法之间，他的精度是否在2者之间呢你可以研究一下。 d ）学生提的问题很好，如果不是已解答，可以作为考试题让他们分析，我们缺乏这类分析问题的题目！ " ◆④ 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链
画出对长度为10的有序表进行折半查找的判定树
第九章 查找 作业：9.3 9.8 9.31 9.33 =============================================================================== ◆9.3② 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成 功的平均查找长度。 参考答案： 等概率查找时查找成功的平均查找长度为 ASL succ =(1*1+2*2+3*4+4*3)/10 =2.9 ◆9.8③ 已知含12个关键字的有序表及其相应权值为： (1)试按次优查找树的构造算法并加适当调整画出由这12个关键字构造所得的次 优查找树，并计算它的PH 值； (2)画出对以上有序表进行折半查找的判定树，并计算它的PH 值。 参考答案： (1) 次优查找树如下所示，其PH 值为133； (2) 对BCD 调整后的次优查找树：其PH 值为134
对次优查找树的调整操作的分析（以下摘自刘文予老师回复邮件） 分析： 什么是次最优并没有一个严格的定义，与我们的实际工程的要求有关。 1. 调整是必须的，否则按书上算法9.3的构造方法构造的查找树离次最优有距离，但是，调整的工作量不能太大，否则，我们可以直接构造最优查找树（用次最优查找树是为了降低构造最优查找树的时间复杂度），显然调整的结果与最优查找树的误差精度与时间复杂度有关，精度越高，时间复杂度越大。书上所说的“适当”比较模糊，没有统一的说法，根据实际的要求选择一个“适当”的调整标准。 2. 书上的参考答案是133，非唯一的标准答案，134也是可取的答案。它是只对根结点进行调整，而书上的方法是对所有的子树的根结点进行调整，显然书上的方法精度更优，但是时间复杂度增大，具体，结果134的方法是O(log2n),书上的方法是O(n*log2n)，但我们注意构造次最优查找树的时间复杂度是O(n*log2n)，即我们对所有的子树的根结点进行调整不会增加构造算法的时间复杂度（会增加一些时间，如增加30％），说明对所有的子树的根结点进行调整是可行的。需强调一点，两种方法都是正确的，没有标准的答案。检验自己得到的PH值究竟是不是最小没有意义，最小是最优查找树，已证明不可能在O(n*log2n)的复杂度下构造出。同理，精确的判知哪一步调整哪一步不调整也是没有意义的，我们已有最优的构造算法。但是我们可以讨论几种常用的调整方法以及他们的特点。 3. 我的一些想法 a）数据结构中的一些问题没有标准答案，需要根据具体的要求进行设计，很多算法时间和空间复杂度是相互制约的，一个减小，另一个会增大，这就需要我们根据实际的情况进行综合设计和平衡。这也是数据结构课程的特点。 b）算法的复杂度是非常重要的，否则，你不能得出正确的分析结果。 c）除了上面的2种调整方法，我还可以提出一种新的方法，把根结点与查找树中的最大PH值结点调整一次，他的时间复杂度是O(n),介于2种方法之间，他的精度是否在2者之间呢？你可以研究一下。 d）学生提的问题很好，如果不是已解答，可以作为考试题让他们分析，我们缺乏这类分析问题的题目！ ◆9.31④试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 分析： 注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别: “若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树。” 假如你准备写递归形式的算法，则建议你采用如下所述的函数首部，
流程图 决策表 决策树习题及答案
1、已知产品出库管理的过程是：仓库管理员将提货人员的零售出库单上的数据登记到零售出库流水账上，并每天将零售出库流水账上当天按产品名称、规格分别累计的数据记入库存账台。请根据出库管理的过程画出它的业务流图。 产品出库管理业务流图 2、设产品出库量的计算方法是：当库存量大于等于提货量时，以提货量作为出库量；当库存量小于提货量而大于等于提货量的10%时，以实际库存量作为出库量；当库存量小于提货量的10%时，出库量为0（即提货不成功）。请表示出库量计算的决策树。 3、有一工资处理系统，每月根据职工应发的工资计算个人收入所得税，交税额算法如下： 若职工月收入=<800元，不交税； 若800职工<职工月收入=<1300元，则交超过800元工资额的5%；
若超过1300元，则交800到1300元的5%和超过1300元部分 的10%。 试画出计算所得税的决策树和决策表。 1、解：（1）决策树 设X为职工工资，Y为职工应缴税额。 X<=800 ——Y=0 某工资处理系统800
数据结构教程李春葆课后答案第9章查找
第9章 查找 教材中练习题及参考答案 1. 设有5个数据do 、for 、if 、repeat 、while ，它们排在一个有序表中，其查找概率分别是p 1=0.2，p 2=0.15，p 3=0.1，p 4=0.03，p 5=0.01。而查找它们之间不存在数据的概率分别为q 0=0.2，q 1=0.15，q 2=0.1，q 3=0.03，q 4=0.02，q 5=0.01，该有序表如下： （1）试画出对该有序表分别采用顺序查找和折半查找时的判定树。 （2）分别计算顺序查找的查找成功和不成功的平均查找长度。 （3）分别计算折半查找的查找成功和不成功的平均查找长度。 答：（1）对该有序表分别采用顺序查找和折半查找时的判定树分别如图9.2和9.3所示。 （2）对于顺序查找，成功查找到第i 个元素需要i 次比较，不成功查找需要比较的次数为对应外部结点的层次减1： ASL 成功=(1p 1+2p 2+3p 3+4p 4+5p 5)=0.97。 ASL 不成功=(1q 0+2q 1+3q 2+4q 3+5q 4+5q 5)=1.07。 （3）对于折半查找，成功查找需要比较的次数为对应内部结点的层次，不成功查找需要比较的次数为对应外部结点的层次减1： ASL 成功=(1p 3+2(p 1+p 4)+3(p 2+p 5))=1.04。 ASL 不成功=(2 q 0 q 5
图9.3 有序表上折半查找的判定树 2. 对于A [0..10]有序表，在等概率的情况下，求采用折半查找法时成功和不成功的平均查找长度。对于有序表（12，18，24，35，47，50，62，83，90，115，134），当用折半查找法查找 90时，需进行多少次查找可确定成功；查找47时需进行多少次查找可确定成功；查找100时，需进行多少次查找才能确定不成功。 答：对于A [0..10]有序表构造的判定树如图9.4（a ）所示。因此有： ASL 成功= 114 4342211?+?+?+?=3 ASL 不成功= 12 4 834?+?=3.67 对于题中给定的有序表构造的判定树如图9.4（b ）所示。查找 90时，关键字比较次序是50、90，比较2次。查找47时，关键字比较次序是50、24、35、47，比较4次。查找100时，关键字比较次序是50、90、115，比较3次。 图9.4 两棵判定树 3. 有以下查找算法： int fun(int a[],int n,int k) （a ） （b ）
决策树决策表练习
1、某运输公司收取运费的标准如下： ①本地客户每吨5元。 ②外地客户货物重量W在100吨以（含），每吨8元。 ③外地客户货物100吨以上时，距离L在500公里以（含）超过部分每吨增加7元，距离500公里以上时，超过部分每吨再增加10元。 试画出决策树、决策表，反映运费策略。 2、邮寄包裹收费标准如下： 若收件地点在1000公里以，普通件每公斤2元，挂号件每公斤3元；若收件地点在1000公里以外，普通件每公斤2.5元，挂号件每公斤3.5元，若重量大于30公斤，超重部分每公斤加收0.5元。绘制收费标准的决策树和决策表（重量用W表示）。 3、某工厂对一部分职工重新分配工作，其原则如下： 年龄不满20岁，文化程度为小学脱产学习，文化程度是中学的为电工。年龄满20岁但不足50岁，文化程度为小学或中学，男性为钳工，女性为车工；文化程度是大学的为技术员。年龄满50岁及50岁以上，文化程度是小学或中学的为材料员；文化程度是大学的为技术员。请画出处理职工分配政策（以文化程度为基准）的决策表、决策树。
4、某学校对教职工拟定奖励策略如下：(1)高级职称且教学评估优秀的奖励1000元，教学效果评估合格的奖励800元；(2)中级职称且教学评估优秀的奖励800元，教学效果评估合格的奖励500元；(3)初级职称且教学评估优秀的奖励500元。要求画出奖励策略的决策树。 5、某用电量计费系统记费如下：如果按固定价格方法记帐，对耗电量小于100度（不包含100度）的情况，按每月最低费用收费。超过100度时，就按A类计费办法收费。如果按可变价格方法记帐，则对100度以下（不包含100度）耗电量，按A类计费办法收费，超过100度时按B类计费办法收费。画出上述说明的决策树。 6、某金融部门的贷款发放最高限额问题描述如下： 对于固定资产超过500万元（含500万元）的企业：·如果无不良还款记录，低于3年期(含3年)的贷款最高限额为100万元； ·如果有不良还款记录，低于3年期(含3年)的贷款最高限额为50万元。 对于固定资产低于500万元的企业： ·如果无不良还款记录，低于3年期(含3年)的贷款最高限额为60万元；
第九章查找 习题解答
第九章查找 习题解答 9.5 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平 均查找长度。 解：求得的判定树如下： 5 710 9 6 4 3 1 8 2 ASL 成功=（1+2*2+4*3+3*4）/10 =2.9 9.9 已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec ） (1)试按表中元素的顺序依次插入一查初始为空的二叉排序树，画出插入完成之后的二 叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 (2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查 找时查找成功的平均查找长度。 解：（1）求得的二叉排序树如下图所示： Jan Feb Mar Apr Aug Dec June July May Sept Oct Nov 在等概率情况下查找成功的平均查找长度为： ASL 成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5 (2) 分析：对表中元素进行排序后，其实就变成了对长度为12的有序表进行折半查找了，那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求出。 长度为12的有序表进行折半查找的判定树如下图所示：
6 8 12 11 7 5 4 1 9 32 10 所以可求出： ASL 成功=（1+2*2+4*3+5*4）/12=37/12 9.19 选取哈希函数H(k)=(3k) MOD 11。用开放定址法处理冲突，di=i((7k)MOD 10 +1)(i=1,2,3,…)。试在0~10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）造哈希表，并求等概率情况下查找成功时的平均查找长度。 解：因为H(22)=0； H(41)=2； H(53)=5； H(46)=6； H(30)=2；H 1(30)=3； H(13)=6；H 1(13)=8； H(01)=3；H 1(01)=0；H 2(01)=8；H 3(01)=5；H 4（01）=2；H 5(01)=10 H(67)=3；H 1(67)=2；H 2(67)=1 所以：构造的哈希表如下图所示： 并求得等概率情况下查找成功的平均查找长度为： ASL 成功=（1*4+2*2+3+6）/8=17/8 9.21 在地址空间为0~16的散列区中，对以下关键字序列构造两哈希表： （Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec ） (1)用线性探测开放定址法处理冲突； (2)用链地址法处理。 并分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。设哈希函数为H(x)=i/2取整,其中i 为关键字中第一个字母在字母表中的序号。 解：（1）因为： H(Jan)=5; H(Feb)=3; H(Mar)=6; H(Apr)=0; H(May)=6; H 1(May)=7; H(June)=5;H 1(June)=6;H 2(June)=7;H 3(June)=8 H(July)=5;H 1(July)=6;H 2(July)=7;H 3(July)=8;H 4(July)=9; H(Aug)=0; H 1(Aug)=1
画出对长度为10的有序表进行折半查找的判定树
1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 2. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。 3.已知如下所示长度为12的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec） (1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树， 并求其在等概率的情况下查找成功的平均查找长度。 (2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成 功的平均查找长度。 (3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长 度。 4. 选取散列函数H（key）=（3*key）%11，用线性探测法处理冲突，对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。 5．假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树； （2）若查找元素54，需依次与哪些元素比较？ （3）若查找元素90，需依次与哪些元素比较？ （4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
6. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。 K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1）画出哈希表的示意图； （2）若查找关键字63，需要依次与哪些关键字进行比较？ （3）若查找关键字60，需要依次与哪些关键字比较？ （4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 7. 选取哈希函数Ｈ（key）=key mod 7, 用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。 8. 已知长度为11的表（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 9．对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，做： （1）设计哈希函数；（2）画出哈希表； （3）计算查找成功和查找失败的平均查找长度 10．试为下列关键字设计哈希表，要求所设计的表在查找成功时的平均查找长度不超过2.0。并请验证你造的哈希表的实际平均查找长度是否满足要求。（CHA,CAI,LAN,WEN,LONG,ZHAO,WU,LIU,CHEN,LI,W ANG,CAO,YUN,CHANG,YANG） 11. 设a,b,c,d,e五个字符的编码分别为1,2,3,4,5，并设标识符依以下次序出现：ac,bd,aa,be,ab,ad,cd,bc,ae,ce。要求用哈希（Hash）方法将它们存入具有10个位置的表中。 （1）将上述关键字（标识符）构造一个哈希函数，使得发生冲突尽可能地少；（2）线性探测再散列法解决冲突。 写出上述各关键字在表中位置。
上传第9章查找习题
8.1 选择题1．顺序查找法适合于存储结构为（）的线性表。 A）散列存储 B）顺序存储或链接存储C）压缩存储D）索引存储【答案】B 2．下面哪些操作不属于静态查找表（） A）查询某个特定元素是否在表中 B）检索某个特定元素的属性C）插入一个数据元素 D）建立一个查找表【答案】C 3．下面描述不正确的是（）A）顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。B）静态查找表中关键字有序时，可用二分查找。C）分块查找也是一种静态查找表。D）经常进行插入和删除操作时可以采用二分查找。【答案】D 4．散列查找时，解决冲突的方法有（）A）除留余数法B）数字分析法 C）直接定址法 D）链地址法【答案】D 5．若表中的记录顺序存放在一个一维数组中，在等概率情况下顺序查找的平均查找长度为（）2A）O（1） B）O(logn) C）O(n) D）O(n) 2【答案】C 6．对长度为4的顺序表进行查找，若第一个元素的概率为1/8，第二个元素的概率为1/4，第三个元素的概率为3/8，第四个元素的概率为1/4，则查找任一个元素的平均查找长度为（） A）11/8 B） 7/4 C）9/4 D）11/4 【答案】C 【解析】对顺序表查找，ASL＝，代入题目得：
ASL=4*(1/8)+3*(1/4)+2*(3/8)+1*(1/4)=9/4 7．静态查找表与动态查找表二者的根本差别在于（）A）它们的逻辑结构不一样 B）施加在其上的操作不同 C）所包含的数据元素的类型不一样 D）存储实现不一样【答案】B 8．若查找表中的记录按关键字的大小顺序存放在一个一维数组中，在等概率情况下二分法查找的平均检索长度是（）2A）O(n) B）O(logn) C）O(nlogn) D）O((logn)) 222【答案】B 11．请指出在顺序表{2,5,7,10,14,15,18,23,35,41,52}中，用二分法查找关键码12需做（）次关键码比较。 A）2 B）3 C）4 D）5 【答案】C 12．从具有n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为 ( ) 。2 A )O (n) B） O（1）C） O (log n) D）O (n ) 2【答案】C 14．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）个结点最佳。 A）10 B）25 C）6 D）625 【答案】B 15．采用分块查找法（块长为s，以二分查找确定块）查找长度为n的线性表时，每个元素的平均查找长度为（）A）s+n B）logn＋s/2 C）log(n/s+1)+s/2 D）22 (n+s)/2 【答案】C 16．对一棵二叉排序树根结点
习题 查找及其答案
习题9 一、单项选择题 1.若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2.对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为( )的9分之一。 A. 20 B. 18 C. 25 D. 22 3.对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为( )。 A. 3 B. 4 C. 5 D. 6 4.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为( )。 A. 2 B. 3 C. 4 D. 5 5.对具有n个元素的有序表采用折半查找，则算法的时间复杂度为( )。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 6.在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为( )。 A. n+k B. k+n/k C. (k+n/k)/2 D. (k+n/k)/2+1 7.在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。 A. 13 B. 24 C. 12 D. 79 8.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 9.从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 10. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是()。 A. -1~1 B. -2~2 C. 1~2 D. 0~1 11.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为( )。 A. 4 B. 8 C. 12 D. 13 12.若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数( )。 A. 1 B. 2 C. 3 D. 4 13.若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为( )。 A. d B. d+1 C. (d+1)/m D. (d+1)%m
第7章 查找技术习题解析
查找技术-----习题解析课后习题讲解1 1. 填空题 ⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序 ⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。 ⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。 【解答】4 【分析】在折半查找判定树中，第3层共有4个结点。 ⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（）。 【解答】62 【分析】H(48)= H(62)=6 ⑹在散列技术中，处理冲突的两种主要方法是（）和（）。 【解答】开放定址法，拉链法 ⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。 ⑻与其他方法相比，散列查找法的特点是（）。 【解答】通过关键码计算记录的存储地址，并进行一定的比较
2. 选择题 ⑴静态查找与动态查找的根本区别在于（）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 【解答】B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。 ⑵有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。 A s=b B s>b C s查找练习
一、填空题： 1．顺序查找n个元素的顺序表,当使用监视哨时,若查找成功,比较关键字的次数至少为____次,最多为____次；若查找失败,比较关键字的次数为____次。2．折半查找有序表(2,4,6,12,20,28,38,50,70,100),若查找表中元素12,它依次与表中元素___________________比较大小。 二、选择题： 1．折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次与表中元素____进行比较,。 A.65,15,37 B.68,30,37 C.65,15,30 D.65,15,30,37 三、解答题： 1．试按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 将所有元素插入一棵初始为空的二叉排序树中, 使之仍是一棵二叉排序树。 (1)试画出插入完成之后的二叉排序树； (2)若查找元素17,它将依次与二叉排序树中哪些元素比较大小? (3)假设每个元素的查找概率相等,试计算该树的平均查找长度 ASL。 (4)对该树进行中序遍历,试写出中序遍历序列。 假定对20个记录的表作折半查找,(1)试画出描述折半查找过程的判定树；(2)若每个记录的查找概率相等,试计算查找成功时的平均查找长度。 四、执行下面的C程序,指出输出结果。 1． int bin_search(struct arecord r[],int n,k:keytype) /* r[1..n]为n个记录的递增有序表,k为关键字*/ { int low, mid, hig; low = 1; hig = n; /* 各变量初始化*/ while( _____ ) { mid = ___________________; if(k 第八章查找 作业解答 1.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均 查找长度。 解：求得的判定树如下： 5 710 9 6 4 3 1 8 2 ASL 成功=（1+2*2+4*3+3*4）/10 =2.9 2.已知如下所示长度为12的表 （Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec ） (1)试按表中元素的顺序依次插入一查初始为空的二叉排序树，画出插入完成之后的二 叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 (2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查 找时查找成功的平均查找长度。 解：（1）求得的二叉排序树如下图所示： Jan Feb Mar Apr Aug Dec June July May Sept Oct Nov 在等概率情况下查找成功的平均查找长度为： ASL 成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5 (2) 分析：对表中元素进行排序后，其实就变成了对长度为12的有序表进行折半查找了，那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求出。 长度为12的有序表进行折半查找的判定树如下图所示： 6 8 12 11 7 5 4 1 9 32 10 所以可求出： ASL 成功=（1+2*2+4*3+4*4）/12=33/12 3. 基于SeqList 类，设计带监视哨的顺序查找算法，要求把监视哨设置在n 号单元（其 中n 为查找表的表长）。 解： int seqSearchwithGuard(Compareable key) { int n=length(); r[n].setKey(key); //置哨兵 for (i=0; r[i].getKey().coppareTo(key)!=0; i++); if (i==n) return -1; //查找失败 else return i;; //查找成功 } 4. 设散列表的长度为13，散列函数为H(K ）=K%13，给定的关键字序列为: 19，14，23，01，68，20，84，27，55，11，10，79。试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，求这两种方法的查找成功和查找不成功的平均查找长度。 解：（1）用拉链法处理冲突： 因为：H(19)=6；H(14)=1;H(23)=10;H(01)=1;H(68)=3;H(20)=7; H(84)=6;H(27)=1;H(55)=3;H(11)=11;H(10)=10;H(79)=1 所以，构造的哈希表如下图所示： 0 1 2 3 4 5 6 7 《数据结构》期末复习题及参考答案- 第9章查找 一、选择题 1、适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序B．链接方式存储，元素有序 C．顺序方式存储，元素无序D．顺序方式存储，元素有序 2、对有18个元素的有序表A作折半查找，则查找A[3]的比较序列的下标为（） A.1，2，3 B.9，5，2，3 C.9，5，3 D.9，4，2，3 3、对有14个数据元素的有序表R进行折半搜索，搜索到R[3]的关键字等于给定值，查找 过程中元素比较的顺序依次为（）。 4、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 5、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况 下查找成功所需的平均比较次数为（）。 A．35/12 B.37/12 C.39/12 D.43/12 6、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但 前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减7、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}， 当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。 A.2 B. 3 C. 4 D.12 8、在查找过程中，只完成查找操作，这种查找称为（） A. 静态查找 B.动态查找 C.内部查找 D.外部查找 9、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90） C.（100，60，80，90，120，110，130） D. (100，80，60，90，120，130，110) 二、填空题 1、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找 失败，它们的平均查找长度是不同的，对于查找成功,他们的平均查找长度是相同的。 2、执行顺序查找时，储存方式可以是__顺序存储或链式存储__，二分法查找时，要求线性 表__顺序存储且有序__。 3、在数据结构中一般采用平均查找长度衡量查找算法时间性能，而对于排序算法一班通过 统计记录的比较次数和移动次数衡量排序算法的时间性能。 一、单选题 1．下列查找方法中，不属于动态的查找方法是( )。 A ．二叉排序树法 B ．平衡树法 C ．散列法 D ．二分查找法 2．适用于静态的查找方法为( )。 A ．二分查找、二叉排序树查找 B ．二分查找、索引顺序表查找 C ．二叉排序树查找、索引顺序表查找 D ．二叉排序树查找、散列法查找 3．静态查找表与动态查找表二者的根本差别在于( )。 A ．它们的逻辑结构不一样 B ．施加在其上的操作不同 C ．所包含的数据元素的类型不一样 D ．存储实现不一样 4．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为( )。 A ．5.5 B ．5 C ．39/8 D ．19/4 5．( )存储方式适用于折半查找。 A ．键值有序的单链表 B ．键值有序的顺序表 C ．键值有序的双链表 D ．键值无序的顺序表 6．对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B ．以链接方式存储 C ．顺序存储，且结点按关键字有序排序 D ．链式存储，且结点按关键字有序排序 7．在索引顺序表中查找一个元素，可用的且最快的方法是( )。 A ．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B ．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C ．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D ．用二分查找法确定元素所在块，再用二分查找法在相应块中查找 8．在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。 A ．13 B ．24 C ．12 D ．79 9．由同一关键字集合构造的各棵二叉排序树( )。 A ．形态和平均查找长度都不一定相同 B ．形态不一定相同，但平均查找长度相同 C ．形态和平均查找长度都相同 D ．形态相同，但平均查找长度不一定相同 10．对二叉排序树进行( )，可以得到各结点键值的递增序列。 A ．先根遍历 B ．中根遍历 C ．层次遍历 D ．后根遍历 11．下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序列？ A ．2，25，40，39，53，34，35 B ．25，39，2，40，53，34，35 C ．53，40，2，25，34，39，35 D ．39，25，40，53，34，2，35 12．在A VL 树中，每个结点的平衡因子的取值范围是( )。 A ．-1~1 B ．-2~2 C ．1~2 D ．0~1 13．在AVL 树中，任一结点的( )。 A ．左、右子树的高度均相同 B ．左、右子树高度差的绝对值不超过1 C ．左、右子树的结点数均相同 D ．左、右子树结点数差的绝对值不超过1 14．下面关于B 树和B +树的叙述中，不正确的是 A ．都是平衡的多叉树 B ．都是可用于文件的索引结构 C ．都能有效地支持顺序检索 D ．都能有效地支持随机检索 15．右图是一棵( )。 2822221915100528 2610 查找技术-----习题解析课后习题讲解 1 1. 填空题 ⑴顺序查找技术适合于存储结构为（）的线性表，而折半查找技术适用于存储结构为（）的线性表，并且表中的元素必须是（）。 【解答】顺序存储和链接存储，顺序存储，按关键码有序 ⑵设有一个已按各元素值排好序的线性表，长度为125，用折半查找与给定值相等的元素，若查找成功，则至少需要比较（）次，至多需比较（）次。 【解答】1，7 【分析】在折半查找判定树中，查找成功的情况下，和根结点的比较次数最少，为1次，最多不超过判定树的深度。 ⑷长度为20的有序表采用折半查找，共有（）个元素的查找长度为3。 【解答】4 【分析】在折半查找判定树中，第3层共有4个结点。 ⑸假定一个数列{25，43，62，31，48，56}，采用的散列函数为H(k)=k mod 7，则元素48的同义词是（）。 【解答】62 【分析】H(48)= H(62)=6 ⑹在散列技术中，处理冲突的两种主要方法是（）和（）。 【解答】开放定址法，拉链法 ⑺在各种查找方法中，平均查找长度与结点个数无关的查找方法是（）。 【解答】散列查找 【分析】散列表的平均查找长度是装填因子的函数，而不是记录个数n的函数。 ⑻与其他方法相比，散列查找法的特点是（）。 【解答】通过关键码计算记录的存储地址，并进行一定的比较 2. 选择题 ⑴静态查找与动态查找的根本区别在于（）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 【解答】B 【分析】静态查找不涉及插入和删除操作，而动态查找涉及插入和删除操作。 ⑵有一个按元素值排好序的顺序表（长度大于2），分别用顺序查找和折半查找与给定值相等的元素，比较次数分别是s和b，在查找成功的情况下，s和b的关系是（）；在查找不成功的情况下，s和b的关系是（）。 A s=b B s>b C s第八章查找补充作业解答(Java版)
《数据结构》期末复习题及参考答案 - 第9章 查找【HSH2013级】给学生
数据结构第8章查找练习题
第7章 查找技术习题解析