[考研类试卷]查找模拟试卷2及答案与解析.doc

上传人:twoload295 文档编号:839397 上传时间:2019-02-21 格式:DOC 页数:19 大小:261.50KB
下载 相关 举报
[考研类试卷]查找模拟试卷2及答案与解析.doc_第1页
第1页 / 共19页
[考研类试卷]查找模拟试卷2及答案与解析.doc_第2页
第2页 / 共19页
[考研类试卷]查找模拟试卷2及答案与解析.doc_第3页
第3页 / 共19页
[考研类试卷]查找模拟试卷2及答案与解析.doc_第4页
第4页 / 共19页
[考研类试卷]查找模拟试卷2及答案与解析.doc_第5页
第5页 / 共19页
点击查看更多>>
资源描述

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 。【知识模块】 查找

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 考试资料 > 大学考试

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1