还剩7页未读，继续阅读
文本内容:
第九章查找
一、选择题
1.若查找每一个记录的概率均等，则在具有D个记录的连续顺叙文件中采用顺序查找法查找个记录，其平均查找长度ASL为（）A.（n-l）/2B.n/2C.（n+l）/2D.n
2.下面关于二分查找的叙述正确的是（）A.表必须有序，表可以顺序方式存储，也可以链表方式存储C,表必须有序，而且只能从小到大罗列B.表必须有序且表中数据必须是整型，实型或者字符型D.表必须有序，且表只能以顺序方式存储
3.用二分（对半）查找表的元素的速度比用顺序法（）A.必然快B.必然慢C,相等D.不能确定
4.具有12个关键字的有序表，折半查找的平均查找长度（）A.
3.1B.4C.
2.5D.
55.当采用分块查找时，数据的组织方式为（）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或者最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或者最小）的数据组成索引块D.数据分成若干块，每块（除最后一块外）中数据个数需相同
6.二叉查找树的查找效率与二叉树的（
（1））有关，在（
（2））时其查找效率最低
（1）A.高度B.结点的多少C.树型D.结点的位置
（2）:A.结点太多B.彻底二叉树C.呈单枝树D.结点太复杂
7.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败，它们的平均查找长度是（（D）,对于查找成功，他们的平均查找长度是（
（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 MOD13,散列地址为1的链中有（）个记录A.1B.2C.3D.
416.关于哈希查找说法不正确的有儿个（）
（1）采用链地址法解决冲突时，查找一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
（3）用链地址法解决冲突易引起会萃现象
（4）再哈希法不易产生会萃A.1B.2C.3D.
417.设哈希表长为14,哈希函数是H（key）二key%ll,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）A.8B.3C.5D.
918.假定哈希查找中k个关键字具有同一哈希值，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？（）A.k-1次B.k次C.k+1次D.k（k+1）/2次
19.好的哈希函数有一个共同的性质，即函数值应当以（）取其值域的每一个值A.最大概率B.最小概率C.平均概率D.同等概率
20.将10个元素散列到100000个单元的哈希表中，则（）产生冲突A.一定会B.-*定不会C.仍可能会
二、判断题
1.采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找（）
2.在散列检索中，“比较”操作普通也是不可避免的（）
3.Hash表的平均查找长度与处理冲突的方法无关（）
4.散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大（）
5.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关（）
6.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（）
7.最佳二叉树是AVL树（平衡二叉树）（）
8.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（）
9.二叉树中除叶结点外，任一结点X,其左子树根结点的值小于该结点（X）的值；其右子树根结点的值2该结点（X）的值，则此二叉树一定是二叉排序树（）
10.有n个数存放在一维数组A[L,n]中，在进行顺序查找时，这n个数的罗列有序或者无序其平均查找长度不同（）
11.N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的（）
12.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同（）
13.B-树中所有结点的平衡因子都为零（）
14.在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转（）
三、填空题1,顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为________次；当使用监视哨时，若查找失败，则比较关键字的次数为——
2.在有序表A[L.12]中，采用二分查找算法查等于A
[12]的元素，所比较的元素下标挨次为O
3.在有序表A[L.20]中，按二分查找方法进行查找，查找长度为5的元素个数是
4.高度为4（含叶子结点层）的3阶b-树中，最多有个关键字
5.在一棵ni阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______________；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个薮是o
6.在哈希函数H（key）二key%p中，p值最好取
8.如果按关键码值递增的顺序挨次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为o
9.如果关键码按值排序，而后用二分法挨次检索这些关键码，并把检索中遇到的在二叉树中没有浮现的关键码挨次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为O提示此时二叉排序树与折半查找的二叉判定树一样了
10.平衡因子的定义是__________________________________________________________
11.查找是非数值程序设计的一个重要技术问题，基本上分成—1—查找，—2—查找和⑶查找处理哈希冲突的方法有—4_5_61和__7L o
12.具有N个关键字的B树的查找路径长度不会大于o在一棵有N个结点的非平衡二叉树中进行查找，平均时间复杂度的上限即最坏情况平均时间复杂度为
13.高度为5除叶子层之外的三阶B-树至少有个结点
452414.可以惟一的标识一个记录的关键字称为o
15.动态查找表和静态查找表的重要区别在于前者包含有和运算，而后者不包含这两种运算
16.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分折半查找方法统计成绩大于或者等于X分的学生人数，请填空使之完善提示这时需要找的是最后一个大于等于X的下标，若查找成功其下标若为m,则有m个学生成绩大于或者等于X,若查找不成功，若这时low所指向的值小于X,则有lowT个学生成绩大于或者等于X,注意这时表中可能不止一个数值为X的值，这时我们要查找的是下标最大的^define N/*学生人数*/int uprxinta[N],int x/*函数返回大于等于X分的学生人数*/{int low=l,mid,high=N;do{mid=low+high/2;if x=a[mid]⑴else2;}while_3_;if a[low]x return low-1;returnlow;}
四、应用题
1.名词解释哈希表叙述B-树定义，主要用途是什么？平衡二叉树AVL树平衡因子平均查找长度ASL3设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数II key二key mod7,表长为10,用开放地址法的二次探测再散列方法解决冲突Hi=Hkey+di mod10di=12,22,要求3,-,O2对该关键字序列构造哈希表，并确定其装填因子，查找成功所需的平均探查次数
4.设一组数据为{1,14,27,29,55,68,10,11,23},现采用的哈希函数是Hkey二key MOD13,即关键字对13取模，冲突用链地址法解决，设哈希表的大小为
130.・12,试画出插入上述数据后的哈希表
7.设有一棵空的3阶B-树，挨次插入关键字30,20,10,40,80,58,47,50,29,22,56,98,99,请画出该树9,已知2棵2-3B-树如下省略外结点3121对树a,请分别画出先后插入26,85两个新结点后的树形；2对树b，请分别画出先后删除53,37两个结点后的树形6190^£2/Go\!2yb
10.输入一个正整数序列53,17,12,66,58,70,87,25,56,60,试完成下列各题1按次序构造一棵二叉排序树BSoa2依此二叉排序树，如何得到一个从大到小的有序序列？3假定每一个元素的查找概率相等，试计算该二叉排序树的平均查找长度4画出在此二叉排序树中删除“66”后的树结构
11.给定关键词输入序列{CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO},假定关键词比较按英文字典序，试画出从一棵空树开始，依上述顺序从左到右输入关键词，用平衡树的查找和插入算法生成一棵平衡树的过程，并说明生成过程中采用了何种转动方式进行平衡调整，标出树中各结点的平衡系数
12.假定对有序表3,4,5,7,24,30,42,54,63,72,87,95进行折半查找，试回答下列问题
1.画出描述折半查找过程的判定树；2,若查找元素54,需挨次与那些元素比较？3,若查找元素90,需挨次与那些元素比较？
4.假定每一个元素的查找概率相等，求查找成功时的平均查找长度第章查找9一.选择题
1.C
2.D3D
4.A
5.B
6.1C
6.2C
7.IB
7.2A
9.C
10.C
11.B
12.B
15.D
16.B
17.D
18.D
19.D
20.C二.判断题
1.V
2.V
3.X
4.J
5.J
6.X
7.V
8.X
9.X
10.
11.
12.X JX
13.
14.V X三.填空题
1.n n+
12.6,9,11,
123.
54.26第4层是叶子结点，每一个结点两个关键字
5.m-1,「m/2]T
9.2,4,
36.小于等于表长的最大素数或者不包含小于20的质因子的合数
8.n+l/
29.n+l/n*log n+l-l
10.结点的左子树的高度减去结点的右子树的高2度
11.1静态查找表⑵动态查找树表⑶哈希表4开放定址方法⑸链地址方法6再哈希⑺建立公共溢出区n+
112.log J2+1，n+l/2最坏情况是每一个结点只要一个孩子结点的情况，这时的I m2」r平均时间复杂度为n+1/2,而log肺+1-2是通常情况下的人51s
13.
3114.主关键字
15.插入删除161low=mid+12high=mid-l3high=low四.应用题
1.概念是基本知识的主要部份，要坚固掌握这里只列出一部份，目的是引起重视，解答略散列地址0123456789关键字140192384275520比较次数11123412查找成功平均查找长度ASL=1+1+1+2+3+4+1+2/8=15/8以关键字27为例11SUCC27=27%7二6冲突H=6+1%10=7冲突II=6+22%10=0冲突H=6+33%10=51所以比较了4次23注意计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i0WiWm-1时的查找次数如下例中m=10o对于关键字集｛30,15,21,40,25,26,36,37｝若查找表的装填因子为
0.8,哈希函数为H key=key%7采用线性探测再散列方法解决冲突，则哈希表如下散列地址01234567892115303625402637关键字比较次数11131126故查找失败时的平均查找长度为ASL=4+8+7+6+5+4+3+2+1+1/10=
4.623A101111A12unsuccASL查找成功二18/
137.如下图
9.1当插入26后的树形为:0123456789插入85后树形为:⑵删除53后为:删除37后:1构造的二叉排序树为4删除结点66后;2对于一个二叉排序树，想得到一个从大到小的序列只要先读右子树再读根结点，最后读左子树的遍历这颗二叉树就可以了如果是要从小到大的序列，则只需中序遍历这颗二叉树就可3该二叉树的平均查找长度为ASL=1*1+2*2+3*4+4*3/10=
2.
910.1二叉判定树为2若要查找54,则需要查找30,63,42,543若要查找90,则需查找30,63,87,95,空4假定每一个元素的查找概率相等，则查找成功时的平均查找长度为ASL=1*1+2*2+4*3+5*4/12=37/12。
个人认证
优秀文档
获得点赞 0
