资源描述：
《数据结构课后习题第九章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一．选择题1.对线性表进行二分查找时，要求线性表必须（）。A.以顺序方式存储B.以顺序方式存储，且结点按关键字值有序排列C.以链接方式存储D.以连接方式存储，且结点按关键字值有序排列2.用二分查找法查找具有n个结点的线性表时，查找每个元素的平均比较次数是（）。A．O（n2）B.O(n*log2n)C.O(n)D.O(log2n)3.利用逐个插入结点的方法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉树排序以后，查找元素35时，需要进行（）次元素比较。A．4B.5C.7D.104.设哈希表的长度为m=14,哈希函数H(key)=ke
2、yMOD11,表中已有4个结点，其地址分别是：addr(15)=4；addr(38)=5;addr(61)=6;addr(84)=7;其余地址空。如果采用二次探测再散列处理冲突，则关键字49的结点的地址是（）。A．8B.3C.5D.95.一颗深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该平衡二叉树共有（）个结点。A.2k-1-1B.2k-1+1C.2k-1D..2k+16.有一个长度为12的有序表，按二分查找法对表进行查找，在表内各元素查找概率相等的情况下，查找成功所需的平均比较次数为（）。A.35/12B.37/12C.39/12D.43/127.
3、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（）。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构8.具有5层结点的平衡二叉树至少有（）个结点。A.12B.11C.10D.99.既希望较快的查找又便于线性表动态变化的查找方法是（）。A.顺序查找B.折半查找C.索引顺序查找D.哈希法查找10.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整以使其平衡。A．LLB.LRC.RLD.RR11.设有一组记录的关键字为{19,14,23,1,68,2
4、0,84,27,55,11,10,79}，用链地址法构造散列表，散列函数为H(key)=keyMOD13,散列地址为1的链中有()个记录。A.1B.2C.3D.412.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行（）次探测。A.k-1B.kC.k+1D.k(k+1)/213.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A.同等概率B.最小概率C.最大概率D.平均概率14.散列表的地址区间为0~17，散列函数为H(k)=Kmod17。采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次
5、存储到散列表中。(1)元素59存放在散列表中的地址是（）。A.8B.9C.10D.11(2)存放元素59需要搜索的次数是（）。A.2B.3C.4D.515.下面关于B-和B+树的叙述中，不正确的是（）。A.B-树和B+树都是平衡的多叉树B.B-树和B+树都可用于文件的索引结构C．B-树和B+树都能有效地支持顺序检索D．B-树和B+树都能有效地支持随机检索16.二叉查找树的查找效率与二叉树的（（1））有关，在（（2））时其查找效率最低。(1)A.高度B.结点的多少C.树形D.结点的位置(2)A.结点太多B.完全二叉树C.呈单支树D.结点太复杂17.当采用分块查找时，
6、数据的组织方式为（）。A.数据分成若干块，每块内数据有序B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C.数据分成若干块，每块内数据有序，每块内最大（或最小）的组成索引块D．数据分成若干块，每块（除最后一块外）中数据个数需相同18.已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半法查找一个不存在的元素，则比较的次数最多是（）。A.4B.5C.6D.719.下列叙述中，不符合m阶B-树定义要求的是（）。A.根结点最多有m棵子树B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D.叶结点之间通过指
7、针链接20.m阶B-树是一棵（）A．ｍ叉排序树 Ｂ．ｍ叉平衡排序树Ｃ．ｍ－１叉平衡排序树 Ｄ．ｍ＋１叉平衡排序树２１．在一棵含有ｎ个关键字的ｍ阶Ｂ－树中进行查找，至多读盘（）次。A.log2nB.1+log2nC.1+log[m]2(n+12)D.1+log[n]2(m+12)二．填空题1.已知一个有序表为{1,8,12,25,29,32,40,62,98},当二分查找值为29和98的元素时，分别需要（）次和（）次比较才能查找成功；若采用顺序查找时，分别需要（）次和（）次比较才能查找成功。2.采用散列（Hash）技术进行查找，需要解决的两个问题是（）和
8、（）。3.
