全国自考数据结构导论（查找）模拟试卷1

全国自考数据结构导论(查找)模拟试

卷1

一、单项选择题(本题共70题，每题7.0分，共70

分。)

1、对有n个数据元索的顺序表做顺序查找时，若查找每个元素的概率相同，则平

均查找长度为3

A^(n-1)/2

B、n/2

C、(n+l)/2

D、n

标准答案：C

知识点解析：暂无解析

2、对长度为4的顺序表进行查找，若查找笫一个元素的概率为1/24,笫二个元

素的概率为I/6,第三个元素的概率为2/3,第四个元素的概率为1/8,则查找

任一个元素的平均查找长度为o

A、23/8

B、20/8

C、17/8

D、14/8

标准答案：A

知识点解析：暂无解析

3、下面有关折半查找的叙述中，正确的是o

A、数据元素必须有序排列，可以采用顺序存储，也可以采用链式存储

B、数据元素必须有序排列，且必须采用顺序存储

C、数据元素必须有序排列，而且只能从大到小排列

D、数据元素可以有序排列，也可以无序排列

标准答案：B

知识点解析：暂无解析

4、对有14个数据元素的有序表a[14]进行折半查找，搜索到a[5]的关键字等于给

定值，此时元素比较顺序依次为。

A、a网,a[5J,a[6],a[7J

B、a[l],a[8],a[7],a[6]

C、a[6],a[4J,a[8]>a|5]

D、a[6],a[2],a[4],a[5]

标准答案：D

知识点解析：暂无解析

5、有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概

率情况下查找成功时所需平均比较次数为o

A、35/12

B、37/12

C、39/12

D、十二月-43

标准答案：B

知识点解析：由题目已知元素序号（即下标）范围为1〜12,查找1次成功的结点

为：6。查找2次成功的结点为：3,9。查找3次成功的结点为：1,4,7,II。

查找4次成功的结点为：2,5,8,10,12。成功查找所有结点的总的比较次数

为:1x1+2x2+3x4+4x5=37平均比较次数为37/12。因此选择B。

6、当采用分块查找时，数据的组织方式为o

A、数据必须有序

B、数据不必有序

C、数据分成若干块，每块为数据不必有序，但块问必须有序

D、数据分成若干块，每块内数据必须有序，但块间不必有序

标准答案：C

知识点解析：暂无解析

7、下面关于哈希表的说法中，正确的是。

A、不管采用何种处理冲突方法，都可直接删除元素

B、哈希表不需比较关键字即可查找到元素

C、哈希函数构造的越复杂，冲突就越小

D、哈希函数在关键字与哈希地址之间建立映像

标准答案：D

知识点解析：暂无解析

8、哈希表的地址区间为。〜17,哈希函数为h（key）=K9/617。采用线性探测法处

理冲突，并将关键字序列｛26,25,72,38,8,18,59）依次存储到哈希表中,则

存放元素59需要搜索的次数是。

A、5

B、4

C、3

D、2

标准答案：B

知识点解析：暂无解析

9、设有一组关键字为｛19,15,23,2,68,20,84,28,55,II,10,80）,用链

地址法构造哈希表，哈希函数为1!（1^丫）=1^丫％13,则哈希地址为2的链表中有

个记录。

A、1

B、2

C、3

D、4

标准答案：D

知识点解析：暂无解析

10、将10个数据元素存放到有100000个单元的哈希表中，则产生冲

突。

A、一定不会

B、一定会

C、可能会

D、无法判断

标准答案：C

知识点解析：暂无解析

二、填空题（本题共9题，每题1.0分，共9分。）

11、顺序查找在杳找成功情况下的平均查找长度为；在查找失败情况下的

平均查找长度为O

标准答案：（n+l）/2n+l

知识点解析：暂无解析

12、折半查找只能使用存储结构。

标准答案：顺序

知识点解析：暂无解析

13、已知一个有序表为｛10,23,35,46,48,55,59,64,72,83,88,99）,当

用折半查找方法查找值为46和83的元素时，分别需要比较次和次

才能查找成功；若采用顺序查找时，分别需要比较次和次才能查找成

功。

标准答案：34410

知识点解析：暂无解析

14、索引顺序表上的查找分两个阶段，它们是和

标准答案：确定待杳元素所在的块在块内宣战待查的元素

知识点解析：暂无解析

15、在分块检索中，若索引表和各块内均采用顺序查找，则900个元素的线性表分

成块最好；若分成25块，其平均查找长度为o

标准答案:3031.5

知识点解析：对n个元素的线性表采用分块检索时;分介，成块最好，在这个问题

中具体分成/丽=30最好：若分成25块，则每块有900/25=36个元素，确定元

素所在块，平均需查找(25+1)/2=13次，确定元素在块内的位置平均需杳找(36+1)

/2=18.5次，合计平均需查找31.5次。

16、在分块查找法中，首先查找,然后再查找相应的o

标准答案：索引表块

知识点解析：暂无解析

17、哈希函数的构造方法主要有、、、和。

标准答案：直接定址法除留余数法数字分析法平方取中法折叠移位法

知识点解析；暂无解析

18、在哈希函数h(key)=key%m中，m值最好取。

标准答案：小于等于表长的素数

知识点解析：暂无解析

19、常用的处理冲突的方法有：和o

标准答案：开放定址法链地址法

知识点解析：暂无解析

三、应用题(本题共8题，每题7.0分，共8分。)

20、顺序查找时间为O(n),折半查找时间为O(k)g2n),哈希法为0(1),为什么有

高效率的查找方法而低效率的方法不被放弃？

标准答案：不同的查找方法适用的范围不同，高效率的查找方法并不是在所有情况

下都比其他查找方法效率要高，而且也不是在所有情况下都可以采用。

知识点解析：暂无解析

21、为什么有序的单链表不能进行折半查找?

标准答案：因为链表无法进行随机访问，若要访问链表中的结点，必须从头指针开

始依次遍历链表，从而浪费大量时间。另外，也不好设定查找结束的条件。

知识点解析：暂无解析

22、已知一个有7个数据元素的有序顺序表，其关键字为｛3,18,25,37,69,

87,99)。请给出用折半查找方法查找关键字值18的查找过程。

我找关键字key=18

3182537698799

第一•步ttt

lowmillupper

3182537698799

第二步ttt

标准答案：midupper

知识点解析：暂无解析

23、已知一组关键字为｛5,88,12,56,71,28,33,43,93,17｝,哈希表长为

13,哈希函数为11(1(6丫)=1<0丫％13,请用线性探杳法和平方探查法解决冲突构造这组

关键字的哈希表，并计算查找成功时的平均查找长度。

标准答案：线性探查法：

哈希地址0123456789101112

关键字2893565713343178812

比较次数1211115611

平均杳找长度：ASL成功=(1X7+2+5+6)/10=2平方探查法:

哈希地址0123456789101112

关・字9328435657133178812

7匕丽:数一

3131111411

平均查找长度：ASL成功=(lx7+4+3x2)/10=1.7

知识点解析：暂无解析

24>已知一组关键字为｛5,88,12,56,71,28,33,43,93,17｝,采用链地址法

构造哈希表，并计算查找成功时的平均查找长度。

0

标准答案：

知识点解析：暂无解析

25、已知关键字序列［20,8,35,127,9,82,98,15,45,174,72},哈希表长

为13,哈希函数为11(1<6丫尸1^丫％13,试分别给出采用线性探查法和平方探查法处

理冲突时的哈希表，并计算查找成功时的平均查找长度。

标准答案：线性探查法：

哈希地址0123456789101112

关键字7215821744520835127998

比较次数71111111136

平均查找长度：ASL成功=(lx8+3+7+6)/11=24/11平方探查法:

哈希地址0123456789101112

关键字9174158245982083512772

比较次数45113311114

平均查找长度：ASL=(1x6+54-3x2+4x2)/11=25/11

知识点解析：暂无解析

26、试写出二分查找的递归算法。

标准答案：intbinlist(datatypea［n］；intS,t：dataTypex)/*n为元素个数,s,t分

别为查找区间的上、下界*/{if(s>l)reiurn(0);/*查找失败*/else{mid=(S++)/

2；switch(mid)of(X［mid］：rcturn(binlist(a,mid+1,t,x));/*在高端区间上递归*

/})}

知识点解析：在待查区间的上、下界处设两个指针，由此计算出中间元素的序号，

当中间元素大于给定值X时，接下来到其低端区间去查找；当中间元素小于给定

值X时，接下来到其高端区间去查找；当中间元素等于给定值X时，表示查找成

功