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

1、习题八查找一、单项选择题1顺序查找法适合于存储结构为（）的线性表。A散列存储顺序存储或链式存储压缩存储索引存储若查找每个记录的概率均等，则在具有个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度为。3适用于折半查找的表的存储方式及元素排列要求为（）.链接方式存储，元素无序.链接方式存储，元素有序.顺序方式存储，元素无序.顺序方式存储，元素有序4当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）A必定快不一定在大部分情况下要快取决于表递增还是递减5当采用分块查找时，数据的组织方式为（）A数据分成若干块，每块内数据有序B数据分成若干块

2、，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块大.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块数据分成若干块，每块（除最后一块外）中数据个数需相同6二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。A正确错误二叉查找树的查找效率与二叉树的（1）高度结点的多少结点太多完全二叉树有关）,在（2）树型大.呈单大枝.树8如果要求一个线性表既能较快的查找，又能适应动态变化的要求法。分快查找顺序查找折半查找9分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是A（10，08，09，06，01

3、，2101，013）大（.10，06，08，09，01，2101，013）顺序查找时其）查找效率最低。结点的位置结点太复杂。则可采用查找基于属性.，09），散列地址为的链中有，用链）个A与处理冲突方法有关而与表的长度无关B与处理冲突方法无关而与表的长度有关大与处理冲突方法有关且与表的长度有关的与处理冲突方法无关且与表的长度无关12.设有一组记录的关键字为1，914，23，1，地址法构造散列表，散列函数为（）记录。13.关于杂凑查找说法不正确的有几个（）（1）采用链地址法解决冲突时，查找一个元素的时间是相同的（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的（3）

4、用链地址法解决冲突易引起聚集现象（4）再哈希法不易产生聚集设哈希表长为，哈希函数是表中已有数据的关键字为5,84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是15将.10个元素散列到1000个0单0元的哈希表中,则（）产生冲突。一定会一定不会仍可能会二、填空题顺序查找个元素的顺序表，若查找成功，则比较关键字的次数最多为次；当使用监视哨时，若查找失败，则比较关键字的次数为。在顺序表（）中，用二分（折半）法查找关键码值0需做的关键码比较次数为，一个无序序列可以通过构造一棵树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。哈希表是通过将查找码按选定

5、的和，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是和。一个好的TOC o 1-5 h z哈希函数其转换地址应尽可能，而且函数运算应尽可能。平衡二叉树又称，其定义是。在哈希函数（）中，值最好取。7假定有个关键字互为同义词，若用线性探测再散列法把这个关键字存入散列表中，至少要进行次探测。法构造的哈希函数肯定不会发生冲突。动态查找表和静态查找表的重要区别在于前者包含有和运算，而后者不包含这两种运算。o在散列存储中，装填因子a的值越大，则.；a的值越小，贝y。已知元整型数组存放个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于分的学生人数，请填空使之完善。学生人数函数返回大于等于分的学生人数第九章查找、单项选择题、填空题3二叉排序_哈希函数解决冲突的方法选择好的哈希函数处理冲突的方法均匀简单树（高度平衡树，高度平衡的二叉排序树）或为空二叉树，或二叉树中任意结点左子树高度与右