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

一、单选题1．下列查找方法中，不属于动态的查找方法是()。A．二叉排序树法B．平衡树法C．散列法D．二分查找法2．适用于静态的查找方法为()。A．二分查找、二叉排序树查找B．二分查找、索引顺序表查找C．二叉排序树查找、索引顺序表查找D．二叉排序树查找、散列法查找3．静态查找表与动态查找表二者的根本差别在于()。A．它们的逻辑结构不一样B．施加在其上的操作不同C．所包含的数据元素的类型不一样D．存储实现不一样4．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为()。A．5.5B．5C．39/8D．19/45．()存储方式适用于折半查找。A．键值有序的单链表B．键值有序的顺序表C．键值有序的双链表D．键值无序的顺序表6．对线性表进行二分查找时，要求线性表必须()。A．以顺序方式存储B．以链接方式存储C．顺序存储，且结点按关键字有序排序D．链式存储，且结点按关键字有序排序7．在索引顺序表中查找一个元素，可用的且最快的方法是()。A．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找B．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D．用二分查找法确定元素所在块，再用二分查找法在相应块中查找8．在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为()。A．13B．24C．12D．799．由同一关键字集合构造的各棵二叉排序树()。A．形态和平均查找长度都不一定相同B．形态不一定相同，但平均查找长度相同C．形态和平均查找长度都相同D．形态相同，但平均查找长度不一定相同10．对二叉排序树进行()，可以得到各结点键值的递增序列。A．先根遍历B．中根遍历C．层次遍历D．后根遍历11．下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序列？A．2，25，40，39，53，34，35B．25，39，2，40，53，34，35C．53，40，2，25，34，39，35D．39，25，40，53，34，2，3512．在AVL树中，每个结点的平衡因子的取值范围是()。A．-11B．-22C．12D．0113．在AVL树中，任一结点的()。A．左、右子树的高度均相同B．左、右子树高度差的绝对值不超过1C．左、右子树的结点数均相同D．左、右子树结点数差的绝对值不超过114．下面关于B树和B+树的叙述中，不正确的是A．都是平衡的多叉树B．都是可用于文件的索引结构C．都能有效地支持顺序检索D．都能有效地支持随机检索15．右图是一棵()。2822221915100528261040A．4阶B-树B．4阶B+树C．3阶B-树D．3阶B+树16．对包含n个关键字的散列表进行检索，平均检索长度是()。A．O(log2n)B．O(n)C．不直接依赖于nD．O(nlog2n)17．在散列查找中，平均查找长度主要与()有关。A．散列表长度B．散列元素的个数C．装填因子D．处理冲突方法18．要解决散列引起的冲突问题，常采用的方法有()。A．数字分析法、平方取中法B．数字分析法、线性探测法C．二次探测法、平方取中法D．二次探测法、链地址法19．从理论上讲，将数据以()结构存放，查找一个数据的时间不依赖于数据的个数n。A．二叉查找树B．链表C．散列表D．顺序表20．假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行()次探侧。A．k-1B．kC．k+1D．k(k+1)/2二、判断题1．顺序查找法不仅可用于顺序表上的查找，也可用于链表上的查找。2．二分查找所对应的判定树，是一棵理想平衡的二叉排序树。3．二叉排序树的形态与关键字的输入序列有关，但平衡二叉排序树是相同的。4．如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。5．二叉排序树上，以根到任一结点的路径为界，则：路径左边结点＜路径结点＜路径右边结点。6．在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不同。7．用线性探测法解决突出时，同义词在散列表中是相邻的。8．不论数据如何组织，分别在10000个结点和10个结点的查找表中进行查找，前者的平均查找长度肯定比后者大。9．在开散列表中不会出现堆积现象。10．开散列表和闭散列表的装填因子都可大于、等于或小于1。三、填空题1．评价查找效率的主要标准是____。2．查找表的逻辑结构是____。集合3．对长度为100的顺序表，在等概率情况下，查找成功时的平均查找长度为____，在查找不成功时的平均查找长度为____。4．在150个结点的有序表中二分法查找，不论成功与否，键值比较次数最多为____。5．索引顺序表上的查找分两个阶段：____、____。6．从n个结点的二叉排序树中查找一个元素，平均时间复杂性大致为____。45301525706550357．散列表中同义词是指____。8．散列表既是一种____方式又是一种____方法。9．散列表中要解决的两个主要问题是：____、____。10．散列表的冲突处理方法有____和____两种，对应的散列表分别称为开散列表和闭散列表。四、应用题、综合题4．对关键字序列{11,78,10,34,47,2,59,21}构造散列表，取散列函数为H(K)＝K％11，用链地址法解决冲突，画出相应的散列表，并分别求查找成功和不成功时的平均查找长度。4．根据元素插入的先后次序不同，可构成多种形态的二叉排序树。请画出4棵含1，2，3，4四个元素且以1为根、深度为4的二叉排序树。4．将一组键值{28,21,41,6,12,70}插入到散列表中，散列函数为H(key)=key％5，1）计算各关键字的散列地址；2）画出相应的开散列表；3）计算等概率下查找成功时的平均查找长度。4．对关键字序列（25,16,34,39,28,56），1）画出按此序列生成的二叉排序树。2）计算等概率下查找成功时的平均查找长度。4．已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，1）画出对应的二分查找判定树；2）计算等概率时查找成功的平均查找长度。4．将一组键值{28,21,41,6,12,70,69}插入到表长为9的散列表中，散列函数采用除余法，用线性探查法解决冲突，1）计算各关键字的散列地址；2）画出相应的闭散列表；3）计算等概率下查找成功时的平均查找长度。4．将一组键值{18,21,41,6,12,67}插入到散列表中，散列函数为H(key)=key％7，1）计算各关键字的散列地址；2）画出相应的开散列表；3）计算等概率下查找成功时的平均查找长度。1．已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的二分查找判定树，求出其平均查找长度。平均查找长度等于29/102．假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出查找成功和不成功的平均查找长度(指关键字比较次数)。若查找键值20，需要进行几次关键字比较？成功时平均查找长度32/10；比较3次：38、25、163．请画出从下面的二叉排序树中删除关键码40后的结果。2011406245083545603284．对关键字序列{23,45,14,17,9,29,37,18}构造散列表，取散列地址为HT[0..6]，散列函数为H(K)＝K％7，用拉链法解决冲突，画出相应的散列表，并求在等概率下，查找成功时的平均查找长度。5．已知散列函数为H(k)＝k％11，关键值序列为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).搜索成功,且表中有若干个关键码等于给定值k的对象,要求一次搜索找出所有对象。解：(1)不同。因为有序顺序表搜索到其关键码比要查找值大的对象时就停止搜索，报告失败信息，不必搜索到表尾；而无序顺序表必须搜索到表尾才能断定搜索失败。(2)相同。搜索到表中对象的关键码等于给定值时就停止搜索，报告成功信息。(3)不同。有序顺序表中关键码相等的对象相继排列在一起，只要搜索到第一个就可以连续搜索到其它关键码相同的对象。而无序顺序表必须搜索全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。五、程序分析与填空1．编写算法，返回二叉排序树中的关键字最大（或最小）的结点地址。提示：关键字最大的结点是“最右下”的结点；关键字最小的结点是“最左下”的结点。pointersearch(bitreet){pointerp;if(t==NULL)returnNULL;//空树p=t;while(p-rchild!==NULL)p=p-rchild;//向右下搜索returnp;}2．编写算法，在二叉排序树中查找键值为K的结点。pointersearch(bitreet,keytypeK)//递归算法{if(t==NULL)returnNULL;//空树if(t-data==K)returnt;//找到elseif(t-dataK)returnsearch(t-lchild,K);//找左子树elsereturnsearch(t-rchild,K);//找右子树}=》候选2．对有n个记录的有序表采用二分查找，其平均查找长度的量级为()。AO(n)BO(n2)CO(1)DO(log2n)2．对长度为n的有序表二分查找，则对所有元素的最长查找长度为()。A.log2(n+1)B.log2nC.n/2D.(n+1)/22．对长度为n的有序表二分查找，则对所有元素的最长查找长度为()。A.log2(n+1)+1B.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。10．二叉排序树的中序遍历序列是递增的，所以前序或后序遍历序列不可能也是递增的。20．若两棵二叉排序树的中序序列相同，则它们的形态也相同。20．在二叉排序树的查找中，能逐步缩小查找范围，故效率肯定比顺序查找快。20．二叉排序树是用来进行排序的。20．冲突处理的开放地址法就是当冲突发生后，依次探查冲突地址后面的各地址单元，直到找到一个空单元或所找关键字为止。10．装填因子对闭散列表的查找效率影响较大，对开散列表影响不大。10．线性探查法在解决同义词冲突的过程中，可能引起非同义词的冲突。20．开散列表的查找效率一般高于闭散列表。20．散列表可从关键字算出存放地址，故查找中实际没有必要进行关键字的比较。4．等概率情况下，对长度为n的顺序表，查找任一元素的平均查找长度为()。A.nB.n+1C.(n-1)/2D.(n+1)/21．等概率情况下，对长度为n的单链有序表，查