《数据结构第8章查 找练 习题资料》由会员分享，可在线阅读，更多相关《数据结构第8章查 找练 习题资料（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-dataK) return search(t-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. log2nC. n/2D. (n+1)/22对长度为n的有序表二分查找，则对所有元素的最长查找长度为( )。A. log2(n+1)+1B. log2n+1C. n/2+1D. (n+1)/2+12对长度为100的有序表二分查找，若查找不成功
