下载文档原格式
《数据结构》第九章习题参考答案《数据结构》第九章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）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）。
习题九排序一、单项选择题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．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。
A．冒泡 B. 希尔C. 快速D. 堆7.就平均性能而言，目前最好的内排序方法是() 排序法。
A. 冒泡B.希尔插入C.交换D.快速8.下列排序算法中，占用辅助空间最多的是：()A. 归并排序B.快速排序C.希尔排序D.堆排序9.若用冒泡排序方法对序列 {10,14,26,29,41,52}从大到小排序，需进行（）次比较。
第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）。
算法导论第九章习题答案（第三版）IntroductiontoAlgorithm Exercise
9.1-1
对所有的元素，两个⼀组进⾏⽐较，共需n-1次⽐较，可以构成⼀棵⼆叉树，最⼩的元素在树的根结点上，接下来，画出⼆叉树，可以很容易的看出共需lgn-1次⽐较，所以共需n+lgn-2次⽐较才可以找出第⼆⼩的元素。
9.1-2
略。
9.2-1
在randomized-select中，对于长度为0的数组，此时p=r，直接返回A[p],所以不会进⾏递归调⽤。
9.2-2
略。
9.2-3
RANDOMIZED-SELECT(A,p,r,i){
while(true){
if(p==r)
return A[p];
q=RANDOMIZED-PARTITION(A,p,r);
k=q-p+1;
if(i==k)
return A[q];
else if(i<k)
q--;
else{
q++;
i-=k;
}
}
}
9.2-4
每次都以最⼤的元素进⾏划分即可。
9.3-1
数学计算，根据书中例题仿照分析即可。
9.3-3
随机化
9.3-5
类似主元划分，只要把⿊箱⼦输出的值作为主元划分去选择即可。
9.3-6
多重⼆分即可。
9.3-7
算出中位数，之后算出每⼀个数与中位数的差即可。
9.3-8
分别取两个数组的中位数进⾏⽐较，如果两个中位数相等，那么即为所求，否则，取中位数较⼩的⼀个的右边，取较⼤的⼀个的右边，直到就剩4个元素为⽌，这时候只要求这4个元素的中位数即可。
数据结构(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 ）。
A、10B、15C、21D、349、就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系（ A ）。
第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 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)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法 10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。
第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n n n 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)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。
数据结构与算法习题册（课后部分参考答案）《数据结构与算法》课程组目录目录课后习题部分第一章绪论 (1)第二章线性表 (3)第三章栈和队列 (5)第四章串 (8)第五章数组和广义表 (10)第六章树和二叉树 (13)第七章图 (16)第九章查找 (20)第十章排序 (23)第一章绪论一. 填空题1. 从逻辑关系上讲，数据结构的类型主要分为集合、线性结构、树结构和图结构。
2. 数据的存储结构主要有顺序存储和链式存储两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素和数据元素之间的关系。
3. 算法具有五个特性，分别是有穷性、确定性、可行性、输入、输出。
4. 算法设计要求中的健壮性指的是算法在发生非法操作时可以作出处理的特性。
二. 选择题1. 顺序存储结构中数据元素之间的逻辑关系是由 C 表示的，链接存储结构中的数据元素之间的逻辑关系是由 D 表示的。
A 线性结构B 非线性结构C 存储位置D 指针2. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是B 。
A 树B 图C 线性表D 集合3. 算法指的是 A 。
A 对特定问题求解步骤的一种描述，是指令的有限序列。
B 计算机程序C 解决问题的计算方法D 数据处理三. 简答题1. 分析以下各程序段，并用大O记号表示其执行时间。
(1) (2)i=1;k=0; i=1;k=0;While(i<n-1) do{ {k=k+10*i; k=k+10*i;i++; i++;} }while(i<=n)⑴基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。
⑵基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。
2. 设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。
第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章查找习题练习答案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=查找失败时，最多的关键字比较次树不超过判定树的深度，此处为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.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)用链地址法处理。
第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。
设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。
解：显然，平均查找长度＝O （log 2n ）<5次（25）。
但具体是多少次，则不应当按照公式)1(log 12++=n n n 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)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。
第九章查找一、选择题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,则应作( ) 型调整以使其平衡。
第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经过三次比较，查找成功。
(2)g的查找过程如下：[a b c d e f (g) h i j k p q]一次比较成功。
(3)n的查找过程如下：下标： 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]第四次比较： a b c d e f g h i j [k] p q]经过四次比较，查找失败。
6.将(for, case, while, class, protected, virtual, public, private, do, template, const ,if, int)中的关键字依次插入初态为空的二叉排序树中，请画出所得到的树T。
然后画出删去for之后的二叉排序树T',若再将for 插入T'中得到的二叉排序树T''是否与T相同?最后给出T"的先序、中序和后序序列。
答：二叉排序树T如下图：删去for后的二叉排序树如下图：再插入结点for后的二叉排序树T"：二叉排序树T"与T不同T"的先序序列是：do case class const while protected private if for int virtual public templateT"的中序序列是：case class const do for if int private protected public template virtual whileT"的后序序列是：const class case for int if private template public virtual protected while do7.对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树?答：有可能。
如有两个序列：3，1，2，4 和3，4，1，2，它们插入空树所得的二叉排序树是相同的。
8.将二叉排序树T的先序序列中的关键字依次插入一空树中，所得和二叉排序树T'与T否相同?为什么?答：这两棵二叉树完全相同。
9.设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查找到的序列?(a) 2，252，401，398，330, 344，397，363；(b) 924, 220, 911, 244, 898, 258, 362, 363;(c) 925, 202, 911, 240, 912, 245, 363;(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.答：(c)是不可能查找到的序列。
把这四个序列各插入到一个初始为空的二叉排序树中，结果可以发现，(c)序列所形成的不是一条路径，而是有分支的，可见它是不可能在查找过程中访问到的序列。
10.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。
此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?答：此命题正确。
假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元也是这个道理。
但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。
新结点总是作为叶子插入在二叉排序树中的。
11.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字?答：在一棵m阶的B-树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。
若删去某结点中一个关键字而导致结点合并时，该结点中原有┌m/2┐-1个关键字。
12.在一棵B-树中，空指针数总是比关键字数多一个，此说法是否正确?请问包含8个关键字的3阶B-树(即2-3树)最多有几个结点?最少有几个结点?画出这两种情况的B-树。
答：这个说法是正确的。
包含8个关键字的3阶B-树最多有7个结点，最少有4个结点。
13.从空树开始，依次输入20，30，50，52，60，68，70，画出建立2-3树的过程。
并画出删除50和68后的B-树状态。
答：过程如下：(1) 插入20，30：(2) 插入50：(3) 插入52：(4) 插入60：(5) 插入68：(6) 插入70：(7)删去50：(8) 删去6814.画出依次插入z,v,o,p,w,y到图9.12(h)所示的5阶B-树的过程。
解：(1)插入z后：(2)插入v,o后(3)插入 p,w,y后16.为什么在内存中使用的B-树通常是3阶的，而不使用更高阶的B-树?答：因为查找等操作的cpu时间在B-树上是O(lgn·(m/lgt)),而m/lgt>1,所以m较大时它所费时间比平衡的二叉排序树上相应操作时间大得多，因此，仅在内存中使用的B-树通常取最小值317.为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根?哪一种长高能保证树平衡?答：因为在二叉排序树中，关键字总是作为一个叶子结点插入以原来的树中，所以当树增高时，新结点总是一个叶子；而B-树中关键字插入总是插入到叶子结点内部，在叶结点中的关键字数目尚未超过它能够容纳的数目之前是不会增加结点的，当关键字数超过结点可容纳的数目时，叶结点就会发生分裂，产生一个新结点(但不一定引起树增高)，并且将其中的中间结点传至上一层，只有当这种分裂操作传递至根结点并引起根结点的分裂时，才能引起树高增加，此时产生一个新的根结点。
所以说B树长高时，新结点总是根。
显然，后一种长高总能保证树的平衡。
19.对于一组给定的、固定不变的关键字序列，有可能设计出无冲突的散列函数H，此时称H为完备的散列函数(perfect hashing function)，若H能无冲突地将关键字完全填满散列表，则称H是最小完备(minimal perfect)的散列函数。
通常找完备的散列函数非常困难，找最小完备的散列函数就更困难。
请问：(1)若h是已知关键字集合K的完备的散列函数，若要增加一个新的关键字到集合K，一般情况下H还是完备的吗?(2)已知关键字集合为(81，129，301，38，434，216，412，487，234)，散列函数为H(x)=(x+18)/63,请问H是完备的吗?它是最小完备的吗?(3)考虑由字符串构成的关键字集合(Bret,Jane,Shirley,Bryce,Michelle,Heather)，试为散列表[0..6]设计一个完备的散列函数。
(提示：考虑每个字符串的第3个字符，即s[2])答：(1) 一般情况下H不是完备的，如果说插入一个新的关键字它还是完备的，那么再插入一个呢?它岂不是永远是完备的散列函数了? 所以一般情况下它不能总是完备的，只有一些很少的情况下它还可能是完备的。
(2)这个H是完备的，其函数值依次为：1，2，5，0，7，3，6，8，4。
如果散列表长m=9时，它就是最小完备的。
(3) 这个函数如下：int Hash (char key[]){ return key[2]%7;}20.设散列函数为h(key)=key%101,解决冲突的方法为线性探查，表中用"-1"表示空单元。
若删去散列表HT中的304(即令HT[1]=-1)之后，在表HT中查找707将会发生什么?若将删去的表项标记为"-2",查找时探查到-2继续向前搜索，探查到-1时终止搜索。
请问用这种方法删304后能否正确地查找到707?012 3 100┌──┬──┬──┬──┬───────────┬─┐HT│202 │304 │507 │707 │...... ││└──┴──┴──┴──┴───────────┴─┘答：查找707时，首先根据散列函数计算得出该元素应在散列表中的0单元，但是在0单元没有找到，因此将向下一单元探查，结果发现该单元是-1(为空单元)，所以结束查找，这将导致707无法找到。
