最新数据结构第八章习题及答案.pdf

《最新数据结构第八章习题及答案.pdf》由会员分享，可在线阅读，更多相关《最新数据结构第八章习题及答案.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢1 习题八 查找 一、单项选择题 1顺序查找法适合于存储结构为（）的线性表。A 散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 2.若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度 ASL为()。A(n-1)/2 B.n/2 C.(n+1)/2 D.n 3适用于折半查找的表的存储方式及元素排列要求为()A 链接方式存储，元素无序 B 链接方式存储，元素有序 C顺序方式存储，元素无序 D 顺序方式存储，元素有序 4当在一个有序的顺序存储表上查找一个数据时，即

2、可用折半查找，也可用顺序查找，但前者比后者的查找速度()A 必定快 B.不一定 C.在大部分情况下要快 D.取决于表递增还是递减 5当采用分块查找时，数据的组织方式为()A 数据分成若干块，每块内数据有序 B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D.数据分成若干块，每块（除最后一块外）中数据个数需相同 6二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。A 正确 B.错误 7.二叉查找树的查找效率与二叉树的(（1）)有关

3、,在(（2）)时其查找效率最低。(1):A.高度 B.结点的多少 C.树型 D.结点的位置(2):A.结点太多 B.完全二叉树 C.呈单枝树 D.结点太复杂。8如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用()查找法。A.分快查找 B.顺序查找 C.折半查找 D.基于属性 9分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()。A（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)10下图所

4、示的 4 棵二叉树,()是平衡二叉树。（A）（B）（C）（D）11散列表的平均查找长度（）。A 与处理冲突方法有关而与表的长度无关 B 与处理冲突方法无关而与表的长度有关 C 与处理冲突方法有关且与表的长度有关 D 与处理冲突方法无关且与表的长度无关 12.设有一组记录的关键字为 19，14，23，1，68，20，84，27，55，11，10，79，用链地址法构造散列表，散列函数为 H（key）=key MOD 13,散列地址为 1 的链中有（）个精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢2 记录。A 1 B.2 C.3 D.4 13.关于杂凑查找说法不正确的有几个

5、()（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集 A.1 B.2 C.3 D.4 14.设哈希表长为 14，哈希函数是 H(key)=key%11,表中已有数据的关键字为 15，38，61，84 共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()A 8 B 3 C 5 D 9 15.将 10 个元素散列到 100000 个单元的哈希表中，则（）产生冲突。A.一定会 B.一定不会 C.仍可能会 二、

6、填空题 1.顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为 _ _ 次；当使用监视哨时，若查找失败，则比较关键字的次数为 _ _。2.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为 _.3 一个无序序列可以通过构造一棵 _ _ _ _ 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。4.哈希表是通过将查找码按选定的 _ _ 和 _ _，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是 _ _ 和 _ _。一个好的哈希函数其转换地址应尽可能 _ _，而且函数运算应

7、尽可能 _ _。5.平衡二叉树又称 _，其定义是 _ _。6.在哈希函数 H（key）=key%p中，p 值最好取 _。7假定有 k 个关键字互为同义词，若用线性探测再散列法把这 k 个关键字存入散列表中，至少要进行 _次探测。8._ 法构造的哈希函数肯定不会发生冲突。9.动态查找表和静态查找表的重要区别在于前者包含有 _和 _运算，而后者不包含这两种运算。10在散列存储中，装填因子的值越大，则 _ _；的值越小，则 _ _。11.已知 N元整型数组 a 存放 N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于 X分的学生人数，请填空使之完善。#define

8、N/*学生人数*/int uprx(int aN,int x)/*函数返回大于等于 X分的学生人数*/int head=1,mid,rear=N;do mid=(head+rear)/2;录其平均查找长度为适用于折半查找的表的存储方式及元素排列要求为链接方式存储元素无序链接方式存储元素有序 用顺序查找但前者比后者的查找速度必定快不一定在大部分情况下要快取决于表递增还递减当采用分块查找时数据的 小的数据组成索引块数据分成若干块每块内数据有序每块内最大或最小的数据组成索引块数据分成若干块每块除最后精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢3 if(x=amid)_(1)

9、_ else _(2)_ _;while(_(3)_ _);if(aheadrear 出师表 出师表 是三国时期蜀汉丞相诸葛亮在北伐中原之前给后主刘禅上书的表文，阐述了北伐的必要性以及对后主刘禅治国寄予的期望，言辞恳切，写出了诸葛亮的一片忠诚之心。历史上有前出师表和后出师表，通常所说的出师表一般指前出师表。原文 先帝创业未半而中道崩殂（c）。今天下三分，益州疲（p）弊，此诚危急录其平均查找长度为适用于折半查找的表的存储方式及元素排列要求为链接方式存储元素无序链接方式存储元素有序 用顺序查找但前者比后者的查找速度必定快不一定在大部分情况下要快取决于表递增还递减当采用分块查找时数据的 小的数据组成

10、索引块数据分成若干块每块内数据有序每块内最大或最小的数据组成索引块数据分成若干块每块除最后精品好文档，推荐学习交流 仅供学习与交流，如有侵权请联系网站删除 谢谢4 存亡之秋也。然侍 卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞（s）忠谏之路也。宫中府中，俱为一体；陟（zh）罚臧（zng）否（p），不宜异同；若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。侍中、侍郎郭攸（yu）之、费祎（y）、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗（w i）陛下。愚以为宫中之事，

11、事无大小，悉以咨之，然后施行，必能裨（b）补阙（qu）漏，有所广益。将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰能，是以众议举宠为督。愚以为营中之事，悉以咨之，必能使行（h ng）阵和睦，优劣得所。亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。侍中、尚书、长(zhng)史、参军，此悉贞良死节之臣，愿陛下亲之信之，则汉室之隆，可计日而待也。臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥（wi）自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有（y u）一年矣。录其平均查找长度为适用于折半查找的表的存储方式及元素排列要求为链接方式存储元素无序链接方式存储元素有序 用顺序查找但前者比后者的查找速度必定快不一定在大部分情况下要快取决于表递增还递减当采用分块查找时数据的 小的数据组成索引块数据分成若干块每块内数据有序每块内最大或最小的数据组成索引块数据分成若干块每块除最后