数据构造第九章查找 习题及答案讲课教案.docx

《数据构造第九章查找 习题及答案讲课教案.docx》由会员分享，可在线阅读，更多相关《数据构造第九章查找 习题及答案讲课教案.docx（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据构造第九章查找习题及答案讲课教案当前位置：文档视界数据构造第九章查找习题及答案讲课教案数据构造第九章查找习题及答案讲课教案第九章查找一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A(n-1)/2B.n/2C.(n+1)/2D.n2.下面关于二分查找的叙述正确的是()A.表必须有序，表能够顺序方式存储，可以以链表方式存储C.表必须有序，而且只能从小到大排列B.表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只能以顺序方式存储3.用二分对半查找表的元素的速度比用顺序法()A必然快B.必然慢C.相等

2、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的有序表和无序表分别进行顺

3、序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是(1),对于查找成功,他们的平均查找长度是(2)供选择的答案:A.一样的B.不同的9分别下面列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A100，80，90，60，120，110，130B.100，120，110，130，80，60，90C.100，60，80，90，120，110，130D.(100，80，60，90，120，130，110)10.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作()型调整以使其平衡。A.LLB.LRC.

4、RLD.RR11.下面关于m阶B-树讲法正确的是()每个结点至少有两棵非空子树；树中每个结点至多有m一1个关键字;所有叶子在同一层上;当插入一个数据项引起B树结点分裂后，树长高一层。AB.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，用链地址法构造散列表，散列函数为Hkey=keyMOD13,散列地址为1的链中有个记录。A1B.2C.3D.416.关于哈希查找讲法不正确的有几个()1采用链地址法解决冲突时，查找一个元素的时间是一样的2

5、采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是一样的3用链地址法解决冲突易引起聚集现象4再哈希法不易产生聚集A.1B.2C.3D.417.设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()A8B3C5D918.假定哈希查找中k个关键字具有同一哈希值，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？()Ak-1次B.k次C.k+1次D.kk+1/2次19.好的哈希函数有一个共同的性质，即函数值应当以()取其值域的每个值。

6、A.最大概率B.最小概率C.平均概率D.同等概率20.将10个元素散列到100000个单元的哈希表中，则产生冲突。A.一定会B.一定不会C.仍可能会二、判定题1采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，由于这会影响以后的查找。2在散列检索中，“比拟操作一般也是不可避免的。3Hash表的平均查找长度与处理冲突的方法无关。4.散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。5.在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。6.就平均查找长度而言，分块查找最

7、小，折半查找次之，顺序查找最大。7最佳二叉树是AVL树平衡二叉树。8在查找树二叉树排序树中插入一个新结点，总是插入到叶结点下面。9二叉树中除叶结点外,任一结点X，其左子树根结点的值小于该结点X的值；其右子树根结点的值该结点X的值,则此二叉树一定是二叉排序树。10有n个数存放在一维数组A1.n中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。11.N个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。12.在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树一样。13.B-树中所有结点的平衡因子都为零。14.在平衡二叉树中，向某个平衡因子不为

8、零的结点的树中插入一新结点，必引起平衡旋转。三、填空题1.顺序查找n个元素的顺序表，若查找成功，则比拟关键字的次数最多为_次；当使用监视哨时，若查找失败，则比拟关键字的次数为_。2在有序表A1.12中，采用二分查找算法查等于A12的元素，所比拟的元素下标依次为_。3.在有序表A1.20中，按二分查找方法进行查找，查找长度为5的元素个数是_4.高度为4含叶子结点层的3阶b-树中，最多有_个关键字。5.在一棵m阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是_;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是_。6.在哈希函数Hkey

9、=key%p中，p值最好取_。8.假如按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比拟次数为_。9.假如关键码按值排序，而后用二分法依次检索这些关键码，并把检索中碰到的在二叉树中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比拟次数为_。提示：此时二叉排序树与折半查找的二叉断定树一样了10.平衡因子的定义是_11.查找是非数值程序设计的一个重要技术问题，基本上分成_(1)_查找，_(2)_查找和_(3)_查找。处理哈希冲突的方法有_(4)_、_(5)_、_(6)_和_(7)_。12.具有N个关键字的B树的查找途径长度不会大于_

10、。在一棵有N个结点的非平衡二叉树中进行查找，平均时间复杂度的上限即最坏情况平均时间复杂度为_13.高度为5除叶子层之外的三阶B-树至少有_个结点。14.能够唯一的标识一个记录的关键字称为_。15.动态查找表和静态查找表的重要区别在于前者包含有_和_运算，而后者不包含这两种运算。16.已知N元整型数组a存放N个学生的成绩，已按由大到小排序，下面算法是用对分折半查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。(提示：这时需要找的是最后一个大于等于X的下标，若查找成功其下标若为m，则有m个学生成绩大于或等于X，若查找不成功，若这时low所指向的值小于X，则有low-1个学生成绩大于或等于X

11、，注意这时表中可能不止一个数值为X的值，这时我们要查找的是下标最大的)#defineN/*学生人数*/intuprx(intaN,intx)/*函数返回大于等于X分的学生人数*/intlow=1,mid,high=N;domid=(low+high)/2;if(x1对树a,请分别画出先后插入26，85两个新结点后的树形；2b10.输入一个正整数序列53,17,12,66,58,70,87,25,56,60，试完成下列各题。1按次序构造一棵二叉排序树BS。2依此二叉排序树，怎样得到一个从大到小的有序序列？3假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度4画出在此二叉排序树中删除“6

12、6后的树构造。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).假定每个元素的查找概

13、率相等，求查找成功时的平均查找长度。第9章查找一选择题二判定题三填空题1nn+126,9,11,1235426第4层是叶子结点，每个结点两个关键字5m-1,m/2?-192,4,36小于等于表长的最大素数或不包含小于20的质因子的合数8(n+1)/29(n+1)/n*log2(n+1)-110结点的左子树的高度减去结点的右子树的高度11(1)静态查找表(2)动态查找树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区12log?m/2?(21n+)+1，(n+1)/2最坏情况是每个结点只要一个孩子结点的情况，这时的平均时间复杂度为n+1/2,而2)1(5(log-+n?是通常情况下的ASL133114主关键字15插入删除16(1)low=mid+1(2)high=mid-1(3)high=low四应用题