下载文档原格式
数据结构-第九章查找在计算机科学的世界里，数据结构就像是一个精心设计的仓库，用于高效地存储和管理数据。
而查找，作为数据结构中的重要一环，它的作用就如同在这个庞大的仓库中迅速找到我们需要的宝贝。
当我们面对大量的数据时，如何快速准确地找到特定的信息，这是查找要解决的核心问题。
在第九章中，我们会深入探讨几种常见的查找算法和数据结构。
首先，我们来谈谈顺序查找。
这是最简单也是最直观的查找方法。
想象一下，我们有一个长长的列表，就像一排摆放整齐的物品，要找某个特定的东西，我们只能从第一个开始，一个一个地依次检查，直到找到目标或者遍历完整个列表。
这种方法虽然简单直接，但效率并不高，特别是当数据量很大时，查找的时间会很长。
与顺序查找相对的是二分查找。
二分查找就聪明多了，它要求数据是有序的。
就好像我们知道物品是按照大小顺序摆放的，每次都可以通过比较中间的元素来判断目标在左边还是右边，然后不断缩小查找的范围。
通过这种方式，查找的效率大大提高。
比如说，在一个有 100 个元素的有序列表中，最多只需要 7 次比较就能找到目标元素。
接下来是二叉查找树。
它是一种特殊的数据结构，每个节点最多有两个子节点，左子节点的值小于父节点，右子节点的值大于父节点。
通过这种特殊的结构，我们可以快速地在树中查找目标元素。
插入和删除操作也相对方便，但要注意保持树的平衡，否则查找的效率可能会下降。
还有哈希表，这是一种非常高效的查找结构。
它通过一个哈希函数将关键字映射到一个特定的位置。
如果哈希函数设计得好，查找的时间复杂度可以接近常数级别。
但哈希表也有它的问题，比如可能会出现哈希冲突，需要通过合适的冲突解决方法来处理。
在实际应用中，选择哪种查找方法取决于具体的情况。
如果数据量较小，顺序查找可能就足够了；如果数据是有序的，二分查找是个不错的选择；如果需要频繁的插入和删除操作，二叉查找树可能更合适；而对于大规模数据且查找操作频繁的情况，哈希表往往能发挥出巨大的优势。
第九章查找一、选择题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。
1 B。
4 C. 2。
5 D. 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。
第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。
A. kB.k+lC. k(k+l)／2D. 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，1B.6，lC.5，1D. 8，15．散列表长m=15，散列表函数H(key)=key%13。
表中已有4个结点：addr(18)=5；addr(32)=6; addr(59)=7; addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。
A. 8B. 3C. 5D. 46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。
A. 15B. 27C. 25D. 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.mB. m-lC.m+lD.[m+1]10．当向一棵m阶的B壤f做删除操作时，若使一个结点中的关键字个数等于( )，则可能需要用它的左兄弟或右兄弟结点合并成一个结点。
A. [m/2]B.[m-l]C. [m/2]+1D. [m+l]-211．衡量查找算法效率的主要标准是( )。
A. 元素个数B. 所需的存储量C. 平均查找长度D.算法难易程度二、填空题1．顺序查找长度为n的顺序表，查找成功的平均查找长度为____。
2．折半查找要求线性表的存储结构为____；而用顺序查找的线性表，既可以采用，也可以采用____。
3．散列查找是一种对关键字进行____的查找方法。
4．散列法既是一种查找方法，又是一种____方法。
5．在有序表(12，24，36，48，60，72，84)中二分查找关键字72时所需进行的关键字比较次数为____。
6．在散列存储中，装填因子α的值越大，存取元素时发生冲突的可能性就____；α的值越小，存取元素时发生冲突的可能性就____。
7．在线性表的散列存储中，处理冲突有____和____两类；当装填因子一定时，采用链地址法处理冲突比采用开放定址法处理冲突的平均查找长度要____。
8．在一棵10阶的B-树上，每一个树根结点中所含的关键字数目最多允许为____；最少允许为____。
9．当向B-树中插入关键字时，可能引起结点的____；最终可能导致整个B-树的高度____。
三、简答题1．对含有n个互不相同元素的集合，同时找最大元素和最小元素至少需要多少次比较？2．若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：(1)查找不成功，即表中无关键字等于给定值。
(2)查找成功，即表中有关键字等于给定值k的记录。
3．对给定的关键字集合，以不同的次序插入初始为空的树中，是否有可能得到同一棵二叉排序树？4．将二叉排序树T的前序序列中关键字依次插入初始为空的树中，所得到的二叉排序树T’与T是否相同？为什么？5．设二叉排序树中关键字由1到1000内的整数构成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查找到的序列。
(1) 2,252,401,398,330,344,397,363(2) 924,220,911,244,898,258,362,363(3) 925,202,911,240,912,245,363(4) 2,399,387,219,266,382,381,278,3636．为什么二叉排序树长高时，新结点总是一个叶子，而B-树长高时，新结点总是根？哪一种长高能保证树平衡？7．设有一组关键字(17，13，14，153，29，35)需插入到表长为12的散列表中．请回答以下问题：(l)设计一个适合该散列表的散列函数；(2)设计的散列函数将上述关键字插入到散列表中，画出其结构；并指出用线性探测法解冲突时构造散列表的装填因子为多少？8．已知记录关键字集合( 53，17，19，61，98，75，79，63，46，49)，要求散列到地址区间(100，101，102，103，104，105，106，107，108，109)内，若产生冲突用开放定址法的线性探测法解决，要求写出选用的散列函数；形成散列表；计算出查找成功时平均查找长度（设等概率情况）。
9．已知一个含有100条记录的表，关键字为中国姓氏的拼音，若采用散列存储方式存放此表，请给出此表的一个散列表设计方案，要求它在等概率的情况下查找成功的平均查找长度不超过3。
四、算法设计题1．利用二叉树遍历的思想写一个判断二叉树是否为平衡二叉树的算法test(BsTree *p，i nt balance，…)；其中p初值指向待判二叉树的根，balance是一判断结果的输出标志，初值为True(l)，根据需要可增加其他必要的参数。
在判断各点平衡的过程中，一旦发现有悖于平衡二叉树的定义，则balance应转变为False(0),且终止该过程。
2．设单链表的结点按关键字的大小从小到大排列，试写出对此链表的查找算法，并说明是否可用折半查找。
3．试设计一个算法，求出指定结点在给定的二叉排序树中的层次。
4．编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树，假设每次查找时的给定值为随机值，查找成功和不成功的概率也相等，试求进行每依次查找时，与给定值进行比较的关键字个数的期望值。
5．已知一组递增有序的关键字k[0…n-1]；k0≤k i≤…≤k n-1，在等概率查找的前提下，可以生成一棵二叉排序树。
以哪个关键字为根结点，按什么方式生成二叉排序树既有平衡性又简单？阐明算法思路，写出相应的算法。
如果k[0…10]为：(7，12，13，15，21，33，38, 41，49，55，58)。
按你的算法画出这棵二叉排序树。
6．编写判定给定的二叉树是否是二叉排序树的函数。
7．编写一个算法，删除二叉排序树中除根结点以外的任一结点p，已知p的双亲结点f。
8．已知某散列表的装填因子小于1，散列函数h(k)为k（k为标识符，均小写）的第一个字母在字母表中的序号。
采用开放定址法的线性探测再散列解决冲突。
试编写一个按第一个字母的顺序输出散列表中所有关键字的算法。
第九章查找第9章查找一．选择题1．C 2．D 3．A 4．D 5．D 6．B7．A 8．B 9．A 10.D 11.C二．填空题1．(n+l)/2。
2．顺序存储结构、顺序存储结构、链接存储结构。
3．运算。
4．存储。
5.2 6．越大，越小。
7．开放定址法，链地址法，短。
8.9，4。
9．分裂，增加l。
三、简答题1．按照下面的顺序查找算法，如果初始序列递增有序，则只需比较n-l次;如果初始序列递减有序，则需比较2(n-l)次。
因此，对含有n个互不相同元素的集合，同时找最大元素和最小元素至少需要比较n-l次，最多需要比较2(n-l)次。
max=min=r[O].key;for(i=1;i<n;i++)if(r[i]. key>max) max-r[i]. key;else if(r[i]. key<min) min=r[i].key;2．(1)查找不成功的情况。
1)对于有序表，第一小的元素在0号位置，第二小的元素在l号位置，第n小的元素，即最大的元素在n-l号位置。
显然，查找第i小的元素只要比较i+l次就能够确定查找不成功。
因此，在等概率的情况下，查找不成功的平均查找长度为2)对于无序的顺序表，查找每一个元素都要比较n+l次才能确定其查找不成功。
因此在等概率的情况下查找不成功的平均查找长度为n+l。
(2)查找成功的情况。
不论是有序表还是无序表，在位置i上查找成功的比较次数均为i+l次，因此在等概率的情况下，其成功的平均查找长度均为(n+l)/2。
3．除单元素外，对给定关键字集合，以不同的次序插入初始为空的树中不可能得到同一棵二叉排序树。
4．因为按二叉排序树T的前序序列将关键字依次插入到初始为空的二叉排序树T’中的插入过程与二叉排序T，的前序遍历过程完全一致，次序不会改变，所以T’与T完全相同。
5．关键字序列(3)不可能是在二叉排序树上查找到的序列。
因为根据序列(3)，240是911的左孩子，912在240的后面，是240的右孩子;而实际上，912比911大，应当在911的右子树上，即912不可能出现在911的左子树上，所以序列(3)不可能出现。
6．因为二叉排序树的插入总是从根结点开始逐层往下比较，若比根小，则走左边;若比根大，则走右边。
这样找到的插入位置，不是某结点的空闲左链域就是某结点的空闲右链域，即新结点总是作为叶结点插入进来的。
B-树的插入不是在树中添加一个叶结点;而是首先在最底层的某个终端结点中添加一个关键字，若该结点的关键字数不超过m-l，则完成插入，否则进行向上“分裂”，从而使新结点总是以根的形式出现。
B-树的插入能保证树的平衡。
7．(1)由于散列表的长度为12，则可选不超过表长的最大素数ll作为除留余数法的模，则可得其散列函数为h(k)=k%11。
(2)若用线性探测法解决冲突，则可构造出散列表如下：此时，其装填因子为：α= 6/12=0.5。
8．散列函数：H(key)=lOO+(key个位数+key十位数)%10。
形成散列表为：查找成功时的平均长度为：(1×5+2×1+3×1+5×3)/10=2.59．(1)确定该散列表的装填因子a。
散列表的查找效率与采用的处理冲突的方法及散列表的装填因子α有关。
α越小，表中的记录数越少或表越长，发生冲突的可能性就越小，此时的查找效率越高：反之，α越大，表中的记录数越多或表的长度越小，表中记录的密度越高，发生冲突的可能性越大，查找效率越低，所花的时间也越长。
