《数据结构课后习题第九章.doc》由会员分享，可在线阅读，更多相关《数据结构课后习题第九章.doc（5页珍藏版）》请在三一文库上搜索。
1、一选择题1. 对线性表进行二分查找时，要求线性表必须() 。A. 以顺序方式存储B.以顺序方式存储，且结点按关键字值有序排列C. 以链接方式存储D.以连接方式存储，且结点按关键字值有序排列2. 用二分查找法查找具有 n 个结点的线性表时，查找每个元素的平均比较次数是 ()。AO( ) B.O(n* ) C.O(n) D.O( )3. 利用逐个插入结点的方法建立序列 (50,72,43,85,75,20,35,45,65,30) 对应的 二叉树排序以后，查找元素 35 时，需要进行()次元素比较。A4B.5 C.7 D.104. 设哈希表的长度为m=14,哈希函数H(key)=key MODI,
2、表中已有4个结点，其 地址分别是： addr(15)=4 ；addr(38)=5;addr(61)=6;addr(84)=7; 其余地址空。 如果采用二次探测再散列处理冲突，则关键字 49 的结点的地址是()。A8 B.3 C.5 D.95. 一颗深度为 k 的平衡二叉树，其每个非终端结点的平衡因子均为 0，则该平衡 二叉树共有()个结点。A. -1 B.1 C. -1 D. .+16. 有一个长度为 12 的有序表，按二分查找法对表进行查找，在表内各元素查找 概率相等的情况下，查找成功所需的平均比较次数为() 。A.35/12 B.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,则应作()型调整 以使其平衡。ALL B.LR C.RL D.RR11. 设有一组记录的关键字为 19,14,23,1,68
4、,20,84,27,55,11,10,79 ，用链地 址法构造散列表，散列函数为 H(key)=key MOD 13, 散列地址为 1 的链中有 () 个 记录。A.1B.2C.3D.412. 假定有 k 个关键字互为同义词，若用线性探测法把这 k 个关键字存入散列表 中，至少要进行()次探测。A.k-1 B.k C.k+1D.k(k+1)/213. 散列函数有一个共同的性质，即函数值应当以()取其值域的每个值。A. 同等概率 B. 最小概率 C. 最大概率 D. 平均概率14. 散列表的地址区间为 017，散列函数为 H(k)=K mod 17 。采用线性探测法处 理冲突，并将关键字序列 2
5、6,25,72,38,8,18,59 依次存储到散列表中。(1) 元素 59 存放在散列表中的地址是() 。A.8B.9C.10D.11存放元素59需要搜索的次数是（）。A.2B.3C.4D.515. 下面关于B-和B+树的叙述中，不正确的是（）。A. B-树和B+树都是平衡的多叉树B. B-树和B+树都可用于文件的索引结构C. B-树和B+树都能有效地支持顺序检索D. B-树和B+树都能有效地支持随机检索16. 二叉查找树的查找效率与二叉树的（1）有关，在（2）时其查找效率最 低。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.m叉排序树B.m叉平衡排序树C.m1叉平衡排序树D.m+1叉平衡排序树2 1 .在一棵含有n个关键字的m阶B树中进行查找，至多读盘（）次。A.B.1+C.1+一 D. 1+二.填空题1. 已知一个有序表为1,8,12,25,29,32,40,62,98,当二分查找值为29和98的元素时，分别需要（）次和（）次比较才能查找成功；若采用顺序查找时，分别 需要（）次和（）次比较才能查找成功。2. 采用散列（Hash）技术进行查找，需要解决的两个问题是（）和（）。3. 在各种查找方法中，平均查找长度与结点个数n无关的是（）。4. 对于长度为225的表，采用分
8、块查找，每块的最佳长度是（）。对哈希表查找， 若用链表处理冲突，则平均查找长度是（）。5. 在分块查找中，对256个元素组成的线性表分成（）块最好，每块最佳长度是 （）。若每块的长度是8,则平均查找长度是（）。6. 在n个记录的有序顺序表中进行折半查找，最大比较次数是（）。7. 假设有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表 中，至少需要进行（）次探测。8. 设有一个长度为10的已排好序的表，用二分查找法进行查找，若查找不成功，至少与关键字比较（）次。9. 高度为8的平衡二叉树的结点输至少有（）个。10. 动态查找表和静态查找表的重要区别在于前者包含（）和（）运算，而后者
9、不包含这两种运算。11. 查找法基本上分成（）查找，（）查找，（）查找3类。处理哈希表冲突的方 法有（），（），（），（）4种。12. 以下是有序变的二分查找的递归算法，在画线处填入适当成分将算法补充完 整。Int Binsch（ElemTye A,int low,int high,KeyType K）ifint mid=（low+high）/2;If（）return mid;/查找成功，返回元素的下标else if （K<Amid.key）return Bin sch（A,low,mid-1,K）;在左子表上继续查找else return;/在右子表上继续查找else;/查找失败，返回
10、-1三计算机与算法设计题1. 画出长度为10的有序线性表进行折半查找的判定树，并求其在等概率时查 找成功的平均查找长度。2. 计算下图所示二叉树在等概率条件下，查找成功和失败时的平均查找长度。成功=（3. 用序列（46, ,8,45,39,70,58,101,10,66,34）建立一棵二叉排序树，画出此树，并求在等概率情况下查找成功时的平均查找长度。4. 给定的一组关键字K=4,5,2,3,6,1，试按二叉排序树生成规则画出这课二叉 排列树，并说明用这组关键字以不同的次序输入后建立起来的二叉排序树的形态 是否相同？当以中序遍历这些二叉排序树时，其遍历结果是否相同？为什么？5. 设有二叉排序树如
11、上图所示，画出依次插入8,3后的情形。6. 设上题（5题插入前的）所示的二叉排序树，画出依次删除5,6后的情形。7. 构造以4,5,721,3,6为关键字的平衡二叉树，并注明用了何种旋转（写出步骤）。8. 设有3阶B一树（如下图所示），画出依次插入18,33,97后的B一树。9. 在上题的B一树上(如上图所示)，分别画出删除66,16,43后的B 一树(从上 图出发)。10. 设散列表的地址范围是【0.9】，散列函数为H(key)=(+2)MOD9并采用链表处理冲突，请画出元素 7、4、5、3、6、2、8 9依次插入散列表的存储 结构。11. 已知待散列的线性表为(36,15,40,63,22
12、 )，散列用的一维地址空间为【0.6】 假定选定的散列函数是H(K)=K mod7,若发生冲突采用线性探查法处理，要求：(1)计算出每一个元素的散列地址并在下图中填写出散列表。0123456(2)求出在查找每一个元素的概率相等情况下的平均查找长度。12. 有字集合 K=15,22,50,13,20,36,28,48,31,41,18，散列表地址空间为 HT【0.15】 散列函数H(K)=K MOD 13采用二次探测再散列的开放地址法解决冲突，试将K值填入HT中，并把查找每个关键字所需的比较次数m填入下表中，然后计算出查找成功时的平均查找长度。I01234567891011121314KM13.
13、 将关键字序列7,8,30,11,18,9,14 散列存储到散列表中。散列表的存储空间 是一个下标从0开始的一维数组。散列函数是：H( key)=(key*3)MOD T,处理冲 突采用线性探测再散列法，要求装填因子为 0.7，问题：(1) 请画出构造的散列表。(2) 分别计算在等概率情况下，查找成功和查找不成功的平均查找长度。14. 设哈希函数 H(k)=3K mod 11,散列地址空间为 010,对关键字序列(32,13,49,24,38,21,4,12)按下述两种解决冲突的方法构造哈希表并分别求出等概率下查找成功时和失败时的平均查找长度ASLsucc和ASLunsucc。(1)线性探测再
14、散列(2)链地址法15. 编写在以BT为树根指针的二叉排序树上进行查找值为Key的结点的非递归算法。BiTree search(BiTree BT,keytype Key)16. 已知长度为 11 的表(xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon),按表中元素顺序依次插入一棵初始为空的平衡二叉树，画出插入完成后的平衡二叉树， 并求其在等概率的情况下查找成功的平均查找长度。17. 写出从哈希表中删除关键字为 K的一个记录的算法，设哈希函数为H,解决冲突的方法为链地址法。18. 设二叉排序树中结点的结构由下述 3 个域构造：数据域 data ，左孩子结点地 址 left ，右孩子结点地址 right 。设 data 域为正整数，该二叉树的根结点地址 为T。现给出一个正整数X。请编写非递归程序，实现将data域的值小于等于x 的结点全部删除掉。5