数据结构第8章查找练习题

1、一、单选题1下列查找方法中，不属于动态的查找方法是( )。A二叉排序树法B平衡树法C散列法D二分查找法2适用于静态的查找方法为( )。A二分查找、二叉排序树查找B二分查找、索引顺序表查找C二叉排序树查找、索引顺序表查找D二叉排序树查找、散列法查找3静态查找表与动态查找表二者的根本差别在于( )。A它们的逻辑结构不一样 B施加在其上的操作不同C所包含的数据元素的类型不一样D存储实现不一样4对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为( )。A5.5B5C39/8D19/45( )存储方式适用于折半

2、查找。A键值有序的单链表B键值有序的顺序表C键值有序的双链表D键值无序的顺序表6对线性表进行二分查找时，要求线性表必须( )。A以顺序方式存储B以链接方式存储C顺序存储，且结点按关键字有序排序D链式存储，且结点按关键字有序排序7在索引顺序表中查找一个元素，可用的且最快的方法是( )。A用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找B用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D用二分查找法确定元素所在块，再用二分查找法在相应块中查找8在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索

3、引查找的平均查找长度为( )。A13B24C12D799由同一关键字集合构造的各棵二叉排序树( )。A形态和平均查找长度都不一定相同B形态不一定相同，但平均查找长度相同C形态和平均查找长度都相同D形态相同，但平均查找长度不一定相同10对二叉排序树进行( )，可以得到各结点键值的递增序列。A先根遍历B中根遍历C层次遍历D后根遍历11下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序列？A2，25，40，39，53，34，35B25，39，2，40，53，34，35C53，40，2，25，34，39，35D39，25，40，53，34，2，3512在AVL树中，每个结点的平衡因子的取

4、值范围是( )。A-11B-22C12D0113在AVL树中，任一结点的( )。A左、右子树的高度均相同B左、右子树高度差的绝对值不超过1C左、右子树的结点数均相同D左、右子树结点数差的绝对值不超过114下面关于B树和B+树的叙述中，不正确的是A都是平衡的多叉树B都是可用于文件的索引结构C都能有效地支持顺序检索D都能有效地支持随机检索15右图是一棵( )。A4阶B-树B4阶B+树C3阶B-树D3阶B+树16对包含n个关键字的散列表进行检索，平均检索长度是( )。AO(log2n)BO(n)C不直接依赖于nDO(nlog2n)17在散列查找中，平均查找长度主要与( )有关。A散列表长度B散列元素

5、的个数C装填因子D处理冲突方法18要解决散列引起的冲突问题，常采用的方法有( )。A数字分析法、平方取中法B数字分析法、线性探测法C二次探测法、平方取中法D二次探测法、链地址法19从理论上讲，将数据以( )结构存放，查找一个数据的时间不依赖于数据的个数n。A二叉查找树B链表C散列表D顺序表20假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行( )次探侧。Ak-1BkCk+1Dk(k+1)/2二、判断题1顺序查找法不仅可用于顺序表上的查找，也可用于链表上的查找。2二分查找所对应的判定树，是一棵理想平衡的二叉排序树。3二叉排序树的形态与关键字的输入序列有关，但平衡二

6、叉排序树是相同的。4如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。5二叉排序树上，以根到任一结点的路径为界，则：路径左边结点路径结点路径右边结点。1535506570454030256在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。7用线性探测法解决突出时，同义词在散列表中是相邻的。8不论数据如何组织，分别在10000个结点和10个结点的查找表中进行查找，前者的平均查找长度肯定比后者大。9在开散列表中不会出现堆积现象。10开散列表和闭散列表的装填因子都可大于、等于或小于1。三、填空题1评价查找效率的主要标准是_。2查找表的逻辑结构是_。集合

7、3对长度为100的顺序表，在等概率情况下，查找成功时的平均查找长度为_，在查找不成功时的平均查找长度为_。4在150个结点的有序表中二分法查找，不论成功与否，键值比较次数最多为_。5索引顺序表上的查找分两个阶段：_、_。6从n个结点的二叉排序树中查找一个元素，平均时间复杂性大致为_。7散列表中同义词是指_。8散列表既是一种_方式又是一种_方法。9散列表中要解决的两个主要问题是：_、_。10散列表的冲突处理方法有_和_两种，对应的散列表分别称为开散列表和闭散列表。四、应用题、综合题4对关键字序列11,78,10,34,47,2,59,21构造散列表，取散列函数为H(K)K11，用链地址法解决冲突

8、，画出相应的散列表，并分别求查找成功和不成功时的平均查找长度。4根据元素插入的先后次序不同，可构成多种形态的二叉排序树。请画出4棵含1，2，3，4四个元素且以1为根、深度为4的二叉排序树。4将一组键值28,21,41,6,12,70插入到散列表中，散列函数为H(key)=key5，1）计算各关键字的散列地址；2）画出相应的开散列表；3）计算等概率下查找成功时的平均查找长度。4对关键字序列（25, 16, 34, 39, 28, 56），1）画出按此序列生成的二叉排序树。2）计算等概率下查找成功时的平均查找长度。4已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,

9、76)，1）画出对应的二分查找判定树；2）计算等概率时查找成功的平均查找长度。4将一组键值28,21,41,6,12,70,69插入到表长为9的散列表中，散列函数采用除余法，用线性探查法解决冲突，1）计算各关键字的散列地址；2）画出相应的闭散列表；3）计算等概率下查找成功时的平均查找长度。4将一组键值18,21,41,6,12,67插入到散列表中，散列函数为H(key)=key7，1）计算各关键字的散列地址；2）画出相应的开散列表；3）计算等概率下查找成功时的平均查找长度。1已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的二分查找判定树，求

10、出其平均查找长度。平均查找长度等于29/102假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出查找成功和不成功的平均查找长度(指关键字比较次数)。若查找键值20，需要进行几次关键字比较？成功时平均查找长度32/10；比较3次：38、25、163请画出从下面的二叉排序树中删除关键码40后的结果。4对关键字序列23,45,14,17,9,29,37,18构造散列表，取散列地址为HT0.6，散列函数为H(K)K7，用拉链法解决冲突，画出相应的散列表，并求在等概率下，查找成功时的平均查找长度。5已知散列函数为H(k)k1

11、1，关键值序列为25、21、41、6、12、69、20、15、22。6用线性探测法处理冲突，散列表长度为12。试画出该散列表，并分别计算查找成功和不成功时关键字的平均比较次数。7在包含n个关键字的线性表里进行顺序查找，若查找第i个关键字的概率为pi，pi如下分布：p1=1/2,p2=1/4,.,pn-1=1/2n-1,pn=1/2n。求成功检索的平均比较次数。8若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?(1).搜索失败;(2).搜索成功, 且表中只有一个关键码等于给定值k的对象;(3).搜索成功, 且表中有若干个关键码

12、等于给定值k的对象, 要求一次搜索找出所有对象。解：(1) 不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。(2) 相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。(3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。五、程序分析与填空1编写算法，返回二叉排序树中的关键字最大（或最小）的结点地址。提示：关键字最大的结点是“最右下”的结点；关键

13、字最小的结点是“最左下”的结点。 pointer search(bitree t)pointer p;if(t=NULL)return NULL; /空树p=t;while(p->rchild!=NULL) p=p->rchild;/向右下搜索return p;2编写算法，在二叉排序树中查找键值为K的结点。pointer search(bitree t,keytype K) /递归算法if(t=NULL) return NULL;/空树if(t->data=K) return t;/找到else if(t->data>K) return search(t->

14、lchild,K);/找左子树else return search(t->rchild,K);/找右子树=候选2对有n个记录的有序表采用二分查找，其平均查找长度的量级为( )。A O(n)B O(n2)C O(1)D O(log2n)2对长度为n的有序表二分查找，则对所有元素的最长查找长度为( )。A.élog2(n+1)ùB. élog2nùC. én/2ùD. é(n+1)/2ù2对长度为n的有序表二分查找，则对所有元素的最长查找长度为( )。A. ëlog2(n+1)û+1B. &#

15、235;log2nû+1C. ën/2û+1D. ë(n+1)/2û+12对长度为100的有序表二分查找，若查找不成功，至少比较( )次。A、9B、8C、7D、66二分查找法要求查找表中各元素的键值必须是( )排列。A.递增或递减B.递增C.递减D.无序33散列存储中，冲突是指( )。A两个元素具有相同的序号B两个记录的关键字相同C数据元素过多D不同关健字值对应相同的存储地址20查找表内元素的关键字一定是整型量。20静态查找表的检索与修改被分成两个不交叉的阶段分别进行。20在n个结点的有序表中进行二分查找，关键字比较次数最多为(n+1)/2。1

16、0二叉排序树的中序遍历序列是递增的，所以前序或后序遍历序列不可能也是递增的。20若两棵二叉排序树的中序序列相同，则它们的形态也相同。20在二叉排序树的查找中，能逐步缩小查找范围，故效率肯定比顺序查找快。20二叉排序树是用来进行排序的。20冲突处理的开放地址法就是当冲突发生后，依次探查冲突地址后面的各地址单元，直到找到一个空单元或所找关键字为止。10装填因子对闭散列表的查找效率影响较大，对开散列表影响不大。10线性探查法在解决同义词冲突的过程中，可能引起非同义词的冲突。20开散列表的查找效率一般高于闭散列表。20散列表可从关键字算出存放地址，故查找中实际没有必要进行关键字的比较。4等概率情况下，

17、对长度为n的顺序表，查找任一元素的平均查找长度为( )。A .nB.n+1C. (n-1)/2D. (n+1)/21等概率情况下，对长度为n的单链有序表，查找任一元素的平均查找长度为( )。A.n/2B.(n+1)/2C.(n-1)/2D.n/410在索引查找中，若主表长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为( )。A .n+kB. k+n/kC. (k+n/k)/2D. (k+n/k)/2+13在索引查找中，若主表长度为n，它被均分为若干个子表，每个子表的长度均为s，则索引查找的平均查找长度为( )。A. (n+s)/2B. (n/s+s)/2+1C

18、. (n+s)/2+1D. (n/s+s)/214从n个结点的二叉搜索树中查找一个元素，最坏时间复杂性为( )。A.O(n)B.O(1)C.O(log2n)D.O(n2)4按递增顺序输入n个记录所建立的二叉排序树，平均查找长度的量级为( )。A.O(n)B.O(nlog2n )C.O(1)D.O(log2n)4在深度为h的n个元素的二叉排序树中，查找所有元素的最长查找长度为( )。A.nB.log2nC.(h+1)/2D.h4从n个结点的二叉搜索树中查找一个元素，平均时间复杂性大致为( )。A.O(n)B.O(1)C.O(log2n)D.O(n2)4. 向n个结点的二叉搜索树中插入一个元素，时

19、间复杂性大致为( )。A.O(1)B.O(log2n )C.O(n)D.O(nlog2n)4根据n个元素建立一棵二叉搜索树，时间复杂性大致为( )。A.O(n)B.O(log2n )C.O(n2)D.O(nlog2n)5对包含n个关键字的平衡二叉排序树进行检索，平均检索长度是( )。AO(log2n)BO(n)C不确定D(nlog2n)8在索引表中，若一个索引项对应主表中的一条记录，则称此索引为_索引，若对应主表中的若干条记录，则称此索引为_索引。7在索引表中，每个索引项至少包含有_域和_域这两项。9若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个记录的索引，

20、则一级索引表的长度为_，二级索引表的长度为_。11平衡二叉排序树高度的数量级为_。O(n)12对m阶B_树，每个非根结点的关键字数目最多为_个。14在B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度_。13对m阶B-树，若某结点因插入新关键字而引起结点分裂，则此结点原有的关键字的个数是_；20线性探测中的堆积现象是指_。15散列表中冲突是指_。10对关键字集合1,2,3，所有可能的二叉排序树有_棵。=综合2在长度为9的有序表二分查找，则等概率时查找成功的平均搜索长度为( )。A. 209B. 189C. 259D. 2292对长度为18的有序表二分查找，则查找第15个元素的

21、查找长度为( )。A、3B、4C、5D、62在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为89和12的结点时，所需进行的比较次数分别为( )。A4，3B3，3C4，4D3，42有一个长度为20的有序表采用二分查找方法进行查找，共有_个元素的查找长度为3。3若数组A1.20的元素按关键字递增，某个元素x处于A6位置，则用二分法查找该元素时所需要比较的数组元素序列为 。7从有序表(12,18,30,43,56,78,82,95)中分别二分查找43和56时，其查找长度分别为_和_。3假定对长度n=50的有序表进行二分查找，则对应的判定树高度为_，判定树中前5层

22、的结点数为_，最后一层的结点数为_。4利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行( )元素间的比较。A、4次B、5次C、7次D、10次7若根据查找表建立长度为m的闭散列表，采用线性探测法处理冲突，假定对一个元素第一次计算的散列地址为d，则下一次的散列地址为( )。A.dB.d+1C.(d+1)/mD.(d+1)%m7若根据查找表建立长度为m的闭散列表，采用二次探测法处理冲突，假定对一个元素第一次计算的散列地址为d，则第四次计算的散列地址为( )。A.(d+1)%mB.(d-1)%mC.(d+4)%mD.(d-4)%m7在采用线性探测法处理冲突的闭散列表上，假定装填因子a的值为0.5，则查找任一元素的平均查找长度为( )。A、1B、1.5C、2D、2.57在采用链接法处理冲突的开散列表上，假定装填因子a的值为4，则查找任一元素的平均查找长度为( )。A、3B、3.5C、4D、2.538设一个闭散列表的容量为m，用线性控测法解决冲突，