1、查找模拟试卷 2 及答案与解析一、单项选择题1 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。 【电子科技大学 2013 二、4(2 分)】【青岛大学 2000 五、1(2 分)】【烟台大学2007 一、2(2 分) 】（A）O(n)O(n)（B） O(n)O(1)（C） O(1)O(n)（D）O(1)O(1)2 线性表的动态链表存储结构与顺序存储结构相比，优点是( )。【暨南大学 2011一、3(2 分) 】（A）所有的操作算法实现简单（B）便于随机存取（C）便于插入与删除 （D）便于节省存储器空间3 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为( )
2、。【暨南大学 2010 一、14(2 分)】（A）存储结构（B）逻辑结构（C）链式存储结构（D）顺序存储结构4 若某线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用 ( )存储方式节省时间。【暨南大学 2010 一、5(2 分)】（A）单链表（B）双链表（C）单循环链表（D）顺序表5 根据教科书中线性表的实现方法，线性表中的元素必须是( )。 【北京理工大学 2007 一、1(1 分) 】（A）整数类型（B）字符类型（C）相同类型（D）结构类型6 若经常需要按序号查找线性表中的数据元素，采用( )比较合适。【北京理工大学 2007 一、2(1 分) 】（A）顺序存储结构（B）链式存储
3、结构（C）静态链表（D）链式存储结构或静态链表7 在顺序查找方法中，查找失败的比较次数为 n+1，如果成功和不成功的概率相等，对每个记录的查找概率为 Pi=1(2n)，那么平均查找长度 ASL 为( )。（A）3(n+1) 4（B） 3(n 一 1)4（C） (n+1)2（D）(n 一 1)28 顺序查找的时间复杂度为( )。（A）O(1)（B） O(1ogn)（C） O(n)（D）O(nlogn)9 以下关于顺序查找的特点说法错误的是( )。（A）顺序查找对表中数据元素的存储没有要求（B）对于线性链表，只能进行顺序查找（C）当 n 很大时，平均查找长度较大，效率高（D）顺序查找既可以用顺序存
4、储也可以用链式存储10 利用折半查找的前提是( )。（A）查找表中的所有记录是按降序排列的（B）查找表中的所有记录是按升序排列的（C）查找表中的所有记录是按关键字有序(升序或降序)（D）查找表中的所有记录是无序11 折半查找中用 Low、High 和 Mid 表示待查找区间的下界、上界和中间位置指针，初值为 Low=1，High=n，那么 Mid 指向( )。（A）(Low+High)2 （B） (Low+High)2（C） (HighLow)2 （D）(High Low)212 在下面折半查找的源码中，空白处应该填入的内容( )。（A）Low=Mid 一 1，High=Mid+1（B） Hi
5、gh=Mid 一 1，Low=Mid+1（C） Low=Mid+1，High=Mid 一 1（D）High=Mid+1，Low=Mid 一 113 折半查找的时间复杂度为( )。（A）O(1)（B） O(10gn)（C） O(n)（D）O(nlogn)14 二叉查找树的查找效率与二叉树的( )有关。（A）高度（B）结点的多少（C）树形（D）结点的位置15 二叉查找树的查找效率( )时最低。（A）结点太多（B）完全二叉树（C）呈单枝树（D）结点太复杂16 二叉查找树的查找效率( )时最高。（A）结点太多（B）完全二叉树（C）呈单枝树（D）结点太复杂17 当采用分块查找时，数据的组织方式为( )。
6、（A）数据分成若干块，每块内数据有序（B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块（C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块（D）数据分成若干块，每块(除最后一块外)中数据个数需相同18 分块查找的平均查找长度是指( )。（A）查找分块索引表时的平均查找长度（B）块内进行顺序查找的平均查找长度（C）查找索引表和块内顺序查找的平均查找长度之和（D）无法确定19 将长度为 n 的表分成 6 块，且每块含 s 个元素，假定表中每个元素的查找概率相等，那么分块查找的平均查找长度为( )。（A）b+s（B） (b+s)2（C
7、） (ns+s) 2（D）(b+s)2+120 分块查找的块间是有序的，可以用折半查找法确定待查元素所在的块。如果将长度为 n 的表分成 6 块，且每块含 s 个元素，假定表中每个元素的查找概率相等，那么分块查找的平均查找长度为( )。（A）b+s（B） 1og2(b+s)2（C） 1og2(ns+s) 2+1（D）1og2(ns+1)+s 221 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列( )查找方法。（A）分块（B）顺序（C）二分法（D）哈希22 下面关于 B-树和 B+树的叙述中，不正确的是( )。（A）B-树和 B+树都是平衡的多分树（B） B-树和 B+
8、树都可用于文件的索引结构（C） B-树和 B+树都能有效地支持随机检索（D）B-树和 B+树都能有效地支持顺序检索23 关于 B-树，下列说法不正确的是( )。（A）B-树是一种查找树（B）所有的叶结点具有相同的高度（C） 2-3 树中，所有非叶子结点有 1 或者 3 个孩子结点（D）通常情况下，B-树不是二叉树24 高度为 5(除叶子层之外)的三阶 B-树至少有( )个结点。（A）30（B） 31（C） 32（D）3325 下列的叙述不正确的个数是( )。（A）1（B） 2（C） 3（D）426 在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测
9、的这些位置的键值( )。（A）一定都是同义词（B）一定都不是同义词（C）不一定都是同义词（D）都相同27 已知一个线性表为(38，25，74，63，52，48)，假定采用 H(K)=K mod 7 计算散列地址进行散列存储，若利用线性探测的开放定址法处理冲突，则在该散列表上进行查找的平均查找长度为 ( )；若利用链地址法处理冲突，则在该散列上进行查找的平均查找长度为( ) 。（A）15，1（B） 17，32（C） 2，43（D）23，7628 下列有关散列查找的叙述正确的是( )。（A）散列存储法只能存储数据元素的值，不能存储数据元素之间的关系（B）散列冲突是指同一个关键字对应多个不同的散列地
10、址（C）用线性探测法解决冲突的散列表中，散列函数值相同的关键字总是存放在一片连续的存储单元中（D）若散列表的装填因子 1，则可避免冲突的产生二、综合题29 在长度由 n 的线性表中进行顺序查找。查找第 i 个数据元素概率为 Pi，且分布如下： 请求出在该线性表中查找成功的平均查找长度(要求写成若干 n 的简单表达式形式)。30 请写一非递归算法，该算法在按值严格递增排列的顺序表 A1，n中采用折半查找法查找值不小于 item 的最小元素。若表中存在这样的元素，则算法给出该最小元素在表中的位置：否则，给出信息 0。31 如果我们使用线性探测在 Hash 法为 1000 个元素设计 Hash 表，
11、Hash 函数的类型为 Hash (x)=x mod D。假定我们要求查找成功时平均查找长度不大于 4，不成功时平均查找长度不大于 185。那么为了满足上述要求，D 的值最少应为多少?32 请画出在下列 3 阶 B 一树中插入关键字 10 以后的 B-树的状态。 33 假定我们使用 B 一树结构来组织一些位于磁盘上的文件数据。请问为什么 B-树的阶数选择得过大或过小都会使数据查找的性能受到严重影响?34 写出 Hash 查找法的定义。Hash 查找法有何特点?什么叫冲突?35 假定有 k 个关键字互为同义词，若用线性探测法将这 k 个关键字存人散列表中，至少需要进行多少次探测?36 已知一组关
12、键字为(112，214，305，46，57，86，72，162，95)，现用散列函数 H(k)=k10 将它们散列到表 HT(0，9)中，用线性探测法 H(k)，H(k)+1，H(k)+2，H(k) 一 1 解决冲突，画出最后的散列表，并计算产生冲突的次数。36 已知一组关键字为(26，36，41，38，44，15，68，12，6，51，25)，用链地址法解决冲突。假设装填因子 =075，散列函数的形式为 H(K)=K MOD P，回答下列问题：37 构造散列函数38 画出散列表39 计算出等概率情况下查找成功的平均查找长度40 计算出等概率情况下查找不成功的平均查找长度查找模拟试卷 2 答案
13、与解析一、单项选择题1 【正确答案】 A2 【正确答案】 C3 【正确答案】 C4 【正确答案】 D5 【正确答案】 C6 【正确答案】 A7 【正确答案】 A【试题解析】 查找失败的比较次数为 n+1，若成功与不成功的概率相等，对每个记录的查找概率为 Pi=1 (2n)，则平均查找长度 【知识模块】 查找8 【正确答案】 C【试题解析】 平均查找长度的数量级就是查找算法的时间复杂度，其为 O(n)。【知识模块】 查找9 【正确答案】 C【试题解析】 当 n 很大时，平均查找长度较大，效率低。顺序查找对表中数据元素的存储没有要求，顺序存储或是链式存储均可。另外，对于线性链表，只能进行顺序查找。
14、【知识模块】 查找10 【正确答案】 C【试题解析】 查找表中的所有记录是按关键字有序(升序或降序)。【知识模块】 查找11 【正确答案】 A【试题解析】 中间位置的值为(Low+High)2。【知识模块】 查找12 【正确答案】 C【试题解析】 如果在待排序列的后面部分的话，Low=Mid+1；反之，High=Mid一 1。【知识模块】 查找13 【正确答案】 B【试题解析】 每查找一次会减少一半的数据，因此时间复杂度为 D(1ogn)。【知识模块】 查找14 【正确答案】 C【试题解析】 二叉查找树的查找效率与二叉树的树形，平衡二叉树的查找效率高于左单支和右单支的树形的查找效率。【知识模块
15、】 查找15 【正确答案】 C【试题解析】 呈单枝树时的查找效率为 O(n)，效率最低。【知识模块】 查找16 【正确答案】 B【试题解析】 完全二叉树的查找效率 O(1ogn)，效率较高。【知识模块】 查找17 【正确答案】 B【试题解析】 本题主要考查分块查找的相关概念。块之间是有序的，块内可以无序。【知识模块】 查找18 【正确答案】 C【试题解析】 分块查找的平均查找长度由两部分构成，即查找索引表时的平均查找长度为 LB，以及在相应块内进行顺序查找的平均查找长度为LW， ASLbs=LB+LW。【知识模块】 查找19 【正确答案】 D【试题解析】 假定将长度为 n 的表分成 b 块，且
16、每块含 s 个元素，则 b=ns 。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为 1b，块中每个元素的查找概率为 1s。若用顺序查找法确定待查元素所在的块，则有 【知识模块】 查找20 【正确答案】 D【试题解析】 若用折半查找法确定待查元素所在的块，则有： L B=log2(b+1)一 1 【知识模块】 查找21 【正确答案】 A【试题解析】 由于题目只说明是线性表，因此排除二分法。哈希算法虽然有最快的查找效率，但建立哈希表无法适应动态变化的要求。在数据量大的查找中，顺序查找显然缺乏效率，因此应选择使用分块查找方法。【知识模块】 查找22 【正确答案】 D【试题解析】 因为 B
17、+树所有的叶子结点中包含了全部关键字信息，以及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接，所以支持从根结点的随机检索和直接从叶子结点开始的顺序检索，但是 B-树不具有这种结构特性，所以只支持从根结点的随机检索，而不支持直接从叶子结点开始的顺序检索。【知识模块】 查找23 【正确答案】 C【试题解析】 B-树定义如下：一棵 m 阶 B-树，或者是空树，或者是满足以下性质的 m 叉树： (1)根结点或者是叶子，或者至少有两棵子树，至多有 m 棵子树； (2)除根结点外，所有非终端结点至少有 m2 棵子树，至多有 m 棵子树； (3)所有叶子结点都在树的同一层上； (
18、4)每个结点应包含如下信息：(n，A 0，K 1，A 1，K 2，A 2，K n，A n)其中： K i(1in)是关键字，且KiK i+1(1in-1)； A i(i=0，1，n)为指向孩子结点的指针，且 Ai 一 1 所指向的子树中所有结点的关键字都小于 Ki，A i 所指向的子树中所有结点的关键字都大于 Ki；n 是结点中关键字的个数，且 m2 一 1nm 一 1，n+1 为子树的棵数。【知识模块】 查找24 【正确答案】 B【试题解析】 由 m 阶 B-树性质可知，根结点至少有两棵子树，根结点之外的所有非终端结点至少有 m2 棵子树，则三阶 B-树的形状至少类似于一棵满二叉树，也即高度
19、为 5 的三阶 B-树至少有(2 5 一 1)=31 个结点。【知识模块】 查找25 【正确答案】 A【试题解析】 (1)(2)(4) 正确， (3)错误。因为如果发生多次冲突，则同义词在表中就不会相邻。【知识模块】 查找26 【正确答案】 C【试题解析】 采用线性探测法处理冲突会产生堆积，即非同义词争夺同一个后继地址。【知识模块】 查找27 【正确答案】 C【试题解析】 若利用线性探测的开放定址法处理冲突，发生 0 次冲突的关键字有3 个，1 次冲突的 1 个，2 次冲突的 1 个，3 次冲突的 1 个，因而在该散列表上进行查找的平均查找长度为 ASL= (3+1+1+2+l+3+1+4)6
20、=2；若利用链地址法处理冲突，同一链表上有 1 个元素的线性链表有 2 个，有 2 个元素的线性链表有 2 个，因此ASL=(41+22)6=43。【知识模块】 查找28 【正确答案】 A【试题解析】 在散列表中，每个元素的存储位置通过散列函数和解决冲突的方法得到，散列存储法只存储数据元素的值，不能存储数据元素之间的关系，所以选项A 正确；散列冲突是指多个不同关键字对应相同的散列地址，选项 B 错误；用线性探测法解决冲突的散列表中，散列函数值相同的关键字不一定总是存放在一片连续的存储单元中，选项 C 错误。装填因子越小，发生冲突的概率越小，但仍有可能发生冲突。【知识模块】 查找二、综合题29
21、【正确答案】 本题考查平均查找长度的计算方法。平均查找长度： 【知识模块】 查找30 【正确答案】 本题实质上是在考查二分查找算法。im Binaryserach(Sequence*s，Keytype item)int low，high，mid； int flag=0；low=1；high=s 一 length；while(1owhigh)mid=(1aigh+low)2； 获得中间位置的结点下标if(itemsmidkey) 调整到左分区high=mid 一 1；else if(itemsmidkey) 调整到右分区low=mid+1； elseif(item=smidkey) return
22、 mid； 正好找到 item 本身if(1ow=high)if(s1owkeysitem)return low+1； 最后停止在左半区，指向比 item 小的第一个数据else if(s1owkeyitem)return low； 最后停止在右半区，指向的数据是第一个大于 item 的elsereturn O；【知识模块】 查找31 【正确答案】 1000DD7D18521D 最少是 32。【知识模块】 查找32 【正确答案】 本题考查 B-树中的插入，注意最终的所有叶子结点都需要在同一层上插入关键字 10 以后的 B-树。 【知识模块】 查找33 【正确答案】 阶数选择过小，则 B 一树的
23、层数会越大，由于 B-树存储在磁盘里，如果层数过多，在磁盘上查找的次数会更多；阶数选择过大，则在每个结点中的比较次数就会变多。【知识模块】 查找34 【正确答案】 哈希查找是通过计算数据元素的存储地址进行查找的一种方法。哈希查找的特点是查找迅速。不同的关键字得到相同的地址的现象称为冲突。【知识模块】 查找35 【正确答案】 查找次数：1+2+k=(1+k)k 2【知识模块】 查找36 【正确答案】 (1)利用哈希函数计算各元素的哈希值： H(112)=11210=2； H(214)=214 10=4； H(305)=30510=5； H(46)： 4610=6； H(57)=5710=7； H
24、(86)=8610=6； H(72) ： 7210=2 ； H(162)=162lO=2； H(95)=9510=5。 (2)得到的散列表如下： 冲突次数：2+1+7+5=15。【知识模块】 查找【知识模块】 查找37 【正确答案】 用链地址法解决冲突构造散列表，并对查找性能进行分析。由于 =075，得表长 m=11075=15。 在一般情况下，H(K)=K MOD P 中，P 取质数或者不包含小于 20 的质因数的和数，因此选择 P=13。散列函数 H(K)=K MOD 13【知识模块】 查找38 【正确答案】 求散列表： H(26)=26 MOD 13=0 ； H(36)=36 MOD 1
25、3=10； H(41)=41 MOD 13=2； H(38)=38 MOD 13=12 ； H(44)=44 MOD 13=5； H(15)=15 MOD 13=2； H(68)=68 MOD 13=3； H(12)=12MOD 13=12； H(6)=6 MOD 13=6 ； H(51)=51 MOD 13=12； H(25)=25 MOD 13=12 。 可以得出散列表如下所示： 【知识模块】 查找39 【正确答案】 等概率情况下查找成功的平均查找长度：ASL=(17+22+31+41)11=1811。【知识模块】 查找40 【正确答案】 等概率情况下查找不成功的平均查找长度：ASL=(15+21+41)13=11 13 。【知识模块】 查找
