tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

查找自测卷答案


查找
题号 题分 得分

自测卷答案
一 10 二 27

姓名
三 16 四 24

班级
五 23

A
总分 100

一、填空题(每空 1 分,共 10 分)
1. 在数据的存放无规律而言的线性表中进行检索的最佳方

法是 顺序查找(线性查找) 。 2. 线性有序表(a1,a2,a3,?,a256)是从小到大排列的,对一个给定的值 k,用二分法检索表中与 k 相 等的元素,在查找不成功的情况下,最多需要检索 8 次。设有 100 个结点,用二分法查找时,最大比 较次数是 7 。 3. 假设在有序线性表 a[20]上进行折半查找,则比较一次查找成功的结点数为 1;比较两次查找成功的结 点数为 2 ;比较四次查找成功的结点数为
5

8

;平均查找长度为

3.7 。

解:显然,平均查找长度=O(log2n)<5 次(2 ) 。但具体是多少次,则不应当按照公式
ASL ? n ?1 m log 2 (n ? 1) 来计算(即(21×log221)/20=4.6 次并不正确!。因为这是在假设 n=2 -1 的情况下 ) n

推导出来的公式。应当用穷举法罗列: 全部元素的查找次数为=(1+2×2+4×3+8×4+5×5)=74; ASL=74/20=3.7 !! ! 4.折半查找有序表(4,6,12,20,28,38,50,70,88,100) ,若查找表中元素 20,它将依次与表中 元素 28,6,12,20 比较大小。 。

5. 在各种查找方法中,平均查找长度与结点个数 n 无关的查找方法是 散列查找 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为 m 的散列表,初始状态为空,现将 n(n<m)个不同的关键码插入到散列表中,解决冲突 的方法是用线性探测法。 如果这 n 个关键码的散列地址都相同, 则探测的总次数是 n(n-1)/2= 1+2+? ( +n-1) 。(而任一元素查找次数 ≤n-1)

二、单项选择题(每小题 1 分,共 27 分)
( B )1.在表长为n的链表中进行线性查找,它的平均查找长度为 A. ASL=n; B. ASL=(n+1)/2; C. ASL= n +1; ( D. ASL≈log2(n+1)-1

A )2.折半查找有序表(4,6,10,12,20,30,50,70,88,100) 。若查找表中元素 58,则它 将依次与表中 比较大小,查找结果是失败。 A.20,70,30,50 B.30,88,70,50 C.20,50 D.30,88,50 次关键字。

( C )3.对 22 个记录的有序表作折半查找,当查找失败时,至少需要比较 A.3 B.4 C.5 D. 6 ( A )4. 链表适用于 A.顺序 查找 B.二分法

C.顺序,也能二分法

D.随机

1

( C

)5. 折半搜索与二叉搜索树的时间性能 A. 相同 B. 完全不同

C. 有时不相同

D. 数量级都是 O(log2n)

6.从供选择的答案中,选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏 内。 要进行线性查找, 则线性表 A ; 要进行二分查找, 则线性表 B ; 要进行散列查找, 则线性表 C 。 某顺序存储的表格,其中有 90000 个元素,已按关键项的值的上升顺序排列。现假定对各个元素进行查找 的概率是相同的,并且各个元素的关键项的值皆不相同。当用顺序查找法查找时,平均比较次数约为 D ,最大比较次数为 E 。 供选择的答案: A~C:① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式,也可以以链表方式存储 ⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好 D,E: ① 25000 ② 30000 ③ 45000 ④ 90000 答案: A= ④ B= ⑤ C= ③ D= ③ E= ④ 7.从供选择的答案中, 选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏内。 数据结构反映了数据元素之间的结构关系。链表是一种 A ,它对于数据元素的插入和删除 B 。 通常查找线性表数据元素的方法有 C 和 D 两种方法, 其中 C 是一种只适合于顺序 存储结构但 E 的方法;而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案: A:①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表 B: ① 不需要移动结点,不需改变结点指针 ②不需要移动结点,只需改变结点指针 ③只需移动结点,不需改变结点指针 ④既需移动结点,又需改变结点指针 C:① 顺序查找 ②循环查找 ③条件查找 ④二分法查找 D:① 顺序查找 ②随机查找 ③二分法查找 ④分块查找 E:① 效率较低的线性查找 ②效率较低的非线性查找 ③ 效率较高的非线性查找 ④效率较高的线性查找 答案:A= ④ B= ② C= ④ D= ① E= ③

9. 从供选择的答案中, 选出应填入下面叙述 ? 内的最确切的解答, 把相应编号写在答卷的对应栏内。 散列法存储的基本思想是根据 A 来决定 B ,碰撞(冲突)指的是 C ,处理碰撞的两类 主要方法是 D 。 供选择的答案 A,B: ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值 ⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间 C: ①两个元素具有相同序号 ② 两个元素的关键码值不同,而非码属性相同 ③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 D: ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法 答案:A= ④ B= ① C= ③ D= ④ 10.【91 程 P4】考虑具有如下性质的二叉树:除叶子结点外,每个
2

结点的值都大于其左子树上的一切结点的值。并小于等于其右子树上的一切结点的值。 现把 9 个数 1,2,3,?,8,9 填入右图所示的二叉树的 9 个结点中,并使之具有上述性质。此时, n1 的值是 A ,n2 的值是 B ,n9 的值是 C 。现欲把 10 放入此树并使该树保持前述性质,增

加的一个结点可以放在 D 或 E 。 供选择的答案 A~C: ①1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 D~E: ① n7 下面 ② n8 下面 ③ n9 下面 ④ n6 下面 ⑤ n1 与 n2 之间 ⑥ n2 与 n4 之间 ⑦ n6 与 n9 之间 ⑧ n3 与 n6 之间 答案:A= ⑦ B= ④ C= ⑥ D= ② E= ⑥

⑨ 9

三、简答题(每小题 4 分,共 16 分)
1.【全国专升本题】对分(折半)查找适不适合链表结构的序列,为什么?用二分查找的查找速度必然比 线性查找的速度快,这种说法对吗? 答:不适合!虽然有序的单链表的结点是按从小到大(或从大到小)顺序排列,但因其存储结构为单链表, 查找结点时只能从头指针开始逐步搜索,故不能进行折半查找。 二分查找的速度在一般情况下是快些, 但在特殊情况下未必快。 例如所查数据位于首位时, 则线性查找快; 而二分查找则慢得多。 2.假定对有序表: (3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题: (1) 画出描述折半查找过程的判定树; (2) 若查找元素 54,需依次与哪些元素比较? (3) 若查找元素 90,需依次与哪些元素比较? (4) 假定每个元素的查找概率相等,求查找成功时的平均查找长度。 解: (1) 先画出判定树如下(注:mid=?(1+12)/2?=6): 30 3 4 5 7 24 63 42 54 72 87 95

(2) 查找元素 54,需依次与 30, 63, 42, 54 等元素比较; (3) 查找元素 90,需依次与 30, 63,87, 95, 72 等元素比较; (4) 求 ASL 之前,需要统计每个元素的查找次数。判定树的前 3 层共查找 1+2×2+4×3=17 次;
3

但最后一层未满,不能用 8×4,只能用 5×4=20 次, 所以 ASL=1/12(17+20)=37/12≈3.08

3. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是 什么? 如果要求时间复杂度更小,你采用什么方法?此方法的时间复杂度是多少? 答:查找某个元素的时间复杂度下限,如果理解为最短查找时间,则当关键字值与表头元素相同时,比较 1 次即可。要想降低时间复杂度,可以改用 Hash 查找法。此方法对表内每个元素的比较次数都是 O(1) 。

4.设哈希(Hash)表的地址范围为 0~17,哈希函数为:H(K)=K MOD 16。 K 为关键字,用线性探测法再散列法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49) 造出 Hash 表,试回答下列问题: (1) 画出哈希表的示意图; (2) 若查找关键字 63,需要依次与哪些关键字进行比较? (3) 若查找关键字 60,需要依次与哪些关键字比较? (4) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。 解: (1)画表如下: 0 1 2 3 4 32 17 63 49

5

6

7

8 24

9 40

10 10

11

12

13

14 30

15 31

16 46

17 47

(2) 查找 63,首先要与 H(63)=63%16=15 号单元内容比较,即 63 vs 31 ,no; 然后顺移,与 46,47,32,17,63 相比,一共比较了 6 次! (3)查找 60,首先要与 H(60)=60%16=12 号单元内容比较,但因为 12 号单元为空(应当有空标记) ,所以 应当只比较这一次即可。 (4) 对于黑色数据元素,各比较 1 次;共 6 次; 对红色元素则各不相同,要统计移位的位数。 “63”需要 6 次, “49”需要 3 次, “40”需要 2 次, “46”需 要 3 次, “47”需要 3 次, 所以 ASL=1/11(6+2+3×3)=17/11=1.5454545454≈1.55

四、分析题(每小题 6 分,共 24 分)
1. 【严题集 9.3②】画出对长度为 10 的有序表进行折半查找的判定树,并求其等概率时查找成功的平均 查找长度。 解:判定树应当描述每次查找的位置: ASL=1/10(1+2×2+3×4+4×3) 5 =1/10(1+4+12+12) 2 8 1 3 6 9 =29/10=2.9 4 7 10

2. 【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为 12,7,17,11,16,2,13,9,
4

21,4,请画出所得到的二叉查找树。 答: 12 7 17 2 11 16 21 4 9 13 验算方法: 用中序遍历应得到排序结果: 2,4,7,9,11,12,13,16,17,21

3.已知如下所示长度为 12 的表: (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec) (1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其 在等概率的情况下查找成功的平均查找长度。 (2) 若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平 均查找长度。 解:

地址 0 1 2 3 4 5 6 7 8 9 10

值 22 66 41 08 30 53 46 01 31

链接指针

1 3 4,7

4. 选取散列函数 H(key)=(3*key)%11,用线性探测法处理冲突, 对下列关键码序列构造一个散列地址空间为 0~10, 表长为 11 的散列表, {22,41,53,08,46,30,01,31,66}。 解:由题意知,m=11(刚好为素数) 则(22*3)%11=6??0 (41*3)%11=11??2 (53*3)%11=14??5
5

(08*3)%11=2??2 (46*3)%11=12??6 (30*3)%11=8??2 (01*3)%11=0??3 (31*3)%11=8??5 (66*3)%11=9??0

22 0 1

66 1

41 2 3

8 3 4, 7

30 4

53 5

46 6

1 7

31 8

9

10

五、算法设计题(4 中选 3,第 1 题 7 分必选,其余每题 8 分,共 23 分)
1. 已知 11 个元素的有序表为(05 13 19 21 37 56 64 75 80 88 92), 请写出折半查找的算
法程序,查找关键字为 key 的数据元素 (建议上机调试)。 解:折半查找的 C 程序有很多参考资料,注意此题要求是整型量。 折半查找的一个递归算法如下,形式非常简洁! int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查找的递归算法 { if(low>high) return 0; //查找不到时返回 0 mid=(low+high)/2; if(ST.elem[mid].key= =key) return mid; else if(ST.elem[mid].key>key) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); } }//Search_Bin_Recursive

3. 已知一个含有 1000 个记录的表,关键字为中国人姓氏的拼音,请给出此表的一个哈希表设计方案,要 求它在等概率情况下查找成功的平均查找长度不超过 3。 解:设计哈希表的步骤为: a) 根据所选择的处理冲突的方法求出装载因子 a 的上界; b) 由 a 值设计哈希表的长度 m; c) 根据关键字的特性和表长 m 选定合适的哈希函数。 刘注:要求 ASL≤3,则 m 必然要尽量长,以减少冲突;

4. 已知某哈希表的装载因子小于 1,哈希函数 H(key)为关键字(标识符)的第一个字母在字母表中的序 号,处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键 字的算法。 解:注意此题给出的条件:装载因子 a〈1, 则哈希表未填满。由此可写出下列形式简明的算法: void PrintWord(Hash Table ht) {//按第一个字母的顺序输出哈希表 ht 中的标识符。 哈希函数为表示符的第一个字母在字母表中的序号, 处 理冲突的方法是线性探测开放定址法。
6

for(i=1; i<=26; i++){ j=i; While(ht.elem[j].key){ if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key); j=(j+1)%m; } } }//PrintWord

7


推荐相关:

第9章查找自测卷答案

第9 章 查找 自测卷答案题号 题分 得分 一 10 二 27 三 16 姓名四 24 班级五 23 总分 100 A 一、填空题(每空 1 分,共 10 分) 填空题( 1. 在...


第8章自测卷答案

第8 章 查找 自测卷答案 一、填空题(每空 1 分,共 10 分) 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找(线性查找) 。 2. 线性有...


第七章查找自测题答案

数据结构 第八章 查找自... 3页 1财富值 高代第七章自测题答案 暂无评价 3页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请...


第9章自测卷答案

第9章自测卷答案_数学_初中教育_教育专区。第 8 章 查找 自测卷答案 一、填空题(每空 1 分,共 10 分) 1. 在数据的存放无规律而言的线性表中进行检索的...


第9章自测卷答案

第8 章 查找 自测卷答案 一、填空题(每空 1 分,共 10 分) 填空题( 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找(线性查找) 。 ...


解决问题的正确答案测试题答案

解决问题的正确答案测试题答案_企业管理_经管营销_专业资料。课后测试如果您对课程...此种说法: √ 正确 错误 正确答案: 正确 14. 很多时候, 员工之所以借口,...


第一单元自测卷答案

第一单元自测卷答案_语文_小学教育_教育专区。小学语文六年级下册第一单元自测试卷...3.“秉”按音序查字法应查大写字母 B ,再查音节 bǐng ;按 部首查字法...


测试题库(通过查找功能找到答案!)

Intel? Teach Elements Assessment in 21st Century Classrooms 《21 世纪课堂评价》结业测试题题库及 使用方法(第 3 页开始为题库)使用方法:通过查找功能找到答案!...


第7章自测练习题参考答案

第7 章自测练习题参考答案 1.有一个有序文件,其中各记录的关键字为: {3,4,5,6,7,8,10,17,19,20,27,32,43,54,65,76,87}, 当用折半查找算法查找...


SQLA摸底测试题答案

SQLA摸底测试题答案_英语_高中教育_教育专区。说明:选择题每题 2 分,共 60 ...d)exists 是关于存在性的查询。 9)关于表联接与子查询的关系,说法错误的是(d...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com