算法与数据结构（C++语言版）（第2版） 第10章课后习题答案

PAGEPAGE3习题答案一、选择1-5：BABDA6-10：BCCBC二、填空1、nn+12、1,3,6,8,11,13,16,193、2,4,34、(n+1)/25、m-1,「m/2-1三、判断1-5：错错错错对四、应用题1、若对长度均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试在下列三种情况下分别讨论二者在等概率情况下平均查找长度是否相同？（1）查找不成功，即表中没有和关键字K相等的记录；（2）查找成功，且表中只有一个和关键字K相等的记录；（3）查找成功，且表中有多个和关键字K相等的记录，要求计算有多少个和关键字K相等的记录。【解答】（1）平均查找长度不相同。在有序的顺序表中查找时，在n+1(1~n+1)个位置均可能失败；查找无序的顺序表时，查找失败都是在第n+1个位置，其平均查找长度是n+1。（2）平均查找长度相同。在n个位置上均可能成功。（3）平均查找长度不相同。前者在某个位置上(1<=i<=n)查找成功时，和关键字K相等的记录是连续的，而后者要查找完顺序表的全部记录。2、建立一棵具有13个结点的判定树，并求其成功和不成功的平均查找长度值各为多少。【解答】查找成功时的平均查找长度为：查找不成功时的平均查找长度为：3、假定对有序表：(3，4，5，7，24，30，42，54，63，72，87，95)进行折半查找，试回答下列问题：(1)画出描述折半查找过程的判定树；(2)若查找元素54，需依次与哪些元素比较?(3)若查找元素90，需依次与哪些元素比较?(4)假定每个元素的查找概率相等，求查找成功时的平均查找长度。【解答】4、已知长度为l2的表{Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec}（1）试按表中元素的次序依次插入一棵初始为空的二叉查找树，并求在等概率情况下查找成功的平均查找长度。（2）用表中元素构造一棵最佳二叉查找树，求在等概率的情况下查找成功的平均查找长度。（3）按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。【解答】(1)ASLsuss=(1*1+2*2+3*3+4*3+5*2+6*1)/12=42/12(2)ASLsuss=(1*1+2*2+4*3+5*4)/12=37/12(3)ASLsuss=(1*1+2*2+4*3+4*4+5*1)/12=38/125、设有一棵空的３阶B树，依次插入关键字30，20，10，40，80，58，47，50，29，22，56，98，99，请画出该树。【解答】五、算法设计1、[题目分析]根据二叉查找树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉查找树，则置flag为false。[算法9.12]voidJudgeBST（BSTreet，intflag）∥判断二叉树是否是二叉查找树，本算法结束后，在调用程序中由flag得出结论{if（t!=null&&flag）{judgebst(t->lchild)；∥中序遍历左子树if(pre==null)pre=t；∥中序遍历的第一个结点不必判断elseif(pre->key<t->key)pre=t；∥前驱指针指向当前结点elseflag=flase；∥不是完全二叉树judgebst（t->rchild&&flag）；∥中序遍历右子树}∥JudgeBST算法结束本题的另一算法是照定义，二叉查找树的左右子树都是二叉查找树，根结点的值大于左子树中所有值而小于右子树中所有值，即根结点大于左子树的最大值而小于右子树的最小值。算法如下：intJudgeBST（BSTreet）∥判断二叉树t是否是二叉查找树，若是，返回true，否则，返回false{if（t==null）returntrue；if(judgebst(t->lchild)&&judgebst(t->rchild)）∥若左右子树均为二叉查找树{m=max(t->lchild)；n=min(t->rchild)；∥左子树中最大值和右子树中最小值return(t->key>m&&t->key<n）；}elsereturnfalse；∥不是二叉查找树}∥结束judgebstintmax（BSTreep）∥求二叉树左子树的最大值{if（p==null）return-maxint；∥返回机器最小整数else{while（p->rchild）p=p->rchild；returnp->key；}}intmin（BSTreep）∥求二叉树右子树的最小值{if（p==null）returnmaxint；∥返回机器最大整数else{while（p->lchild）p=p->lchild；returnp->key；}}2、【题目分析】按着“右子树－根结点－左子树”遍历二叉查找树，并输出结点的值。voidInvertOrder(BSTreebt)∥按递减次序输出二叉查找树结点的值{BiTreep=bt;if(p){InOrder(bt->rchild);∥中序遍历右子树printf(p->data);∥访问根结点InOrder(bt->lchild);∥中序遍历左子树}∥if}∥结束3、typedefstructnode{ElemTypedata；intcount；structnode*lchild，*rchild；}BiTNode，*BSTree；voidSearch_InsertX(BSTreet，ElemTypeX)∥在二叉查找树t中查找值为X的结点，若查到，则其结点的count域值增1∥否则，将其插入到二叉查找树中{p=t；while(p!=null&&p->data!=X)∥查找值为X的结点，f指向当前结点的双亲{f=p；if(p->data<X)p=p->rchild;elsep=p->lchild;}if(!p)∥无值为x的结点，插入之{p=(BiTNode*)malloc(sizeof(BiTNode))；p->data=X；p->lchild=null；p->rchild=null；p->count=0;if(t==null)t=p;∥若初始为空树，则插入结点为根结点elseif(f->data>X)f->lchild=p；elsef->rchild=p；}elsep->count++；∥查询成功，值域为X的结点的count增1}∥Search_InsertX4、【题目分析】因为平衡二叉树各结点已标明了平衡因子b，故从根结点开始记树的层次。根结点的层次为1，每下一层，层次加1，直到层数最大的叶子结点，这就是平衡二叉树的高度。当结点的平衡因子b为0时，任选左、右一分枝向下查找，若b不为0，则沿左(当b=1时)或右(当b=-1时)子树向下查找。intHeight(AVLTreet)∥求平衡二叉树t的高度{level=0；p=t；while(p){level++；∥树的高度增1if(p->bf<0)p=p->rchild；∥bf=-1沿右分枝向下elsep=p->lchild；∥bf>=0沿左分枝向下}∥whilereturn(level)；∥平衡二叉树的高度}∥算法结束5、[问题分析]设n个元素存于向量中，元素两两比较，每次比较的大者置于向量的一端，小者置于向量的另一端，一趟比较后将元素分成大者端和小者端，比较次数是n/2。接着对大者端和小者端分别进行简单选择排序，选出最大元素和最小元素，各需n/2-1次比较，总共比较次数不超过3n/2-2。voidMaxMinSele(SeqListr)∥用最多3n/2-2次比较在n个元素r中选出最大值和最小值{for(i=0,j=n-1-i;i<j;i++,j--)if(r[i].key>r[j].key)r[i]<-->r[j];if(i>j){i--;j++;}∥n为偶数时k=0;for(m=k+1;m<i;m++)if(r[m].key<r[k].key)k=m;printf(“最小值＝%d\n”,r[k].key);k=j;for(m=j+1;m<n;m++)if(r[m].key>r[k].key)k=m;printf(“最大值＝%d\n”,r[k].key);}6、引子知乎2022年408真题数据结构篇（修订版）-知乎()方法一：利用二叉搜索树的性质：设x是二叉搜索树中的一个结点。如果y是x左子树中的一个结点，那么，y.key<=x.key，如果y是x右子树中的一个结点，那么y.key>=x.keyboolhelper(SqBiTreeT,inti,longlonglower,longlongupper){if(i>=T.ELemNum||T.SqBiTNode[i]==-1){//越界或者为空结点returntrue;}if(T.SqBiTNode[i]<=lower||T.SqBiTNode[i]>=upper){returnfalse;}returnhelper(T,2*i+1,lower,T.SqBiTNode[i])&&helper(T,2*i+2,T.SqBiTNode[i],upper);}boolisValidBST(SqBiTreeT){returnhelper(T,0,LONG_MIN,LONG_MAX);}方法二：中序遍历利用二叉搜索树的性质的推论：中序遍历为单调递增序列。递归遍历：由于无法记录前驱，考虑保存整个中序遍历序列，最后进行检查。voidinorder(SqBiTreeT,inti,int*a,int*j){if(i>=T.ELemNum||T.SqBiTNode[i]==-1){//越界或者为空结点return;}inorder(T,2*i+1,a,j);a[(*j)++]=T.SqBiTNode[i];inorder(T,2*i+2,a,j);}boolisValidBST(SqBiTreeT){int*a=(int*)malloc(sizeof(int)*MAX_SIZE);intj=0;inorder(T,0,a,&j);for(intk=0;k<j-1;k++){if(a[k]>=a[k+1]){returnfalse;}