数据结构第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，则查找任一元素的平均查找长度为()。A．5.5B．

2、5C．39/8D．19/45．()存储方式适用于折半查找。A．键值有序的单链表B．键值有序的顺序表C．键值有序的双链表D．键值无序的顺序表6．对线性表进行二分查找时，要求线性表必须()。A．以顺序方式存储B．以链接方式存储C．顺序存储，且结点按关键字有序排序D．链式存储，且结点按关键字有序排序7．在索引顺序表中查找一个元素，可用的且最快的方法是()。A．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找B．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D．用二分查找法确定元素所在块，再用二分查找法

3、在相应块中查找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，3

4、9，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．右图是一棵()。A．4阶B-树B．4阶B+树C．

5、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个关键字互为同义词，若用

6、线性探测法把这k个关键字存入散列表中，至少要进行()次探侧。A．k-1B．kC．k+1D．k(k+1)/2二、判断题1．顺序查找法不仅可用于顺序表上的查找，也可用于链表上的查找。2．二分查找所对应的判定树，是一棵理想平衡的二叉排序树。3．二叉排序树的形态与关键字的输入序列有关，但平衡二叉排序树是相同的。4．如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树。5．二叉排序树上，以根到任一结点的路径为界，则：路径左边结点＜路径结点＜路径右边结点。1535506570454030256．在二叉排序树中，即使删除一个结点后马上再插入该结点，该二叉排序树的形态也可能不

7、同。7．用线性探测法解决突出时，同义词在散列表中是相邻的。8．不论数据如何组织，分别在10000个结点和10个结点的查找表中进行查找，前者的平均查找长度肯定比后者大。9．在开散列表中不会出现堆积现象。10．开散列表和闭散列表的装填因子都可大于、等于或小于1。三、填空题1．评价查找效率的主要标准是____。2．查找表的逻辑结构是____。集合3．对长度为100的顺序表，在等概率情况下，查找成功时的平均查找长度为____，在查找不成功时的平均查找长度为____。4．在150个结点的有序表中二分法查找，不论成功与否，键值比较次数最多