1、全国自考数据结构导论（查找）模拟试卷 1 及答案与解析一、单项选择题1 对有 n 个数据元素的顺序表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为_。（A）(n 一 1)2（B） n2（C） (n+1)2（D）n2 对长度为 4 的顺序表进行查找，若查找第一个元素的概率为 124，第二个元素的概率为 16，第三个元素的概率为 23，第四个元素的概率为 18，则查找任一个元素的平均查找长度为_。（A）238（B） 208（C） 178（D）1483 下面有关折半查找的叙述中，正确的是_。（A）数据元素必须有序排列，可以采用顺序存储，也可以采用链式存储（B）数据元素必须有序排列，且必须采
2、用顺序存储（C）数据元素必须有序排列，而且只能从大到小排列（D）数据元素可以有序排列，也可以无序排列4 对有 14 个数据元素的有序表 a14进行折半查找，搜索到 a5的关键字等于给定值，此时元素比较顺序依次为_。（A）a8，a5，a6，a7（B） a1，a8，a7，a6（C） a6，a4，a8，a5（D）a6，a2，a4，a55 有一个长度为 12 的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功时所需平均比较次数为_。（A）3512（B） 3712（C） 3912（D）十二月-436 当采用分块查找时，数据的组织方式为_。（A）数据必须有序（B）数据不必有序（C）数据
3、分成若干块，每块内数据不必有序，但块问必须有序（D）数据分成若干块，每块内数据必须有序，但块间不必有序7 下面关于哈希表的说法中，正确的是_。（A）不管采用何种处理冲突方法，都可直接删除元素（B）哈希表不需比较关键字即可查找到元素（C）哈希函数构造的越复杂，冲突就越小（D）哈希函数在关键字与哈希地址之间建立映像8 哈希表的地址区间为 017，哈希函数为 h(key)=K9617。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59 依次存储到哈希表中，则存放元素 59 需要搜索的次数是_。（A）5（B） 4（C） 3（D）29 设有一组关键字为19， 15，23，2，6
4、8，20，84，28，55，11，10，80 ，用链地址法构造哈希表，哈希函数为 h(key)=key13，则哈希地址为 2 的链表中有_个记录。（A）1（B） 2（C） 3（D）410 将 10 个数据元素存放到有 100000 个单元的哈希表中，则_产生冲突。（A）一定不会（B）一定会（C）可能会（D）无法判断二、填空题11 顺序查找在查找成功情况下的平均查找长度为_；在查找失败情况下的平均查找长度为_。12 折半查找只能使用_存储结构。13 已知一个有序表为10，23，35，46，48，55，59，64，72，83，88，99 ，当用折半查找方法查找值为 46 和 83 的元素时，分别需
5、要比较_次和_次才能查找成功；若采用顺序查找时，分别需要比较_次和_次才能查找成功。14 索引顺序表上的查找分两个阶段，它们是_和_。15 在分块检索中，若索引表和各块内均采用顺序查找，则 900 个元素的线性表分成_块最好；若分成 25 块，其平均查找长度为_。16 在分块查找法中，首先查找_，然后再查找相应的_。17 哈希函数的构造方法主要有_、_、_、_和_。18 在哈希函数 h(key)=keym 中，m 值最好取_ 。19 常用的处理冲突的方法有：_和_。三、应用题20 顺序查找时间为 O(n)，折半查找时间为 O(log2n)，哈希法为 O(1)，为什么有高效率的查找方法而低效率的
6、方法不被放弃?21 为什么有序的单链表不能进行折半查找?22 已知一个有 7 个数据元素的有序顺序表，其关键字为3，18 ，25， 37，69，87 ，99)。请给出用折半查找方法查找关键字值 18 的查找过程。23 已知一组关键字为5， 88，12，56，7l，28，33，43，93，17，哈希表长为13，哈希函数为 h(key)=key13，请用线性探查法和平方探查法解决冲突构造这组关键字的哈希表，并计算查找成功时的平均查找长度。24 已知一组关键字为5， 88，12，56，7l，28，33，43，93，17,采用链地址法构造哈希表，并计算查找成功时的平均查找长度。25 已知关键字序列20
7、， 8，35，127，9，82，98，15，45，174，72 ，哈希表长为 13，哈希函数为 h(key)=key13，试分别给出采用线性探查法和平方探查法处理冲突时的哈希表，并计算查找成功时的平均查找长度。26 试写出二分查找的递归算法。27 写出从哈希法构造的散列表中删除关键字为 k 的一个记录的算法，设所有哈希函数为 H，解决冲突的方法是链地址法。全国自考数据结构导论（查找）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 C【知识模块】 查找2 【正确答案】 A【知识模块】 查找3 【正确答案】 B【知识模块】 查找4 【正确答案】 D【知识模块】 查找5 【正确答案】 B【试
8、题解析】 由题目已知元素序号(即下标)范围为 112。查找 1 次成功的结点为：6。查找 2 次成功的结点为：3，9。查找 3 次成功的结点为：1，4，7，11。查找 4 次成功的结点为：2，5，8，10，12。成功查找所有结点的总的比较次数为:11+22+34+45=37平均比较次数为 3712。因此选择 B。【知识模块】 查找6 【正确答案】 C【知识模块】 查找7 【正确答案】 D【知识模块】 查找8 【正确答案】 B【知识模块】 查找9 【正确答案】 D【知识模块】 查找10 【正确答案】 C【知识模块】 查找二、填空题11 【正确答案】 (n+1) 2 n+1【知识模块】 查找12
9、【正确答案】 顺序【知识模块】 查找13 【正确答案】 3 4 4 10【知识模块】 查找14 【正确答案】 确定待查元素所在的块在块内查找待查的元素【知识模块】 查找15 【正确答案】 30 315【试题解析】 对 n 个元素的线性表采用分块检索时，分 成块最好，在这个问题中具体分成 =30 最好；若分成 25 块，则每块有 90025=36 个元素，确定元素所在块，平均需查找(25+1)2=13 次，确定元素在块内的位置平均需查找(36+1)2=18 5 次，合计平均需查找 315 次。【知识模块】 查找16 【正确答案】 索引表 块【知识模块】 查找17 【正确答案】 直接定址法 除留余
10、数法 数字分析法 平方取中法 折叠移位法【知识模块】 查找18 【正确答案】 小于等于表长的素数【知识模块】 查找19 【正确答案】 开放定址法 链地址法【知识模块】 查找三、应用题20 【正确答案】 不同的查找方法适用的范围不同，高效率的查找方法并不是在所有情况下都比其他查找方法效率要高，而且也不是在所有情况下都可以采用。【知识模块】 查找21 【正确答案】 因为链表无法进行随机访问，若要访问链表中的结点，必须从头指针开始依次遍历链表，从而浪费大量时间。另外，也不好设定查找结束的条件。【知识模块】 查找22 【正确答案】 【知识模块】 查找23 【正确答案】 线性探查法：平均查找长度：ASL
11、 成功 =(17+2+5+6)10=2 平方探查法：平均查找长度：ASL 成功 =(17+4+32)10=17【知识模块】 查找24 【正确答案】 【知识模块】 查找25 【正确答案】 线性探查法：平均查找长度：ASL 成功 =(18+3+7+6)11=2411 平方探查法：平均查找长度：ASL=(16+5+32+42)11=25 11【知识模块】 查找26 【正确答案】 int binlist(datatype an；int S，t ；dataType x)*n 为元素个数，s，t 分别为查找区间的上、下界*if(st)return(0); *查找失败 *elsemid=(S+)2；swit
12、ch(mid)of(Xmid：return(binlist(a，mid+1，t，x); *在高端区间上递归*【试题解析】 在待查区间的上、下界处设两个指针，由此计算出中间元素的序号，当中间元素大于给定值 X 时，接下来到其低端区间去查找；当中间元素小于给定值 X 时，接下来到其高端区间去查找；当中间元素等于给定值 X 时，表示查找成功，输出其序号。【知识模块】 查找27 【正确答案】 void Delete(LinkList*HT ，ElemType key) *在哈希表 HT 中删除关键字 key*P=HTH(key);if(!p)print f(”表中无该元素n”) ；exit(0) ；if(p 一data=k) *表中的一个元素*HTH(key)=P-next,free(p);else while(p&p 一data!=k)q=p；P=P 一next；if(p) *查找成功*( q 一next=P 一next；free(p)；elseprintf(“表中无此元素n”) ； exit(0) ；【试题解析】 首先利用哈希函数关键字 k 的地址 d，并在第 d 个单链表中查找值为 k 的关键字，若查找成功，则删除该结点。算法描述如下。【知识模块】 查找
