第7章参考答案08.doc

练习及参考答案一 选择题： 12345678910BCCCDBCDDD1112131415CDBDB1静态查找表与动态查找表的根本区别在于（B）A.它们的逻辑结构不一样 B.施加在其上的操作不一样C.所包含的数据元素类型不一样 D.存储实现不一样2在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（C）。A. n B. l C. n+1 D. n-13.顺序查找适用于存储结构为（C）的线性表。A.散列存储 B.压缩存储C.顺序存储或链式存储 D.索引存储4.用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（C)。A. O(log2n2） B. O(nlog2n) C. O(n) D. O( log2n）5.适用于折半查找的表的存储方式及元素排列要求为（D）。A.链接方式存储，元素无序 B.链接方式存储，元素有序C.顺序方式存储，元素无序 D.顺序方式存储，元素有序6.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（B）。A. 35/12 B. 37/12 C. 39/12 D. 43/127.在有序表1，3，9，12，32，41，62，75，77，82，95，100上进行折半查找关键字为82的数据元素需要比较（C）次。A. 1 B. 2 C. 4 D. 58.设散列表长为14，散列函数为H(key)=key% 11。当前表中已有4个结点：addr(15 )=4，addr(38) = 5，addr(61)=6，addr(84)=7。如用二次探测再散列处理冲突，则关键字为49的结点的地址是（D）。A. 8 B. 3 C. 5 D. 199.散列函数有一个共同的性质，即函数值应当以（D）取其值域的每个值。A.最大概率 B.最小概率 C.平均概率 D.同等概率10.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少（D）次探测？ A. k-1次 B. k次 C. k1次 D. k（k+l）/2次11. 取在散列函数H(k)k% m中，一般来讲，m应取（C)。A.奇数 B.偶数 C.素数 D.充分大的数12.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值（D)A.一定是同义词 B.一定不是同义词C.都相同 D.不一定都是同义词13.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（B）个结点最佳。A. 10 B. 25 C. 6 D. 62514.下列关于m阶B树的说法错误的是（D）。A.根结点至多有m棵子树B.所有叶子都在同一层次上C.非叶结点至少有m/2 ( m为偶数）或功i/2 +1 (m为奇数）棵子树D.根结点中的数据是有序的15. m阶B树是一棵（B）。A. m叉排序树 B. m叉平衡排序树C. m一1叉平衡排序树 D. m1叉平衡排序树二、判断题12345678910111213141516171819201.顺序查找可以在顺序表上进行，不能在单链表上进行。（）2.折半查找只能在有序的顺序表上进行。（）3.对于给定的关键字集合，以不同的次序插人到初始为空的二叉排序树中，得到的二叉排序树是相同的。（）4.若二叉排序树中关键字互不相同；那么，最小值结点必定无左孩子，最大值结点必定无右孩子。（）5.在二叉排序树中，最大值结点和最小值结点一定是叶子结点。（）6.将二叉排序树T的先序遍历序列依次插人初始为空的树中，所得到的二叉排序树T2和T；的形态完全相同。（）7.对二叉排序树进行中序遍历得到的序列是由小到大有序的。（）8.二叉树为二叉排序树的充分必要条件是任一非终端结点的值大于其左孩子的值、小于右孩子的值。（）9.二叉排序树的查找和折半查找的时间复杂度都是0(log2n)，时间性能相同。（）10.采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（）11.采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的在位置置为空，因为这将会影响以后的查找。（）12. m阶B树每一个结点的子树个数都小于或等于m。（）13.散列表的查找效率主要取决于构造散列表时选取的散列函数和处理冲突的方法。（）14.散列法存储的基本思想是由关键码的值决定数据的存储地址。（）15.当负载因子小于1时，则向散列表中插人元素时不会引起冲突。（）16.查找表中数据元素的任何数据项都可以作为关键字。（x）17. m阶B树的任何一个结点的所有子树的高度都相等。（）18.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（x）19.在散列存储方式中，负载因子的值越大，存取元素时发生冲突的可能性就越大。（）20.对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的（）。三问答题 1.画出长度为18的顺序查存储的有序表进行折半查找的判定树，并指出在等概率时，查找成功的平均查找长度，以及查找失败时所需最多的关键字比较次数。【解答】（1）判定树如下图所示（2）平均查找长度： (1+22+34+48+53) /18=32/92.已知如下所示长度为12的关键字有序的表：Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec(1)试按表中的顺序依次插入到一棵空的二叉排序树中，画出插入完成后的二叉排序树，并求其在等概率下查占成功的平均查找成度。（2）若对表中元素先进行排序构成有序表，求其在等概率下查找成功的平均查找成度。（3）按表中元素的顺序构造一棵平衡二叉排序树，求其在等概率下查占成功的平均查找成度。这种情况就退化成为顺序查找。【解答】 （1）二叉排序树如图所示。 （2）ASL= (11+22+33+43+52+61) /12=3.5（3）若先排序再构造二叉排序树，则构造是的一棵单枝树；ASL= (11+21+31+41+.+121) /12=6.53.试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。令Fk表示含有最少结点的深度为k的平衡二叉树的结点数目。那么，可知道F1=1，F2=2，FnFn-2Fn-11。含有12个结点的平衡二叉树的最大深度为5，如图7-10所示。4.含有9个叶子结点的3阶B树中至少有多少个非叶子结点？含有10个叶子结点的3阶B树中至少有多少个非叶子结点？【解答】4个，7个。5.试从空树开始，画出按以下次序向3阶B树中插人关键码的建树过程：20,30,50,52,60,68,70。如果此后删除50和68，画出每一步执行、：2后3阶B树的状态。图7-11【解答建树过程如图7-11所示。6.在地址空间为016的散列区中，对以下关键字序列构造两个散列表： Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec（l)用线性探测开放定址法处理冲突； （2）用链地址法处理冲突。并分别求这两个散列表在等概率情况下查找成功和不成功的平均查找长度。设散列函数为H(key)=i/2，其中i为关键字中第一个字母在字母表中的序号。【解答】（1)结果如图7-12所示。012345678910111213141516AprAugDecFeb JanMacMayJuneJulySepOctNw图7-12平均查找长度为31/12。（2）结果如图7-13所示。平均查找长度为3/2。7.设散列函数H(key)=(3key)%11，用开放地址法处理冲突，探测序列为di=i(7key)%10+1),i=1,2,3, 。试在010的散列地址空间扎对关键字序列(22,41,53,46,30,13,01,67)构造散列表，并求等概率情况下查找成功时的平均查找长度。01234567891022674130 5346 13 01 ASL=17/88.画出依次插入z,v,o,q,w,y到图7-15所示的5阶B树的过程四算法设计题1.将监视哨设在高下标端，改写书中给出的顺序查找算法，并分别求出在等概率情况下查找成功时和查找失败的平均查找长度。typedef struct datatype *data; int length; SSTableint search(SSTable st,keytype kx)int i; st.datast.length+1=kx; i=1; while(kx!=st.datai)i+; return(i);2将折半查找的算法改写为递归算法。【提示】对于每次查找的思想是相同的，只是查找区间发生了变化，因此折折半查找算法改写为递归算法时要将查找区间的上下限作为参数，递归调甩时查找区间的上下限是变化的。int BinSearch(datatype R，int low, int hig, keytype K)int mid; if (low hig) retum(0); else mid =(lowhig)/2； if(K=Rmid.key)return(mid); else if(KRmid.key)return(Bitiseareh(R,mid+1,hig,K)； else return(Binsrch(R,low,mid-1); 3.编写算法，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性。【提示】先在有序表R中利用折半查找法查找关键字值小于或等于x的结点，mid指向关键字正好等于x的结点或low指向关键字正好大于x的结点，然后采用移动法插入x结点即可。void Binlnsert(datatype R，KeyType x) int low =1,hign,mid,inplace,i,find0; while(lowRmid.key) lowmid+1； else i = mid; find=1； if(find)inspace=mid; else inspacelow; for(i=n;i =inspace；i-)Ri+l=Ri; Rinspac=x;4.假设二叉排序树T的各个元素值均不相同，设计一个算法按递减次序打印各元素的值。【提示】调整中序递归遍历算法，先遍历右子树，然后输出根结点的值，再遗历左子树。viod PrintNode(BiSTree T) if(T) PrintNode(T-rchild); printf（T-data）； PrintNode(T-lchild);5.已知一棵二叉排序树上所有关键字中的最小值为-max，最大值为max，又知-maxxmax。编写递归算法，求该二叉排序树上的小于x且最靠近x的值a和大于x且最靠近x的值b。【提示】解决本题的关键是递归函数的参数设置，采用逐渐缩小查找区间的方法来实现。void fun(BiSTree T,int x,int *a,int *b) if(T) if(xdata. key) /*当x小于根结点时，修改b,在左子树上继续查找*/ *b=T-data. key; fun(T=lchild, x,a,b); else if（xT-data) /*当x大于根结点时，修改a,在右子树上继续查找*/ *a=T-data.key; fun(T=rchild, x,a,b); else /*当x等于根结点时，a是其左子树的最右下结点，b是其右子树的最左下结点* if(T-lchild) p=T-lchild; while(p- rchilt) p = p - rchiid; *a = p - data.key; if(T-rchild） PT-rchild； while(P-lchild）PP-lchild； *b=p-data.key; 6.在平衡二叉排序树的每个结点中增设一个lsize域，其值为它的左子树中的结点数加1。试写时间复杂度为O(log2n)的算法，确定树中第k小的结点的位置。【提示】由二叉排序树的性质和lsize域的定义可知，第k小的结点即lsize域的值为k的结点。因此，可以采用递归算法在二叉排序树中查找这样的结点。typedef struct BiTNode datatype data； int lsize； struct BiTNode *lehild，*rchild； BiTNode，*BiTree；*增设lsize 域的二叉树的类型定义*Biffree Index(BiTree T, int k) if(T=NULL) return(NULL)；*若根结点t为空则查找失败* if(T-lsize=k) return（T）；*找到第k小结点，返回其地址* else if(T-lsize k) Index(T-lchild;k)；*若k小于根结点，在左子树继续查找*/ else Index(T-rchild;k)；/*若k大于根结点，在右子树继续查找* 7.假设一棵平衡二叉树的每个结点都标明了平衡因子bf，设计算法求平衡二叉树的高度。提示因为二叉树各结点已标明了平衡因子bf，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子bf为0时，任选左右一分支向下查找，若bf不为0，则沿左（当bf=1时）或右（当bf=-1时）向下查找。typedef struct bsnode datatyte data；struct bsnode *lchild,*rchild；int bf; *结点的平衡因子*BBiST Node，BBiSTree；*带平衡因子域的平衡二叉树的类型定义*int Height(BBiSTree T) *求平衡二叉树T的高度*int level0；BBiSTree p=T;while(p)level+； *树的高度增1if(p-bfrehild； *bf-1，沿右分支向下*else p=p-lchild; /*hf =0，沿左分支向下* return（level）；8.设计在有序顺序表上进行斐波那契查找的算法，并画出长度为20的有序表进行斐波那契查找的判定树，求出在等概率下查找成功的平均查找长度。【提示】采用类似折半查找的算法，按照斐波那契数列分割查找表，实现查找。int Fibo_Search(SSTable L，keytype x，int fibo)/*向量fibo中为斐波那契分割序列*/int low1； int high=L.length； /*设L.length=fiboK-1*/ while(low L. elemRmid)lowmid + 1； else return(mid)； retum(0)；9.试编写一个判定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构，且树中结点的关键字均不同。【提示】 判断一棵二叉树是二叉排序树，可以采用递归算法。对于树中所有结点，检查其左子树上所有结点的关键字是否都小于它的关键字，检查其右子树上所有结点的关键字是否都大于它的关键字。int BinsortTree(BisTree T)/*判别由二叉链表