1、查找模拟试卷 1 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 已知一个长度为 16 的顺序表 L，其元素按关键字有序排列，若采用折半查找法查找一个不 L 中存在的元素，则关键字的比较次数最多是（ ）。（A）4（B） 5（C） 6（D）72 顺序查找适合于存储结构为（ ）的线性表。（A）顺序存储结构或链式存储结构（B）散列存储结构（C）索引存储结构（D）压缩存储结构3 对长度为 n 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功的平均查找长度为（ ）。（A）n2（B） (n+1)2（C） (n-1) 2（D）n44 对长度为 3 的顺序表进
2、行查找，若查找第一个元素的概率为 12，查找第二个元素的概率为 13，查找第三个元素的概率为 16，则查找到表中任一元素的平均查找长度为（ ）。（A）53（B） 2（C） 73（D）435 当采用分块查找时，数据的组织方式为（ ）。（A）数据分成若干块，每块内数据有序（B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干块，每块(除最后一块外)中数据个数需相同6 下列关于二分查找的叙述中，正确的是（ ）。（A）表必须有序，表可以顺序方式存储，也可以链表方式存储（B
3、）表必须有序且表中数据必须是整型，实型或字符型（C）表必须有序，而且只能从小到大排列（D）表必须有序，且表只能以顺序方式存储7 使用二分(折半) 查找查找元素的速度比用顺序法（ ）。（A）必然快（B）必然慢（C）相等（D）不能确定8 已知一个长度为 16 的顺序表，其元素按关键字有序排列，若采用折半查找查找一个不存在的元素，则比较的次数至少是（ ），至多是（ ）。（A）4（B） 5（C） 6（D）79 已知一个有序表(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为 90 的元素时，查找成功的比较次数为（ ）。（A）1（B） 2（C） 4（D）610 折半
4、查找过程所对应的判定树是一棵（ ）。（A）最小生成树（B）平衡二叉树（C）完全二叉树（D）满二叉树11 在有 11 个元素的有序表 A1，2，11中进行折半查找 (L(10w+high)/2)，查找元素 A11时，被比较的元素下标依次是（ ）。（A）6，8，10，11（B） 6，9，10，11（C） 6，7，9，11（D）6，8，9，1112 具有 12 个关键字的有序表中，对每个关键字的查找概率相同，折半查找查找成功的平均查找长度为（ ），折半查找查找失败的平均查找长度为（ ）。（A）3712（B） 3512（C） 3913（D）491313 对有 2500 个记录的索引顺序表(分块表)进行
5、查找，最理想的块长为（ ）。（A）50（B） 125（C） 500（D）log 2250014 为提高查找效率，对有 65025 个元素的有序顺序表建立索引顺序结构，在最好情下查找到表中已有元素最多需要执行（ ）次关键字比较。（A）10（B） 14（C） 16（D）2115 设顺序存储的某线性表共有 123 个元素，按分块查找的要求等分为 3 块。若对索表采用顺序查找方法来确定子块，且在确定的子块中也采用顺序查找方法，则在等概率的况下，分块查找成功的平均查找长度为（ ）。（A）21（B） 23（C） 41（D）6216 对表长为 n 的有序表进行折半查找，其判定树的高度为（ ）。（A）log
6、2(n+1)（B） log2(n+1)-1（C） log2n（D）Iog2n-117 图所示是一棵（ ）。（A）4 阶 B 树（B） 4 阶 B+树（C） 3 阶 B 树（D）3 阶 B+树18 下列叙述中，不符合 m 阶 B 树定义要求的是（ ）。（A）根结点最多有 m 棵子树（B）所有叶结点都在同一层上（C）各结点内关键字均升序或降序排列（D）叶结点之间通过指针链接19 下列关于 m 阶 B-树的说法错误的是（ ）。（A）根结点至多有 m 棵子树（B）所有叶结点都在同一层次上（C）非叶结点至少有 m2(m 为偶数)或 m2+1(m 为奇数)棵子树（D）根结点中的数据是有序的20 当在一棵
7、m 阶 B 树中做插入操作时，若一个结点中的关键字个数等于（ ），则必须分裂成两个结点，当向一棵 m 阶的 B 树做删除操作时，若一个结点中的关键字个数等于（ ），则可能需要同它的左兄弟或右兄弟结点合并成一个结点。（A）m，m2-2（B） m-1，m2-1（C） m+1，m 2（D）m2，m2+121 以下关于 m 阶 B 树的说法中正确的是（ ）。I,每个结点至少有两棵非空子树 II,树中每个结点至多有 m-1 个关键字,所有叶结点在同一层 ,当插入一个元素引起 B 树结点分裂后，树长高一层（A）I、II（B） II、III（C） I、IV（D）I、II、22 下列关于 B 树和 B+树的叙
8、述中，不正确的是（ ）。（A）B 树和 B+树都能有效地支持顺序查找（B） B 树和 B+树都能有效地支持随机查找（C） B 树和 B+树都是平衡的多叉树（D）B 树和 B+树都可以用于文件索引结构23 含有 n 个非叶结点的 m 阶 B-树中至少包含（ ）个关键字。（A）n(m+1)（B） n（C） n(m2-1)（D）(n-1)(1m2-1)+124 已知一棵 3 阶 B 树中有 2047 个关键字，则此 B 树的最大高度为（ ），最小高度为（ ）。（A）11（B） 10（C） 8（D）725 高度为 5 的 3 阶 B 树至少有（ ）个结点，至多有（ ）个结点。（A）32（B） 31（C
9、） 120（D）12126 已知一棵 5 阶 B 树中共有 53 个关键字，则树的最大高度为（ ），最小高度为（ ）。（A）2（B） 3（C） 4（D）527 具有 n 个关键字的 m 阶 B-树，应有（ ）个叶结点。（A）n+1（B） n-1（C） mn（D）nm228 为提高散列(Hash)表的查找效率，可以采取的正确措施是（ ）。 I,增大装填(载 )因子 II,设计冲突 (碰撞)少的散列函数 ,处理冲突( 碰撞)时避免产生聚集(堆积)现象（A）仅 I（B）仅 II（C）仅 I、II（D）仅 II、 I29 设有一个含有 200 个表项的散列表，用线性探测法解决冲突，按关键字查询时找到一
10、个表项的平均探测次数不超过 1.5，则散列表项应能够容纳（ ）个表项。(设查找成功的平均查找长度为 ASL=1+1/(1-a)2，其中 a 为填装因子)（A）400（B） 526（C） 624（D）67630 在开址法中散列到同一个地址而引起的“堆积”问题是由于（ ）引起的。（A）同义词之间发生冲突（B）非同义词之间发生冲突（C）同义词之间或非同义词之间发生冲突（D）散列表“ 溢出”31 采用开放定址法解决冲突的哈希查找中，发生聚集的原因主要是（ ）。（A）数据元素过多（B）负载因子过大（C）哈希函数选择不当（D）解决冲突的方法选择不当32 下列关于 Hash 查找说法中，不正确的有几个（ ）
11、。I,采用链地址法解决冲突时，查找一个元素的时间是相同的 II,采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的I,采用链地址法解决冲突易引起聚集现象,再哈希法不易产生聚集 V,哈希查找中不需要任何关键字的比较 ,哈希表在查找成功时平均查找长度与表长有关,若在哈希表中删除一个元素，只要简单地将该元素删除即可（A）2（B） 3（C） 4（D）533 Hash 查找一般适用于（ ）情况下的查找。（A）查找表为链表（B）查找表为有序表（C）关键字集合比地址集合大得多（D）关键字集合与地址集合之间存在对应关系34 假定有 K 个关键字互为同义词，若用线性探测法把这 K 个关
12、键字填入 Hash 表中，至少要进行（ ）次探测。（A）K-1（B） K（C） K+1（D）K(K+1) 235 设有一组记录的关键字为19，14，23，1，68，20，84，27，55，11，10，79 ，用链地址法构造散列表，散列函数为 H(key)=keyMOD13，散列地址为 1 的链中有（ ）个记录。（A）1（B） 2（C） 3（D）435 若采用链地址法构造散列表，散列函数为 H(key)=keyMOD17，则需( )个链表。这些链的链首指针构成一个指针数组，数组的下标范围为()。36 _;（A）17（B） 13（C） 16（D）任意37 _;（A）0 至 17（B） 1 至 17
13、（C） 0 至 16（D）1 至 1638 在采用链地址法处理冲突所构成的散列表上查找某一关键字，则在查找成功的情况下，所探测的这些位置上的键值（ ）；若采用线性探测法，则（ ）。（A）一定都是同义词（B）不一定都是同义词（C）都相同（D）一定都不是同义词39 设 Hash 表长 m=14，哈希函数为 H(key)=key 11，表中已有 4 个结点 H(15)=4，H(38)=5，H(61)=6 ，H(84)=7 ，其余地址为空，如用线性探测法处理冲突，则关键字为 49 的结点地址是（ ）。（A）8（B） 3（C） 5（D）940 对包含 n 个元素的散列表进行查找，平均查找长度（ ）。（A
14、）为 O(log2n)（B）为 O(n)（C）不直接依赖于 n（D）直接依赖于表长 m二、综合题41 求图的中心点的算法。设 v 是有向图 G 的一个顶点，把 v 的偏心度定义为：max从 w 到 v 的最短距离 1w 是 g 中所有顶点，如果 v 是有向图 G 中具有最小偏心度的顶点，则称顶点 v 是 G 的中心点。查找模拟试卷 1 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 B【试题解析】 具有 n 个结点的判定树的高度为 log2n+l，长度为 16，则高度为 5，所以最多比较 5 次。【知识模块】 查找2 【正确答案】 A【试题解析】 顺序查找
15、是从表的一端开始向另一端查找。它不要求查找表具有随机存取的特性，可以是顺序存储或链式存储。【知识模块】 查找3 【正确答案】 B【试题解析】 在有序单链表上做顺序查找，查找成功的平均查找长度与无序顺序表或有序顺序表相同，都是(n+1)2。【知识模块】 查找4 【正确答案】 A【知识模块】 查找5 【正确答案】 B【试题解析】 通常情况下，在分块查找的结构中，不要求每个索引块中的元素个数都相等。【知识模块】 查找6 【正确答案】 D【试题解析】 因为二分查找总是要通过下标来定位到中间元素，故而应该采用顺序存储结构，又二分查找能够进行的前提就是要求查找表是有序的，但具体是从大到小还是从大到小的顺序
16、这个则不做要求。【知识模块】 查找7 【正确答案】 D【试题解析】 折半查找的快体现在一般的情况下，对于某些特殊的情况，可能顺序查找会快于折半查找。(如查找一个含 1000 个元素的有序表中第一个元素，则顺序查找的比较次数为 1 次，而折半查找的比较次数却将近 10 次。)【知识模块】 查找8 【正确答案】 A【试题解析】 对于此类题，有两种做法：一种是将查找过程中构成的判定树画出来，然后最小的分枝高度对应于最少的比较次数，最大的分枝高度对应于最多的比较次数，当出现类似于长度为 15 的顺序表时，判定树刚好是一棵满树，此时，最多比较次数与最少比较次数相等；另一种方法是直接用公式求出最小的分枝高
17、度和最大分枝高度，从前面的讲解不难看出最大分枝高度为 H=log2(n+1)=5，这对应的就是最多比较次数。然后由于判定树不是一棵满树，所以至少应该是 4(由判定树的各分枝高度最多相差 1 得出)。值得注意的是，若是求查找成功或查找失败的平均查找长度，则需要画出判定树进行求解，如题 12。此外，对长度为 n 的有序表，采用折半查找时，查找成功和查找失败的最多比较次数相同，均为log 2(n+1)，最少比较次数也相同。【知识模块】 查找9 【正确答案】 B【试题解析】 开始时 low 指向 13，high 指向 134，mid 指向 50，比较第一次9050，所以将 low 指向 62，high
18、 指向 134，mid 指向 90，第二次比较找到 90。【知识模块】 查找10 【正确答案】 B【试题解析】 显然 A 应该排除。对于 C，前面的考点精析示例中的判定树就不是完全二叉树，所以 C 也排除。由 C 也可以排除 D，而且是否为满二叉树与查找元素的个数有关，从而选 B。事实上，由折半查找的定义也不难看出，每次把一个数组从中间结点分割时，总是把数组分为结点数相差最多不超过 1 的两个子数组，从而导致对应的判定树的两棵子树高度差绝对值不会超过 1。所以应该是平衡二叉树。【知识模块】 查找11 【正确答案】 B【知识模块】 查找12 【正确答案】 A【知识模块】 查找13 【正确答案】
19、A【知识模块】 查找14 【正确答案】 C【知识模块】 查找15 【正确答案】 B【知识模块】 查找16 【正确答案】 A【知识模块】 查找17 【正确答案】 A【知识模块】 查找18 【正确答案】 D【知识模块】 查找19 【正确答案】 C【知识模块】 查找20 【正确答案】 A【知识模块】 查找21 【正确答案】 B【知识模块】 查找22 【正确答案】 A【知识模块】 查找23 【正确答案】 D【知识模块】 查找24 【正确答案】 A【知识模块】 查找25 【正确答案】 B【知识模块】 查找26 【正确答案】 C【知识模块】 查找27 【正确答案】 A【知识模块】 查找28 【正确答案】
20、B【试题解析】 Hash 表的查找效率取决于：哈希函数、处理冲突的方法和装填因子。显然，冲突的产生概率与装填因子(即表中记录数与表长之比)的大小成正比，所以 I 与题意相反：I 错在“避免”二字，冲突是不可避免的。【知识模块】 查找29 【正确答案】 A【知识模块】 查找30 【正确答案】 C【试题解析】 在开址法中散列到同一个地址而产生的“堆积”问题，是由于为解决同义词冲突的探查序列和非同义词之间不同的探查序列交织在一起，导致关键字查询需要经过较长的探测距离，降低了散列的效率。所以要选择好的处理冲突的方法来避免“堆积”。【知识模块】 查找31 【正确答案】 D【试题解析】 聚集是因选取不当的
21、处理冲突的方法，而导致不同关键字的元素对同一哈希地址进行争夺的现象。当采用线性再探测法时，容易引发聚集现象。【知识模块】 查找32 【正确答案】 D【试题解析】 链地址法解决冲突时查找一个元素可能需要在链表中遍历，所需时间不一样，I 错误。同义词发生冲突不等于聚集，链地址法解决冲突时将同义词放在同一个链表中，不会引起聚集现象，I 错误。 Hash 查找的思想是计算 Hash 地址来进行查找，然后再比较关键字确定是否查找成功，V 错误。Hash 查找成功的平均查找长度与装填因子有关，与表长无关，错误。在开放定址的情形下，不能随便删除表中某个元素，否则可能会导致搜索路径被中断，错误。【知识模块】
22、查找33 【正确答案】 D【试题解析】 关键字集合与地址集合之间存在对应关系时，通过哈希函数表示这种关系，这样查找以计算哈希函数而不是比较的方式进行查找。【知识模块】 查找34 【正确答案】 D【知识模块】 查找35 【正确答案】 D【知识模块】 查找【知识模块】 查找36 【正确答案】 A【知识模块】 查找37 【正确答案】 C【知识模块】 查找38 【正确答案】 A【知识模块】 查找39 【正确答案】 A【试题解析】 线性探测法的公式为 Hi=(H(k)+di)m，其中 di=1，2，3，m-1。H(49)=4911=5，发生冲突；H 1=(H(49)+1) 14=6，冲突；H 2=(H(
23、49)+2)14=7，冲突；H 3=(H(49)+3)14=8，没有冲突。选 A。【知识模块】 查找40 【正确答案】 C【试题解析】 在散列表中，平均查找长度与填装因子 a 直接相关，表的查找效率不直接依赖于表中已有表项个数 n 或表长 m。【知识模块】 查找二、综合题41 【正确答案】 算法的基本设计思想：首先利用 FLOYD 算法求出每对顶点间的最短路径矩阵 W；然后对矩阵 W，求出每列 j 的最大值，得到顶点 j 的偏心度：最后在所有偏心度中，取最小偏心度的顶点 v 就是有向图的中心点。算法的代码：void FLOYDPXD(AdjMatrix g) 对以带权邻接矩阵表示的有向图 g，求其中心点AdjMatrix w=g; 将带权邻接矩阵复制到 wint s;int n=gvexnum； 将有向图的顶点个数赋给 nfor(int k=1；kwik+wkj)WiJ：Wik+wkj;V=1； 中心点初值顶点 v 为 1dist=MAXINT; 偏心度初值为机器最大数for(j=1，js)s=WiJ;if(Sdist) 各偏心度中最小值为中心点diSt=S;v=j; forprintf(“有向图 g 的中心点是顶点d，偏心度dn” ，v，dist); FLOYDPXD【知识模块】 查找
