第9章 查找习题
第九章查找习题
一、判断题
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的元素时，次比较后查找成功。
A. 1
B. 2
C. 3
D. 4
10.散列函数有一个共同性质，即函数值应当以取其值域的每个值。
A. 最大概率
B. 最小概率
C. 平均概率
D. 同等概率
11．采用线性探测法解决冲突时所产生的一系列后继散列地址（）
A．必须大于等于原散列地址 B . 必须小于等于原散列地址
C．可以大于或小于但不等于原散列地址 D. 对地址在何处没有限制
12．采用链地址法解决冲突时，每一个散列地址所链接的同义词子表各个表项的（）相同。
A．关键字值B．元素值C．散列地址D．含义
13．对长度为n 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为（）。
A．n/2 B．（n+1）/2 C．（n-1）/2 D．n/4
三、填空题
1.对线性表采用折半查找方法，该线性表必须采用______存储结构，并且_______。
2.具有n个结点的判定树的深度h=_______。
3.一个待散列存储的线性表为K=(18,25,63,50,42,32,9)，散列函数为H(k)=k MOD 9，则与线性表中元素18冲突的元素有_______个。
4．假定在有序表A[1..20]上进行折半查找，则比较一次查找成功的结点数为，比较两次查找成功的结点数为，比较三次查找成功的结点数为，比较四次查找成功结点数为，比较五次查找成功的结点数为，平均查找长度为。
5．在散列存储中，装填因子α的值越大，存取元素时发生冲突的可能性就，当α的值越小，存取元素时发生冲突的可能性就。
6. 给定线性表(18,25,63,50,42,32,90)，用散列方式存储，若选用h(K)=K % 9作为散列函数，则元素18的同义词元素共有个，元素25的同义词元素共有个，元素50的同义词元素共有个。
四、问答题
1.设有一个有序文件，其中各记录的关键字为{1,2,3,4,5,6,7,8,9,10,11,12,13,14, 15}，当用折半查找算法查找关键字为3,8,19时，其比较次数分别为多少？
2.假定一个待哈希存储的线性表为{32,75,63,48,94,25,36,18,70}，哈希地址空间为[0…10]，若采用哈希函数H(k)=k MOD 11和线性探测法处理冲突，试给出对应的哈希表，并求出在等概率情况下查找成功时的平均查找长度。
3.设有一个关键码的输入序列{ 55, 31, 11, 37, 46, 73, 63, 02, 07 },
(1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。
(2) 计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。4．设散列表为HT[13], 散列函数为H (key) = key %13。用闭散列法（开放定址法）解决冲突, 对下列关键码序列12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。采用线性探查法寻找下一个空位, 画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。
【解答】
使用散列函数H(key) = key mod 13，有
H(12) = 12, H(23) = 10, H(45) = 6, H(57) = 5,
H(20) = 7, H(03) = 3, H(78) = 0, H(31) = 5,
H(15) = 2, H(36) = 10.
(1) 利用线性探查法造表：
(1) (1) (1) (1) (1) (1) (4) (1) (2) (1) 搜索成功的平均搜索长度为
ASL succ = 1
10(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14
10
第九章 查找 习题（参考答案）
一、判断题
1、否
2、是
3、是
4、是
5、是
6、否
7、是
8、是
二、选择题
1、C
2、C
3、A
4、B
5、D
6、C
7、D
三、填空题
1、顺序 数据有序
2、??1log 2+n
3、2
四、问答题
1. 查找关键字为3时，其比较次数为4
查找关键字为8时，其比较次数为1
查找关键字为19时，其比较次数为4
ASL=2
3. 【解答】
(1) 构造平衡二叉搜索树的过程
(2) 计算在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 ASL succ = (1/9)*(1+2*2+3*4+4*2)=25/9
ASL unsucc = (1/10)*(3*6+4*4)=17/5
右旋 左右旋
91第九章 财产清查练习题、案例参考答案
第九章财产清查 该练习根据李建丽同学的作业进行修改，红字部分为修改后的参考答案或解释说明。 一、单项选择题 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．累计折旧
第九章查找复习题.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的最大合数。
第九章 习题及答案
第九章习题 一、选择题 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章_查找 第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为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 3. 用二分（对半）查找表的元素的速度比用顺序法( ) A．必然快 B. 必然慢 C. 相等 D. 不能确定 4. 具有12个关键字的有序表，折半查找的平均查找长度（） A. 3.1 B. 4 C. 2.5 D. 5 5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失 败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案: A. 相同的 B.不同的 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) 10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 11. 下面关于m阶B-树说法正确的是( ) ①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。 A．①②③ B. ②③ C. ②③④ D. ③ 12. m阶B-树是一棵( ) A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 15. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链 地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个记录。 A．1 B. 2 C. 3 D. 4 16. 关于哈希查找说法不正确的有几个( ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集
《数据结构》习题集：第9章_查找
第九章查找 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 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
第9章 查找练习题及答案
第九章查找 单项选择题 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章查找习题
第九章查找习题 一、判断题 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.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，
第9章习题解答
本章习题解答只给出算法描述，1~8题略。 ⒈画出对长度为18的有序的顺序表进行折半查找时的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 ⒉已知如下所示长度为12的关键字有序的表： {Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec} ⑴试按表中元素的顺序依次插入到一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 ⑵若对表中元素先进行排序构成有序表，求在等概率的情况下查找成功的平均查找长度。 ⑶按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 ⒊试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。 ⒋含有9个叶子结点的3阶B–树中至少有多少个非叶子结点？含有10个叶子结点的3阶B–树中至少有多少个非叶子结点？ ⒌试从空树开始，画出按以下次序向3阶B–树中插入关键码的建树过程：20，30，50，52，60，68，70。如果此后删除50和68，画出每一步执行后3阶B–树的状态。 ⒍在地址空间为0～16的散列区中，对以下关键字序列构造两个哈希表： {Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec} ⑴用线性探测开放地址法处理冲突； ⑵用链地址法处理冲突。 并分别求这两个哈希表在等概率情况下查找成功和不成功的平均查找长度。设哈希函数为H(key) =i/2,其中i为关键字中第一个字母在字母表中的序号。 ⒎哈希函数H(key)=(3*key) % 11。用开放定址法处理冲突，d i=i ((7*key) % 10+1)，i=1,2,3,…。试在0～10的散列地址空间中对关键字序列（22，41，53，46，30， 13，01，67）构造哈希表，并求等概率情况下查找成功时的平均查找长度。 ⒏画出依次插入z，v，o，q，w，y到下图所示的5阶B–树的过程。 ⒐将监测哨设在高下标端，改写教科书上给出的顺序查找算法。并分别求出等概率情况下查找成功和查找失败的平均查找长度。 typedef struct{ KeyType key ; … }ElemType; typedef struct{ ElemType *elem；// elem[1]中存储第一个元素 int length; }S_table ;
第九章查找 习题解答
第九章查找 习题解答 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次更新2019-5)
第9章查找 一、选择题 1.顺序查找一个共有n个元素的线性表，其时间复杂度为（），折半查找一个具有n个元素的有序表，其时间复 杂度为（）。【＊，★】 A.O(n) B. O(log2n) C. O(n2) D. O(nlog2n) 2.在对长度为n的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。【＊，★】 A.n B. C. D. 3.采用顺序查找方式查找长度为n的线性表时，平均查找长度为（）。【＊】 A.n B. n/2 C. (n+1)/2 D. (n-1)/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.对线性表进行折半查找时，要求线性表必须（）。【＊】 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，建立二叉排序树，则其先序遍历序列为（）， 中序遍历序列为（）。【＊＊，★】 A.abcloprstu B. alcpobsrut C. trbaoclpsu D. trubsaocpl 10.折半查找和二叉排序树的时间性能（）。【＊】 A.相同 B. 不相同 11.一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（）个结点。 A.2k-1-1 B. 2k-1 C. 2k-1+1 D. 2k-1 12.利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉排序树以后，查找元素35要
数据结构第9章查找习题
习题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分）】
第九章查找统一作业答案
第九章 查找 作业：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小于调整前的PH值的原因，还不是很清楚。 网上参考答案：无参考答案 ◆9.31④试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 习题集参考答案： 注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别: “若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树。” 假如你准备写递归形式的算法，则建议你采用如下所述的函数首部， bool BiSortTree(BiTree T, BiTree &PRE) 其中PRE为指向当前访问结点的前驱的指针。 网上参考答案： int last=0,flag=1; int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树，是则返回1，否则返回0 { if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data