9.1 用序列（46，88，45，39，70，58，101，10，66，34）建立一棵二叉排序树，画出此树，并求在等概率情况下查找成功时的平均查找长度。
9.2 给定一组关键字K={4，5，2，3，6，1}，试按二叉排序树生成规则画出这棵二叉排序树，并说明用这组关键字以不同的次序输入后建立起来的二叉排序树的形态是否相同？当以中序遍历这些二叉排序树时，其遍历结果是否一样？为什么？
9.3 设有二叉排序树如图9-1，画出依次插入8、3后的情形。
9-1
9.4 设有二叉排序树如图9-1，画出依次删除5、9后的情形。
9.5 设散列表的地址范围是[0…9]，散列函数为H(key)=(key2+2) Mod 9，并采用链表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。
9.6 已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H(Key)=key mod 7，若发生冲突采用线性探测法处理，要求：
（1）计算每一个元素的散列地址，并在下图中填写出散列表。
0 1 2 3 4 5 6
（2）求出在查找每一个元素概率相等的情况下的平均查找长度。
9.7假定对有序表：(3，4，5，7，24，30，42，54，63，70，87，95)进行折半查找，试回答下列问题：(1) 画出描述折半查找过程的判定树；(2) 若查找元素54，需依次与哪些元素比较？(3) 若查找元素90，需依次与哪些元素比较？(4) 假定每个元素的查找概率相等，求查找成功时的平均查找长度。
9.8 给出一个线性表D=(6，87，155，188，220，465，505，511，
586，656，670，766，897，908)共14个元素，给出用二分法查找586，填写下列表格表示查找过程。
第九章财产清查 该练习根据李建丽同学的作业进行修改，红字部分为修改后的参考答案或解释说明。 一、单项选择题 1.实地盘存制的优点是（ A ）。 A.有利于财产物资的管理 B.可以简化核算 C.能及时提供财产物资的收.发.存信息 D.不必进行定期盘点 2.采用直接转销法核算坏账损失时，应借记（C）。 A.营业外支出 B.管理费用 C.坏账准备 D.应收账款 3.财产物资的经管人员变动时，对这部分财产物资进行的清查属于（B）。 A.全面清查 B.局部清查 C.定期清查 D.资产评估 4.采用永续盘存制，平时对财产物资的记录是（ C ）。 A.只登收入 B.只登发出 C.既要登收入，又要登发出 D.既不登记收入，又不登记发出 5.现金清查采用的方法是（ A ）。 A.实地盘点 B.抽样盘点 C.估算 D.推算 6.企业财产物资的盘存制度有( A )。 A.实地盘存制 B.收付实现制 C.应收应付制 D.平行登记制 7.库存原材料因受自然灾害等非常原因发生损失，应列入（ B ）账户的借方。 A.管理费用 B.营业外支出 C.财务费用 D.其他业务成本 8.实地盘存制和永续盘存制的主要区别是（A）。
A．盘点的方法不同 B．盘点的目标不同 C．盘点的工具不同 D．盘亏处理结果不同 9.一般而言，单位撤销、合并时要进行（ B ）。 A．定期清查 B．全面清查 C．局部清查 D．实地清查 10.对于现金的清查，应将其结果及时填列（ C ）。 A．盘存单 B．实存账存对比表 C．现金盘点报告表 D．对账单 11.银行存款的清查方法是（ C ）。 A．日记账与总分类账核对 B．日记账与收付款凭证核对 C．日记账与对账单核对 D．总分类账与收付款凭证核对 12.对于大量成堆难于清点的财产物资，应采用的清查方法是（D）。 A．实地盘点法 B．抽样盘点法 C．查询核对法 D．技术推算法 13.在记账无误的情况下，造成银行对账单与银行存款日记账不一致的原因是（ C ）。 A．应付账款 B．应收账款 C．未达账项 D．外埠存款 14.实存账存对比表是调整账面记录的（ C ）。 A．记账凭证 B．转账凭证 C．原始凭证 D．累计凭证 15.下列项目的清查应采用询证核对法的是（B）。 A．原材料 B．应付账款 C．实收资本 D．短期投资 16.对于盘亏的固定资产，按照规定程序批准后，应按盘亏固定资产的净值借记的会计科目是（ A ）。 A．待处理财产损溢 B．营业外支出 C．累计折旧
第九章：查找复习题 一、选择题 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的最大合数。
第九章习题 一、选择题 1.以下选项中不能正确把cl定义成结构体变量的是( ) A）typedef struct B）struct color cl { int red; { int red; int green; int green; int blue; int blue; } COLOR; COLOR cl; }; C）struct color D）struct { int red; { int red; int green; int green; int blue; int blue; } cl; } cl; 2.有以下说明和定义语句 struct student { int age; char num[8];}; struct student stu[3]={{20,"200401"},{21,"200402"},{10\9,"200403"}}; struct student *p=stu; 以下选项中引用结构体变量成员的表达式错误的是( ) A) (p++)->num B)p->num C)(*p).num D)stu[3].age 3.有以下结构体说明、变量定义和赋值语句 struct STD {char name[10]; int age; char sex; }s[5],*ps; ps=&s[0]; 则以下scanf函数调用语句中错误引用结构体变量成员的是( )。 A）scanf(“%s”,s[0].name); B）scanf(“%d”,&s[0].age); C）scanf(“%c”,&(ps->sex)); D）scanf(“%d”,ps->age); 4．以下叙述中错误的是（） A）可以通过typedef增加新的类型 B）可以用typedef将已存在的类型用一个新的名字来代表 C）用typedef定义新的类型名后，原有类型名仍有效 D）用typedef可以为各种类型起别名，但不能为变量起别名 5.有以下程序段（） typedef struct node { int data; struct node *next; } *NODE; NODE p;
《数据结构》习题集：第9章_查找 第9章找到 1。如果一个由18个元素组成的有序表被存储在一维数组中，[19]，第一个元素被放入[1]，现在执行二进制搜索，用于寻找[3]的比较序列的下标是()A1，2，3 B，5，2，3 C，5，3 D，4，2，3 2。如果二进制排序树中有n个节点，则二进制排序树中的平均搜索长度为() 2 a . o(1) b . o(log2n) c . o(n) d . o(n)5。如果有序表中有1000个元素，通过二进制搜索找到元素x所需的最大比较次数是()次。A.25b.10c.7d.1 6。顺序搜索的时间复杂度是()a . o(n)b . o(N2)c . o(n1/2)d . o(1 og2n)8。()二叉树可以获得从小到大的有序序列 A。一阶遍历b .中间阶遍历c .后阶遍历d .层次遍历9。将一组初始记录键序列设置为(13，18，24，35，47，50，62，83，90，115，134)，然后通过二分法查找键90时要比较的键的数量为()如果哈希表的长度为100，并且哈希函数H(k)=k% P，那么P通常是最佳选择() a.99 b.97 c.91 d.9311。将键值插入二进制排序树的平均时间复杂度为() a . o(n)b . o(1 og2n)c . o(nlog2n)d . o(N2) 12。如果在顺序表A中有14个元素，[1:14]，在通过二分法寻找元素A[4]的过程中，比较元素的顺序是()A.一个[1)，一个[2)，一个[3)，一个[4)，一个[1)，一个[14)，一个[7)，一个[4] C.A[7]，A[3]，A[5]，A[4] D. A[7]，A[5]，A[3]，a [4] 13。如果哈希表中有m个存储单元，
第九章查找 一、选择题 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为 ( C )。【北京航空航天大学 2000 一、8 （2分）】 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) 【南京理工大学1998一、7（2分）】 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 3. 下面关于二分查找的叙述正确的是 ( D ) 【南京理工大学 1996 一、3 （2分）】 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 4. 对线性表进行二分查找时，要求线性表必须（ B ）【燕山大学 2001 一、5 （2分）】 A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 5．适用于折半查找的表的存储方式及元素排列要求为( D ) 【南京理工大学 1997 一、6 （2分）】 A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 6．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 【南京理工大学 1997 一、7 （2分）】 7．当采用分快查找时，数据的组织方式为 ( B ) 【南京理工大学 1996 一、7 （2分）】 A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 8. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2）C)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 9. 要进行顺序查找，则线性表（1C）；要进行折半查询，则线性表（2D）；若表中元素个数为n,则顺序查找的平均比较次数为 （3G）；折半查找的平均比较次数为（4H）。【北方交通大学 1999 一、2 （4分）】 （1）（2）：A. 必须以顺序方式存储； B. 必须以链式方式存储；C. 既可以以顺序方式存储，也可以链式方式存储； D. 必须以顺序方式存储，且数据已按递增或递减顺序排好； E. 必须以链式方式存储，且数据已按递增或递减的次序排好。 （3）（4）：A.n B.n/2 C.n*n D.n*n/2 E.log2n F.nlog2n G.(n+1)/2 H.log2(n+1) 10．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( A)查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 【西安电子科技大学 2001应用一、8 （2分）】 11. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C ) 【北方交通大学 2000 二、4 （2分）】 A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找 12．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C ) 【合肥工业大学2000一、4（2分）】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) 13. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8， 18，59依次存储到散列表中。 （1）元素59存放在散列表中的【北方交通大学 2001 一、（19，20）（4分）】地址是（ D）。 A． 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（ C ）。 A． 2 B. 3 C. 4 D. 5 14. 将10个元素散列到100000个单元的哈希表中，则（ C ）产生冲突。【北京邮电大学 2001 一、4 （2分）】 A. 一定会 B. 一定不会 C. 仍可能会 15. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key） =key MOD 13,散列地址为1的链中有（D）个记录。【南京理工大学1997 一、4 （2分）】 A．1 B. 2 C. 3 D. 4 16. 下面关于哈希(Hash，杂凑)查找的说法正确的是( C ) 【南京理工大学 1998 一、10 （2分）】
第九章查找 9.25 int Search_Sq(SSTable ST,int key)//在有序表上顺序查找的算法,监视哨设在高下标端 { ST.elem[ST.length+1].key=key; for(i=1;ST.elem[i].key>key;i++); if(i>ST.length||ST.elem[i].key 第九章查找 1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现 进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 2．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A. O(1) B. O(log 2 n) C. O(n) D. O(n2) 5．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 6．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。 A. O(n) B. O(n2) C. O(n1/2) D. O(1og 2 n) 8．（）二叉排序树可以得到一个从小到大的有序序列。 A. 先序遍历 B.中序遍历 C. 后序遍历 D. 层次遍历9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 A. 1 B. 2 C. 3 D. 4 10．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。 A. 99 B. 97 C. 91 D. 93 11．在二叉排序树中插入一个关键字值的平均时间复杂度为（）。 A. O(n) B. O(1og 2n) C. O(nlog 2 n) D. O(n2) 12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。 A. A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D. A[7]，A[5] ，A[3]，A[4] 13．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。 A. 小于等于m的最大奇数 B.小于等于m的最大素数 C. 小于等于m的最大偶数 D. 小于等于m的最大合数 14．设顺序表的长度为n，则顺序查找的平均比较次数为（）。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 15．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 A. 1 B. 2 C. 3 D. 4 17．设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（）。 A. 4 B. 5 C. 6 D. 7 18．二叉排序树中左子树上所有结点的值均（）根结点的值。 A. < B. > C. = D. != 26．对一棵二叉排序树采用中根遍历进行输出的数据一定是（） A.递增或递减序列 B.递减序列 C.无序序列 D.递增 序列 27．一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当 第9章查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。 2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结 点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。 6. 散列法存储的基本思想是由关键字的值决定数据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n 第九章查找 习题解答 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 第九章查找（参考答案） 9.1 int seqsearch( rectype r[], keytype k) // 监视哨设在n个元素的升序顺序表低下标端，顺序查找关键字为k的数据// 元素。若存在，则返回其在顺序表中的位置，否则，返回0 r[0].key=k; i=n; while (r[i].key>k) i--; if (i>0 && r[i].key==k) return(i); else return(0) } // 算法结束 查找过程的判定树是单支树。 查找成功的平均查找长度为 ASL=∑PICI =1/n*∑i = 1/2*(n+1) 查找不成功的平均查找长度为 ASL=1/(n+1)(∑i+(n+1))=(n+2)/2. 9.2 typedef struct lnode {int freq; // 访问频率域 keytype key; // 关键字 ElemType other; struct lnode *prior,*next; // 双向链表 }seqlist; typedef struct snode {int freq; // 访问频率域 keytype key; // 关键字 ElemType other; }snode; void locate(seqlist L,keytype X) // 在链表中查找给定值为X的结点，并保持访问频繁的结点在前 //调用本函数前，各结点的访问频率域（freq）值均为0。 {seqlist *p; // p是工作指针 p=L->next; // p指向第一元素 while (p!=null && p->key!=X) p=p->next; // 查找X结点 if (p==null) {printf(“no X”); return; } else {q=p->prior; // q是p的前驱 p->next->prior=p->prior; // 先将p结点从链表中摘下 q->next=p->next; while (q!=L && q->freq 一、选择题 1、对线性表进行二分查找时，要求线性表必须（） A、以顺序方式存储 B、以链表方式存储 C、以顺序方式存储，且结点按关键字有序排列 D、以链表方式存储，且结点按关键字有序排列 2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（） A、n B、n/2 C、(n+1)/2 D、(n-1)/2 3、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（） A、n2 B、nlog2n C、n D、log2n 4、二分查找和二叉排序树的时间性能（） A、相同 B、不相同 C、有时相同 D、有时不相同 5、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（）次比较后查找成功。 A、1 B、2 C、4 D、8 6、哈希表长m=14，哈希表函数H（key）=key%11，表中已有4个结点：ADDR（15）=4，ADDR（38）=5；ADDR（61）=6；ADDR（84）=7；其余地址为空，如果用二次探测再散列处理冲突，关键字为49的结点的地址是（） A、8 B、3 C、5 D、9 7、一个长度为12的有序表，按二分查找法对该表进行查找，在表内每个元素等概率情况下查找成功所需的平均比较次数（） A、35/12 B、37/12 C、39/12 D、43/12 8、用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）结点最佳。 A、10 B、25 C、6 D、625 9、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（）查找方法。 A、分块 B、顺序 C、二分 D、散列 10、有100个元素，用折半查找法进行查找时，最大比较次数是（） A、25 B、50 C、10 D、7 11、有100个元素，用折半查找法进行查找时，最小比较次数是（） A、7 B、4 C、2 D、1 12、散列函数有一个共同性质，即函数值应当以（）取其值域的每个值。 A、同等概率 B、最大概率 C、最小概率 D、平均概率 13、散列地址空间为0到m-1，k为关键字，用p去除k，将所得的余数作为k的散列地址，即H（k）=k%p。为了减少发生冲突的概率，一般取p为（） A、小于m的最大奇数 B、小于m的最大偶数 C、小于m的最大素数 D、小于m的最大合数 14、顺序存储的表格中有90000个元素，按关键字值额定升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字的值皆不相同，用顺序查找法查找时，平均比较次数约为（C），最大比较次数约为（D） A、25000 B、30000 C、45000 D、90000 二、填空题 1、若有一棵二叉排序树，则按照中序遍历顺序将产生一个（有序）序列 2、顺序查找法的平均查找长度为（(N+1)/2）；二分查找法的平均查找长度为（LOG2N）；分 第九章查找 单项选择题 1.顺序查找法适合于存储结构为的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储 2.对线性表进行二分查找时，要求线性表必须。 A. 以顺序方式存储 B. 以顺序方式存储，且结点按关键字有序排列 C. 以链接方式存储 D. 以链接方式存储，且结点按关键字有序排列 3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为。 A. O(n2) B. O(nlog2n) C. O(n) D. O (logn) 5.二分查找和二叉排序树的时间性能。 A. 相同 B. 不相同 6.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当二分查找值为82的结点时，次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 7.设哈希表长m=14，哈希函数H(key)=key%11。表中有4个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是。 A. 8 B. 3 C. 5 D. 9 8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳地。 A. 10 B. 25 C. 6 D. 625 10.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用查找方法。 A. 分块 B. 顺序 C. 二分 D. 散列 填空题 1.顺序查找法的平均查找长度为；二分查找法的平均查找长度为；分块查找法（以顺序查找确定块）的平均查找长度为；分块查找法（以二分查找确定块）的平均查找长度为；哈希表查找法采用链接法处理冲突时的平均查找长度为。 2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 3.二分查找的存储结构仅限于，且是。 4.在分块查找方法中，首先查找，然后再查找相应的。 5.长度为255的表，采用分块查找法，每块的最佳长度是。 6.在散列函数H(key)=key%p中，p应取。 7.假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为，则 习题9 查找 9.1 单项选择题 1.顺序查找法适合于存储结构为____的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储 2.对线性表进行二分查找时，要求线性表必须____。 A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____. A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。 A．O（n2） B. O(nlog2n) C. O(n) D. O(log2n) 5.二分查找和二叉排序树的时间性能____。 A. 相同 B. 不相同 6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 7.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点： addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7 如用二次探测再散列处理冲突，关键字为49的结点的地址是____。 A. 8 B. 3 C. 5 D. 9 8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 9．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为。 A.从第0个元素往后查找该数据元素 B.从第1个元素往后查找该数据元素 C.从第n个元素往开始前查找该数据元素 D.与查找顺序无关 10．解决散列法中出现的冲突问题常采用的方法是。 A.数字分析法、除余法、平方取中法 B.数字分析法、除余法、线性探测法 C.数字分析法、线性探测法、多重散列法 D.线性探测法、多重散列法、链地址法 11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址。 A.必须大于等于原散列地址 B.必须小于等于原散列地址 C.可以大于或小于但不能等于原散列地址 D.地址大小没有具体限制 12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于。 A.静态查找表 B.动态查找表 C.静态查找表与动态查找表D两种表都不适合 第九章 查找 一、 选择题 1.若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为 ( )。【北京航空航天大学 2000 一、8 （2分）】 A ． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】 A ．（N+1）/2 B. N/2 C. N D. [（1+N ）*N ]/2 3. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 4. 对线性表进行二分查找时，要求线性表必须（ ）【燕山大学 2001 一、5 （2分）】 A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 5．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】 A ．链接方式存储，元素无序 B ．链接方式存储，元素有序 C ．顺序方式存储，元素无序 D ．顺序方式存储，元素有序 6．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A ．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 【南京理工大学 1997 一、7 （2分）】 7．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】 A ．数据分成若干块，每块内数据有序 B ．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 8. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 9. 要进行顺序查找，则线性表（1 ）；要进行折半查询，则线性表（2 ）；若表中元素个数为n,则顺序查找的平均比较次数为（3 ）；折半查找的平均比较次数为（4 ）。【北方交通大学 1999 一、2 （4分）】 （1）（2）：A. 必须以顺序方式存储； B. 必须以链式方式存储；C. 既可以以顺序方式存储，也可以链式方式存储； D. 必须以顺序方式存储，且数据已按递增或递减顺序排好； E. 必须以链式方式存储，且数据已按递增或递减的次序排好。 （3）（4）：A.n B.n/2 C.n*n D.n*n/2 E.log 2n F.nlog 2n G.(n+1)/2 H.log 2(n+1) 10．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 【西安电子科技大学 2001应用 一、8 （2分）】 11. 既希望较快的查找又便于线性表动态变化的查找方法是 ( ) 【北方交通大学 2000 二、4 （2分）】 A ．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找 12．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 【合肥工业大学2000一、4（2分）】 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) 13. 散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。 （1）元素59存放在散列表中的【北方交通大学 2001 一、（19，20） （4分）】地址是（ ）。 A ． 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次数是（ ）。 A ． 2 B. 3 C. 4 D. 5 14. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。【北京邮电大学 2001 一、4 （2分）】 A. 一定会 B. 一定不会 C. 仍可能会 15. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H （key ）=key MOD 13,散列地址为1的链中有（ ）个记录。【南京理工大学 1997 一、4 （2分）】 A ．1 B. 2 C. 3 D. 4 16. 下面关于哈希(Hash ，杂凑)查找的说法正确的是( ) 【南京理工大学 1998 一、10 （2分）】 第九章查找习题 一、判断题 1.折半查找法可以用于按值有序的线性链表的查找。 2.对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的。 3.任一二叉排序树的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。 4.中序遍历二叉排序树的结点就可以得到排好序的结点序列。 5.哈希表存储的基本思想是由关键码的值决定数据的存储地址。 6.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法。 7.装载因子是散列法的一个重要参数，它反映散列表的装满程度。 8.采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置为空，因为这会影响以后的查找。 二、选择题 1.采用顺序查找方法查找长度为n的线性表，平均查找长度为 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2.对线性表采用折半查找法，该线性表必须 A.采用顺序存储结构 B.采用链式存储结构 C.采用顺序存储结构，且元素按值有序 D.采用链式存储结构，且元素按值有序 3.在按值有序的线性表(5,8,11,12,15,20,32,41,57)中采用折半查找法查找20需要进行多少次元素间的比较 A.3 B.4 C.5 D.6 4.按逐点插入法建立对应于序列(54,28,16,34,73,62,95,60,26,43)的二叉排序树后，查找62要进行多少次比较。 A.2次 B.3次 C.5次 D.6次 5.散列法存储的基本思想是根据哪个来决定存储地址。 A.散列表空间 B.元素的序号 C.装载因子 D.关键码值 6.散列法存储的冲突指的是 A.两个元素具有相同的序号 B.两个元素的关键码值不同，而非码属性相同 C.不同关键码值对应相同的存储地址 D. 装载因子过大 7.哈希地址空间为m，k为关键字，散列地址H(k)=k MOD p。为了减少发生冲突的频率，一般取p为 A.小于m的最大奇数 B.小于m的最大合数 C.小于m的最大素数 D.大于m的最小素数 8.在10阶B-树中根结点所包含的关键码 ．．．个数最多为_______，最少为________。 A. 1 B. 2 C. 9 D. 10 9．已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当折半查找值为90的元素时，次比较后查找成功；当折半查找值为47的元素时，次比较后查找成功。《数据结构》习题集：第9章_查找
数据结构 第9章 查找
第九章查找 习题解答
数据结构课后习题答案第九章
数据结构第九章查找练习及答案
第9章 查找练习题及答案
数据结构第9章查找习题
数据结构 第九章查找 习题
第9章查找习题
相关主题
文本预览