数据结构第八章习题及答案.docx

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

1、习题八 查找一, 单项选择题1依次查找法适合于存储结构为（ ）的线性表。A 散列存储 B. 依次存储或链式存储 C. 压缩存储 D. 索引存储2.若查找每个记录的概率均等，则在具有n个记录的连续依次文件中采纳依次查找法查找一个记录，其平均查找长度ASL为( )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n3适用于折半查找的表的存储方式及元素排列要求为( ) A链接方式存储，元素无序 B链接方式存储，元素有序C依次方式存储，元素无序 D依次方式存储，元素有序4当在一个有序的依次存储表上查找一个数据时，即可用折半查找，也可用依次查找，但前者比后者的查找速度( ) A必定快 B

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

3、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的链中有（ ）个记录。A1 B. 2 C. 3 D. 413. 关于杂凑查找说法不正确的有几个( ) （1）采纳链地址法解决冲突时，查找一个元素的时间是相同的 （

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

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

7、%p中，p值最好取_。7假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行_次探测。8. _法构造的哈希函数确定不会发生冲突。9. 动态查找表与静态查找表的重要区分在于前者包含有_与_运算，而后者不包含这两种运算。10在散列存储中，装填因子的值越大，则_ _；的值越小，则_ _。11. 已知N元整型数组a存放N个学生的成果，已按由大到小排序，以下算法是用对分（折半）查找方法统计成果大于或等于X分的学生人数，请填空使之完善。 #define N /*学生人数*/int uprx(int aN,int x ) /*函数返回大于等于X分的学生人数*/ int head=1,mid,rear=N; do mid=(head+rear)/2;if(x=amid) _(1) _ else _(2)_ _;while(_(3)_ _);if (aheadrear第 5 页