《数据结构》习题集：第9章查找(第1次更新2019-5)

资料范本本资料为word版本，可以直接编辑和打印，感谢您的下载数据结构第九章排序习题及答案地点：__________________时间：__________________说明：本资料适用于约定双方经过谈判，协商而共同承认，共同遵守的责任与义务，仅供参考，文档可直接下载或修改，不需要的部分可直接删除，使用时请详细阅读内容习题九排序一、单项选择题1．下列内部排序算法中：A．快速排序 B.直接插入排序C. 二路归并排序D. 简单选择排序E. 起泡排序F. 堆排序（1）其比较次数与序列初态无关的算法是（）（2）不稳定的排序算法是（）（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（）（4）排序的平均时间复杂度为O(n•logn)的算法是（）为O(n•n)的算法是（）2．比较次数与排序的初始状态无关的排序方法是( )。

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序3．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21（3） 15 21 25 84 47 （4） 15 21 25 47 84则采用的排序是 ( )。

A. 选择B. 冒泡C. 快速D. 插入4．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择B. 冒泡C. 归并D. 堆5．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A．(38,40,46,56,79,84) B. (40,38,46,79,56,84)C．(40,38,46,56,79,84) D. (40,38,46,84,56,79)6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。

（完整word版）《数据结构》习题集：第9章_查找第九章查找1.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，32．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。

A. O(1)B. O(log2n) C. O(n) D. O(n2) 5．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。

A. 25B. 10C. 7D. 16．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。

A. O(n)B. O(n2)C. O(n1/2)D. O(1og2n) 8．（）二叉排序树可以得到一个从小到大的有序序列。

A. 先序遍历B.中序遍历C. 后序遍历D. 层次遍历9．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。

A. 1B. 2C. 3D. 410．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。

A. 99B. 97C. 91D. 9311．在二叉排序树中插入一个关键字值的平均时间复杂度为（）。

A. O(n)B. O(1og2n) C. O(nlog2n) 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，则顺序查找的平均比较次数为（）。

《数据结构》第九章习题参考答案《数据结构》第九章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、快速排序是一种稳定的排序方法。

（×）2、在任何情况下，归并排序都比简单插入排序快。

（×）3、当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。

（√）4、内排序要求数据一定要以顺序方式存储。

（×）5、直接选择排序算法在最好情况下的时间复杂度为O（n）。

( ×)6、快速排序总比简单排序快。

( ×)二、单项选择题1．在已知待排序文件已基本有序的前提下，效率最高的排序方法是（A）。

A．直接插入排序B．直接选择排序C．快速排序D．归并排序2．下列排序方法中，哪一个是稳定的排序方法？（B）A．直接选择排序B．折半插入排序C．希尔排序D．快速排序3、比较次数与排序的初始状态无关的排序方法是( B)。

A．直接插入排序B．起泡排序（时间复杂度O（n2））C．快速排序D．简单选择排序4、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 则采用的排序是( A)。

A. 选择B. 冒泡C. 快速D. 插入5、快速排序方法在（D）情况下最不利于发挥其长处。

A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据个数为奇数D. 要排序的数据已基本有序6、用某种排序方法对线性表{25，84，21，47，15，27，68，35，20}进行排序，各趟排序结束时的结果为：（基准）20，21，15，25，84，27，68，35，47（25）15，20，21，25，47，27，68，35，84（左20右47）15，20，21，25，35，27，47，68，84（左35右68）15，20，21，25，27，35，47，68，84 ；则采用的排序方法为（C）。

第9章 查找答案一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 9 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m-1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=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<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)二、单项选择题（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n ＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

第9章集合部分答案解释如下。

4．不能说哪种哈希函数的选取方法最好，各种选取方法有自己的适用范围。

8．哈希表的结点中可以包括指针，指向其元素。

11．单链表不能使用折半查找方法。

20．按插入后中序遍历是递增序列的原则，若某结点只有右子树，而插入元素的关键字小于该结点的关键字，则会插入到该结点的左侧，成为其左孩子。

这种插入就不是插入到叶子下面。

21．从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。

但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。

故不能说完全二叉树是平衡二叉树。

23．某结点的左子树根结点不一定是它的中序前驱，其右子树根结点也不一定是它的中序后继。

24．在等概率下，查找成功时的平均查找长度相同，查找失败时的平均查找长度不相同。

26．只有被删除结点是叶子结点时命题才正确。

三．填空题1．n n+1 2．4 3．6,9,11,12 4．55．26（第4层是叶子结点，每个结点两个关键字） 6．1,3,6,8,11,13,16,19 7．5,96 8．m-1,「m/2⎤-1 9．2,4,310．(1)哈希函数(2)解决冲突的方法 (3)选择好的哈希函数 (4)处理冲突的方法 (5)均匀(6)简单11．AVL树（高度平衡树，高度平衡的二叉排序树），或为空二叉树，或二叉树中任意结点左子树高度与右子树高度差的绝对值小于等于1。

12．小于等于表长的最大素数或不包含小于20的质因子的合数 13．16 14．⎣㏒n」+1215．(1)45 (2)45 (3)46（块内顺序查找） 16．k(k+1)/2 17．30，31.5（块内顺序查找）18．(1)顺序存储或链式存储 (2)顺序存储且有序 (3)块内顺序存储，块间有序 (4) 散列存储19．(n+1)/2 20．(n+1)/n*log2(n+1)-1 21．结点的左子树的高度减去结点的右子树的高度22．(1)顺序表(2)树表(3)哈希表(4)开放定址方法(5)链地址方法(6)再哈希(7)建立公共溢出区23．直接定址法 24．log⎡m/2⎤(21n+)+1 25．O(N) 26．n(n+1)/227．54 28．31 29．37/12 30．主关键字 31．左子树右子树32．插入删除 33．14 34．(1)126 (2)64 (3)33 (4)65 35．（1）low<=high (2) (low+hig) DIV 2 (3) binsrch:=mid (4)binsrch:=0 36．(1) k (2) I<n+1 37．(1)rear=mid-1 (2)head=mid+1 (3)head>rear 38．(1)p!=null (2)pf=p (3)p!=*t (4)*t=null四．应用题1．概念是基本知识的主要部分，要牢固掌握。

数据结构第9章练习及答案1．顺序查找法适合于存储结构为（）的线性表。

A）散列存储B）顺序存储或链接存储C）压缩存储D）索引存储【答案】B2．下面哪些操作不属于静态查找表（）A）查询某个特定元素是否在表中B）检索某个特定元素的属性C）插入一个数据元素D）建立一个查找表【答案】C3．下面描述不正确的是（）A）顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。

B）静态查找表中关键字有序时，可用折半查找。

C）分块查找也是一种静态查找表。

D）经常进行插入和删除操作时可以采用折半查找。

4．散列查找时，解决冲突的方法有（）A）除留余数法B）数字分析法C）直接定址法D）链地址法【答案】D5．若表中的记录顺序存放在一个一维数组中，在等概率情况下顺序查找的平均查找长度为（）A）O（1）B）O(log2n) C）O(n) D）O(n2)【答案】C6．对长度为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/47．静态查找表与动态查找表二者的根本差别在于（）A）它们的逻辑结构不一样B）施加在其上的操作不同C）所包含的数据元素的类型不一样D）存储实现不一样【答案】B8．若查找表中的记录按关键字的大小顺序存放在一个一维数组中，在等概率情况下折半法查找的平均检索长度是（）A）O(n) B）O(log2n) C）O(nlog2n) D）O((log2n)2)【答案】B9．对有14个数据元素的有序表R[14]（假设下标从1开始）进行二分查找，搜索到R[4]的关键码等于给定值，此时元素比较顺序依次为（）。

A）R[1]，R[2]，R[3]，R[4] B）R[1]，R[13]，R[2]，R[3]C）R[7]，R[3]，R[5]，R[4] D）R[7]，R[4]，R[2]，R[3]【答案】C10．对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。

第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。

A. k B。

k+l C. k(k+l）／2 D. l+k （k+l)/22．下述命题( )是不成立的。

A。

m阶B-树中的每一个结点的子树个数都小于或等于mB。

m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C。

m阶B-树中的每一个结点的子树高度都相等D。

m阶B—树具有k个子树的非叶子结点含有(k-l）个关键字3．如果要求一个基本线性表既能较快地查找，又能适应动态变化的要求，可以采用( ）查找方法.A。

分块 B. 顺序 C. 二分 D.散列4．设有100个元素，用折半查找法进行查找时，最大比较次数是( ),最小比较次数是( ）.A。

7，1 B.6，l C.5，1 D. 8，15．散列表长m=15，散列表函数H(key）=key％13。

表中已有4个结点：addr（18)=5；addr(32）=6; addr(59)=7；addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。

A. 8 B。

3 C. 5 D。

46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。

A。

15 B. 27 C。

25 D。

307．散列函数有一个共同性质，即函数值应当以( )取其值域的每个值。

A.同等概率B。

最大概率C。

最小概率D。

平均概率8．设散列地址空间为O.。

m—1，k为关键字，假定散列函数为h(k)=k％p，为了减少冲突，一般应取p为( )。

A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9．当向一棵m阶的B-树做插入操作时，若使一个结点中的关键字个数等于( )，则必须分裂成两个结点。

A。

m B。

m-l C.m+l D。

数据结构(C语言版)习题及答案第九章数据结构(C语言版)习题及答案习题一、选择题1、一组记录的排序码为〔46，79，56，38，40，84〕，那么利用堆排序的方法建立的初始堆为( B )。

A、79，46，56，38，40，80B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，382、排序趟数与序列原始状态(原始排列)有关的排序方法是〔 ACD 〕方法。

A、插入排序B、选择排序C、冒泡排序D、快速排序3 、以下排序方法中，〔 B 〕是稳定的排序方法。

A、直接选择排序B、二分法插入排序C、希尔排序D、快速排序4、数据序列〔8，9，10，4，5，6，20，1，2〕只能是以下排序算法中( C )的两趟排序后的结果。

A、选择排序B、冒泡排序C、插入排序D、堆排序5、对序列(15，9，7，8，20，-1，4)进行排序，进行一趟排序后，数据的排列变为〔4，9，-1，8，20，7，15〕，那么采用的是〔 C 〕排序。

A、选择B、快速C、希尔D、冒泡6 、一组待排序记录的关键字为〔46，79，56，38，40，84〕，那么利用快速排序，以第一个记录为基准元素得到的一次划分结果为〔 C 〕。

A、(38,40,46,56,79,84)B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)7、用直接插入排序对下面四个序列进行排序〔由小到大〕，元素比拟次数最少的是〔 C 〕。

A、94,32,40,90,80,46,21,69B、32,40,21,46,69,94,90,80C、21,32,46,40,80,69,90,94D、90,69,80,46,21,32,94,408、假设用冒泡排序对关键字序列〔18,16,14,12,10,8〕进行从小到大的排序，所需进行的关键字比拟总次数是〔 B 〕。

第9章查找习题练习答案1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?答：设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。

从第2次开始，每次取一个元素先和max比较，如果大于max 则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，一路比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。

2.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1)查找不成功，即表中无关键字等于给定值K的记录；(2)查找成功，即表中有关键字等于给定值K的记录。

答：查找不成功时，需进行n+1次比较才能确定查找失败。

因此平均查找长度为n+1，这时有序表和无序表是一样的。

查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。

因为顺序查找与表的初始序列状态无关。

3.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。

答：等概率情况下，查找成功的平均查找长度为：ASL=(1+2*2+3*4+4*8+5*3)/18=3.556查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5.4.为什么有序的单链表不能进行折半查找?答：因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。

5.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。

解：(1)查找b的过程如下(其中方括号表示当前查找区间，圆括号表示当前比较的关键字)下标： 1 2 3 4 5 6 7 8 9 10 11 12 13第一次比较： [a b c d e f (g) h i j k p q]第二次比较： [a b (c) d e f] g h i j k p q第三次比较： [a (b)]c d e f g h i j k p q经过三次比较，查找成功。

《数据结构》习题集：第9章_查找《数据结构》习题集：第9章_查找第9章找到1。

如果一个由18个元素组成的有序表被存储在一维数组中，[19]，第一个元素被放入[1]，现在执行二进制搜索，用于寻找[3]的比较序列的下标是()A1，2，3 B，5，2，3 C，5，3 D，4，2，3 2。

如果二进制排序树中有n个节点，则二进制排序树中的平均搜索长度为()2a . 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.99b.97c.91d.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个存储单元，哈希函数H(key)= key% p，那么p最好选择()A.小于或等于m b 的最大奇数，小于或等于m c的最大素数，小于或等于m d的最大偶数，小于或等于m 14的最大组合数。

第九章9.1 若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同？（1）查找不成功，即表中没有关键字等于给的值K的记录；（2）查找成功，且表中只有一个关键字等于给定值K的记录；（3）查找成功，且表中有若干关键字等于给定值K的记录，要求找出所有这些记录。

答：(1)相同，有序n+1; 无序n+1(2)相同，有序12n+；无序12n+（3）不相同，对于有序表，找到了第一个与K相同的元素后，只要再找到与K 不同的元素，即可停止查找；对于无序表，则要一直查找到最后一个元素。

9.3 画出对长度为10的有序表进行折半查找的判定树，并分别求其等概率时查找成功和查找不成功的ASL。

查找成功：ASL=1/10(1*1+2*2+3*4+4*3)=2.92．设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。

然后求出等概率情况下查找成功与失败时的ASL。

【分析】因为顺序表中关键字是递增有序的，所以从低下标端开始顺序查找，若当前的关键码比要查找的关键码大，说明查找失败，终止查找。

【解答】（1）算法int seqsearch(SeqList R,KeyType K){int i;R[n]=K; // 设置哨兵i=0;while (R[i].key<K)i++;if (R[i].key==K)return i% n;elsereturn 0;}（2）查找长度成功情况：ASL succ=(1+2+3+……+n)/n=(n+1)/2失败情况：K<R[0].key时，比较1次，就终止查找；R[0].key<K< R[1].key时，比较2次，就终止查找；R[1].key<K< R[2].key时，比较3次，就终止查找；…R[n-2].key<K< R[n-1].key时，比较n次，就终止查找；R[n-1].key<K时，比较n+1次，就终止查找；所以ASL unsucc=((1+2+3+……+n+（n+1）)/(n+1)=（n+2）/2。

第9章 集合一、基础知识题假设对长度均为n 的有序的顺序表和无序的顺序表别离进行顺序查找，试在以下三种情形下别离讨论二者在等概率情形下平均查找长度是不是相同？（1）查找不成功，即表中没有和关键字K 相等的记录； （2）查找成功，且表中只有一个和关键字K 相等的记录；（3）查找成功，且表中有多个和关键字K 相等的记录，要求计算有多少个和关键字K 相等的记录。

【解答】（1）平均查找长度不相同。

前者在n+1个位置都可能失败，后者失败时的查找长度都是n+1。

（2）平均查找长度相同。

在n 个位置上都可能成功。

（3）平均查找长度不相同。

前者在某个位置上(1<=i<=n)查找成功时，和关键字K 相等的记录是持续的，而后者要查找完顺序表的全数记录。

在查找和排序算法中，监视哨的作用是什么？【解答】监视哨的作用是免去查找进程中每次都要检测整个表是不是查找完毕，提高了查找效率。

用分块查找法，有2000项的表分成多少块最理想？每块的理想长度是多少？假设每块长度为25 ，平均查找长度是多少？【解答】分成45块，每块的理想长度为45(最后一块长20)。

假设每块长25，那么平均查找长度为ASL=(80+1)/2+(25+1)/2=(顺序查找确信块)，或ASL=19(折半查找确信块)。

用不同的输入顺序输入n 个关键字，可能构造出的二叉排序树具有多少种不同形态? 【解答】 证明假设二叉排序树中的一个结点存在两个小孩，那么它的中序后继结点没有左小孩，中序前驱结点没有右小孩。

【证明】依照中序遍历的概念，该结点的中序后继是其右子树上按中序遍历的第一个结点，即右子树上值最小的结点：叶子结点或仅有右子树的结点，没有左小孩；而其中序前驱是其左子树上按中序遍历的最后个结点，即左子树上值最大的结点：叶子结点或仅有左子树的结点，没有右小孩。

命题得证。

关于一个高度为h 的A VL 树，其最少结点数是多少？反之，关于一个有n 个结点的A VL 树， 其最大高度是多少? 最小高度是多少?【解答】设以N h 表示深度为h 的A VL 树中含有的最少结点数。

第九章查找 习题解答9.5 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

解：求得的判定树如下： 57109643182ASL 成功=（1+2*2+4*3+3*4）/10 =2.99.9 已知如下所示长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec ）(1)试按表中元素的顺序依次插入一查初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

解：（1）求得的二叉排序树如下图所示：JanFeb MarApr Aug Dec June July MaySeptOctNov在等概率情况下查找成功的平均查找长度为：ASL 成功=（1+2*2+3*3+4*3+5*2+6*1）/12=42/12=3.5(2)分析：对表中元素进行排序后，其实就变成了对长度为12的有序表进行折半查找了，那么在等概率的情况下的平均查找长度只要根据折半查找的判定树就很容易求出。

长度为12的有序表进行折半查找的判定树如下图所示：681211754193210所以可求出：ASL 成功=（1+2*2+4*3+5*4）/12=37/129.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)=10H(67)=3；H 1(67)=2；H 2(67)=1所以：构造的哈希表如下图所示：并求得等概率情况下查找成功的平均查找长度为：ASL 成功=（1*4+2*2+3+6）/8=17/89.21 在地址空间为0~16的散列区中，对以下关键字序列构造两哈希表： （Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec ）(1)用线性探测开放定址法处理冲突；(2)用链地址法处理。

《数据结构》期末复习题及参考答案- 第9章查找////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////注意：做复习题时，请结合阅读教材，钻研教材，参考课件////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////一、选择题1、适用于折半查找的表的存储方式及元素排列要求为( )A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序2、对有18个元素的有序表A作折半查找，则查找A[3]的比较序列的下标为（）A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，33、对有14个数据元素的有序表R进行折半搜索，搜索到R[3]的关键字等于给定值，查找过程中元素比较的顺序依次为（）。

4、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( )A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/25、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。

A．35/12 B.37/12 C.39/12 D.43/126、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减7、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经（）次比较后查找成功。

第九章查找一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 下面关于二分查找的叙述正确的是 ( )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的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是((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,则应作( ) 型调整以使其平衡。

数据结构第九章查找练习及答案一、选择题1、对线性表进行二分查找时，要求线性表必须（）A、以顺序方式存储B、以链表方式存储C、以顺序方式存储，且结点按关键字有序排列D、以链表方式存储，且结点按关键字有序排列2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）A、nB、n/2C、(n+1)/2D、(n-1)/23、采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）A、n2B、nlog2nC、nD、log2n4、二分查找和二叉排序树的时间性能（）A、相同B、不相同C、有时相同D、有时不相同5、有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（）次比较后查找成功。

A、1B、2C、4D、86、哈希表长m=14，哈希表函数H（key）=key%11，表中已有4个结点：ADDR（15）=4，ADDR（38）=5；ADDR（61）=6；ADDR（84）=7；其余地址为空，如果用二次探测再散列处理冲突，关键字为49的结点的地址是（）A、8B、3C、5D、97、一个长度为12的有序表，按二分查找法对该表进行查找，在表内每个元素等概率情况下查找成功所需的平均比较次数（）A、35/12B、37/12C、39/12D、43/128、用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分（）结点最佳。

A、10B、25C、6D、6259、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用（）查找方法。

A、分块B、顺序C、二分D、散列10、有100个元素，用折半查找法进行查找时，最大比较次数是（）A、25B、50C、10D、711、有100个元素，用折半查找法进行查找时，最小比较次数是（）A、7B、4C、2D、112、散列函数有一个共同性质，即函数值应当以（）取其值域的每个值。