習(xí)題答案5選擇題DABBBAAC填空題三元組表，鏈式存儲結(jié)構(gòu)（1）288（2）282（3）72（4）276（5）A[2][3]判斷題對錯錯錯對應(yīng)用題1、[題目分析]三對角矩陣第一行和最后一行各有兩個非零元素，其余每行均有三個非零元素，所以共有3n-2個元素。（1）主對角線左下對角線上的元素下標間有i=j+1關(guān)系，k與i和j的關(guān)系為k=3(i-1);主對角線上元素下標間有關(guān)系i=j，k與i和j的關(guān)系為k=3(i-1)+1;主對角線上右上那條對角線上元素下標間有關(guān)系i=j-1，k與i和j的關(guān)系為k=3(i-1)+2。綜合以上三等式，有k=2(i-1)+j(1<=i，j<=n，|i-j|<=1)（2）i=k/3+1；（1≤k≤3n-2） //k/3取k被3除所得結(jié)果的最大整數(shù)。下同j=k-2(i-1)=k-2(k/3)=k%3+k/32、特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規(guī)律，因此可以對非零元素分配單元（對值相同元素只分配一個單元），將非零元素存儲在向量中，元素的下標i和j和該元素在向量中的下標有一定規(guī)律，可以用簡單公式表示，仍具有隨機存取功能。而稀疏矩陣是指非零元素和矩陣容量相比很?。╰<<m*n），且分布沒有規(guī)律。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機存取的功能。即使用三元組表的順序存儲結(jié)構(gòu)，存取下標為i和j的元素時，要掃描三元組表，下標不同的元素，存取時間也不同，最好情況下存取時間為O(1)，最差情況下是O(n)，因此也失去了隨機存取的功能。算法設(shè)計1、（1）#include<iostream>#include<iomanip>usingnamespacestd;intmain(){while(1){intn,a[1000];cin>>n;cout<<"請輸入"<<n*(n+1)/2<<"個數(shù):";for(inti=0;i<n*(n+1)/2;i++)cin>>a[i];for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(i>=j)cout<<setw(3)<<a[i*(i+1)/2+j]<<"";elsecout<<setw(3)<<a[j*(j+1)/2+i]<<"";}cout<<endl;}cout<<"節(jié)約"<<n*n-n*(n+1)/2<<"個空間."<<endl;}return0;}（2）#include<iostream>#include<iomanip>usingnamespacestd;intmain(){while(1){intn,a[1000];cin>>n;cout<<"請輸入"<<n*(n+1)/2+1<<"個數(shù):";for(inti=0;i<n*(n+1)/2+1;i++)cin>>a[i];//上三角for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(i<=j)cout<<setw(3)<<a[(2*n-i+1)*i/2+(j-i)]<<"";elsecout<<setw(3)<<a[n*(n+1)/2]<<"";}cout<<endl;}cout<<"節(jié)約"<<n*n-n*(n+1)/2-1<<"個空間."<<endl;}//下三角/*for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(i>=j)cout<<setw(3)<<a[i*(i+1)/2+j]<<"";elsecout<<setw(3)<<a[n*(n+1)/2]<<"";}cout<<endl;}*/return0;}（3）#include<iostream>#include<cmath>#include<iomanip>usingnamespacestd;intmain(){intn,d,a[100],m;cin>>n>>d;cout<<"請輸入"<<(n*(2*d+1)-d*d-d+1)<<"個數(shù):";for(inti=0;i<n*(2*d+1)-d*d-d+1;i++)cin>>a[i];for(inti=0;i<n;i++){for(intj=0;j<n;j++){if(fabs(i-j)<=d)cout<<setw(3)<<a[(i*(2*d+1)-d)+(j-i+d)]<<"";elsecout<<setw(3)<<a[n*(2*d+1)-d*d-d]<<"";}cout<<endl;}cout<<"節(jié)約"<<n*n-(n*(2*d+1)-d*d-d+1)<<"個空間."<<endl;return0;}2、[題目分析]實際上，數(shù)組c存儲的是上三角矩陣a按列序為主序遍歷的結(jié)果，對于a中元素a[i][j]易知其在c中的存儲位置為j*(j+1)/2+i,我們可按行主序遍歷矩陣a,設(shè)a[i][j]在b中的下標為k,這樣可求得c[j*(j+1)/2+i]的值.template<classT>voidMatrixRowToCol(T*b,intn){inti,j,k=0;T*c=newT[n*(n+1)/2];for(i=0;i<n;i++){ //行下標for(j=i;j<n;j++){ //列下標c[j*(j+1)/2+i]=b[k++];//b中的元素b[k],相應(yīng)地在c中下標為j*(j+1)/2+i} }for(k=0;k<n*(n+1)/2;k++)cout<<c[k]<<"";cout<<endl;}3、【題目分析】尋找馬鞍點最直接的方法,是在一行中找出一個最小值元素,然后檢查該元素是否是元素所在列的最大元素,如是,則輸出一個馬鞍點,時間復(fù)雜度是O(m*(m+n)).本算法使用兩個輔助數(shù)組max和min,存放每列中最大值元素的行號和每行中最小值元素的列號,時間復(fù)雜度為O（m*n+m），但比較次數(shù)比前種算法會增加，也多使用向量空間。intm=10,n=10;voidSaddle(intA[m][n])//A是m*n的矩陣,本算法求矩陣A中的馬鞍點{ inti,j,max[n]={0}, //max數(shù)組存放各列最大值元素的行號,初始化為行號0min[m]={0}; //min數(shù)組存放各行最小值元素的列號,初始化為列號0for(i=0;i<m;i++) //選各行最小值元素和各列最大值元素.for(j=0;j<n;j++){if(A[max[j]][j]<A[i][j])max[j]=i;//修改第j列最大元素的行號if(A[i][min[i]]>A[i][j])min[i]=j;//修改第i行最小元素的列號}for(i=0;i<m;i++){j=min[i]; //第i行最小元素的列號存于jif(i==max[j]) //若第j列的最大元素的行號剛好等于iprintf(“A[%d][%d]是馬鞍點，元素值是%d”,i,j,A[i][j]);∥是馬鞍點}}4、template<classT>boolTriple<T>::addMatrix(Triple<T>&A,Triple<T>&B){inti,j;Tva,vb,vc;if(A.numRow!=B.numRow||A.numCol!=B.numCol)returnfalse;//行數(shù)或列數(shù)不等時不能進行相加運算numRow=A.numRow; //C的行數(shù)賦值A(chǔ)的行數(shù)numCol=B.numCol; //C的列數(shù)賦值B的列數(shù)maxSize=A.numRow*B.numCol;delete[]matrix;matrix=newNode[maxSize]; //c的行列數(shù)與a的相同curLength=0;for(i=0;i<numRow;i++)for(j=0;j<numCol;j++){va=A.getValue(i,j);vb=B.getValue(i,j);vc=va+vb;if(vc)setValue(i,j,vc);}returntrue;}5、【題目分析】題目要求按B數(shù)組內(nèi)容調(diào)整A數(shù)組中記錄的次序，可以從i=1開始，檢查是否B[i]=i。如是，則A[i]恰為正確位置，不需再調(diào)；否則，B[i]=k≠i，則將A[i]和A[k]對調(diào)，B[i]和B[k]對調(diào)，直到B[i]=i為止。template<classrectype>voidCountSort(rectypeA[],intB[])//A是100個記錄的數(shù)組，B是整型數(shù)組，本算法利用數(shù)組B對A進行計數(shù)排序{inti,j,n=100;i=1;while(i<=n){if(B[i]!=i) //若B[i]=i則A[i]正好在自己的位置上，則不需要調(diào)整{j=i;while(B[j]!=i){k=B[j];B[j]=B[k];B[k]=k;//B[j]和B[k]交換r0=A[j];A[j]=A[k];A[k]=r0;} //r0是數(shù)組A的元素類型,A[j]和A[k]交換i++;} //完成了一個小循環(huán)，第i個已經(jīng)安排好}}6、【題目分析】從集合(1..n)中選出k(本題中k=2)個元素,為了避免重復(fù)和漏選,可分別求出包括1和不包括1的所有組合.即包括1時,求出集合(2..n)中取出k-1個元素的所有組合;不包括1時,求出集合(2..n)中取出k個元素的所有組合.,將這兩種情況合到一起,就是題目的解.說明：i從1開始，表示當前的起始下標，k表示取k個元素intA[],n;//設(shè)集合已存于數(shù)組A中,假定數(shù)組下標從1開始voidcomb(intP[],inti,intk){ if(k==0)print(P);elseif(k<=n){P[i]=A[i];comb(P,i+1,k-1); //包含i，從i+1位置開始取k-1個comb(P,i+1,k); //不包含i，從i+1位置開始取k個}}習(xí)題答案6一、選擇1-5:BCCCB6-10:BBBDC11-15:CDACD16:C二、填空1、(1)2H-1(2)2H-1(3)H=log2N+12、(1)0(2)(n-1)/2或n/2(3)(n+1)/2(4)log2(n+1)3、(1)n1-1(2)n2+n34、(1)2k-2+1（第k層1個結(jié)點，總結(jié)點個數(shù)是2H-1，其雙親是2H-1/2=2k-2）(2)log2i+15、n/26、(1)a(2)dbe(3)hfcg7、cedba8、(1)前驅(qū)(2)后繼三、判斷題1-8:錯對對對對對錯錯四、應(yīng)用題1、設(shè)樹的結(jié)點數(shù)為n，分枝數(shù)為B，則下面二式成立 n=n0+n1+n2+…+nm (1) n=B+1=n1+2n2+…+mnm (2)由(1)和(2)得葉子結(jié)點數(shù)：2、提示：tLRLtRLRt若先序序列與后序序列相同，則或為空樹，或為只有根結(jié)點的二叉樹；若中序序列與后序序列相同，則或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹；若先序序列與中序序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹；若中序序列與層次遍歷序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹。3A,B,F,JE,D,HC,K,G4、5、（1）中序：DBCEAF后序：DECBFA（2）aaaaaaaaaaaaaaABFDCE6、【提示】森林的先序和后序分別對應(yīng)二叉樹的先序和中序，先構(gòu)造二叉樹，然后轉(zhuǎn)換成森林FAFAEBDCJHGIKONLMG7、(1)先序序列：ABCDEFGHIJ后序序列：BCDAFEHJIG(2)(3)后序序列：DCBFJIHGEA8、AABFD(3)CEHG(1)(2)9、（1）正則k叉樹只含有兩類結(jié)點：葉結(jié)點（n0個）和度為k的分支結(jié)點（nk個）。樹T中的結(jié)點總數(shù)n=n0+nk=n0+m，樹中所含的分支數(shù)b=n-1，這些分支均為度為k的結(jié)點發(fā)出的，即b=m*k，故n0=（k-1）*m+1（2）高度為h的正則k叉樹T中，含最多結(jié)點的樹形為：除第h層外，第1到第h-1層的結(jié)點都是度為k的分支結(jié)點，而第h層均為葉結(jié)點，即樹是“滿”樹。此時第j（1<=j<=h）層結(jié)點數(shù)為kj-1，結(jié)點總數(shù)M1為：（k^h-1)/(k-1)含最少結(jié)點的正則k叉樹的樹形為：第1層只有根結(jié)點，第2到第h-1層僅含1個分支結(jié)點和k-1個葉結(jié)點，第h層有k個葉結(jié)點。即除根外第2層到第h層中每層的結(jié)點數(shù)均為k，故T中所含結(jié)點總數(shù)M2為：k(h-1)+1五、算法設(shè)計題1、【題目分析】結(jié)點計數(shù)可以在遍歷中解決。根據(jù)“訪問根結(jié)點”在“遞歸遍歷左子樹”和“遞歸遍歷右子樹”中位置的不同，而有前序、后序和中序遍歷。//設(shè)置三個全局變量，分別記度為2，1和葉子結(jié)點的個數(shù)intn2,n1,n0;voidCount(BiTreet){ if(t) {if(t->left&&t->right)n2++;elseif(t->left&&!t->right||!t->left&&t->right)n1++;elsen0++; if(t->left!=null)Count(t->left); if(t->right!=null)Count(t->right);}}2、從根節(jié)點的左右子樹進行交換，然后以根節(jié)點的左子樹為根節(jié)點，而后以根節(jié)點的右結(jié)點為根節(jié)點，進行左右子樹交換。遇到空節(jié)點或葉節(jié)點直接返回。下面求二叉樹鏡像的函數(shù)代碼實現(xiàn)：template<classT>voidBinaryLinkList<T>::MirroTree(Node*root){

if(root==NULL)return;

if(root->left==NULL&&root->right==NULL)return;

else

{

TreeNode*temp=root->left;

root->left=root->right;

root->right=temp;

}

MirroTree(root->left);

MirroTree(root->right);}3、求最大寬度可采用層次遍歷的方法，記下各層結(jié)點數(shù)，取其最大寬度。代碼經(jīng)過測試template<classelemType>intBinaryLinkList<elemType>::Width(){ if(root==NULL)return(0); //空二叉樹寬度為0 Node*p=root; Node**Q=newNode*[size()]; //Q是隊列，元素為二叉樹結(jié)點指針 intfront=1,rear=1; //front隊頭指針,rear隊尾指針, intlast=1; //last同層最右結(jié)點在隊列中的位置 inttemp=0,maxw=0; //temp記當前層寬度,maxw記最大寬度 Q[rear]=p; //根結(jié)點入隊列 while(front<=last){ p=Q[front++];temp++; //同層元素數(shù)加1 if(p->left!=NULL)Q[++rear]=p->left;//左子女入隊 if(p->right!=NULL)Q[++rear]=p->right;//右子女入隊 if(front>last){ //一層結(jié)束， last=rear; //last指向下層最右元素 if(temp>maxw)maxw=temp; //更新當前最大寬度 temp=0; } } delete[]Q; return(maxw);}4、template<classT>boolEqual(Node*p,Node*q){ //pq是指向兩顆二叉樹根結(jié)點的指針if(p==NULL&&q==NULL)returntrue;elseif(!p&&q||p&&!q||p->data!=q->data)returnfalse;elsereturn(Equal(p->left,q->left)&&Equal(p->right,q->right));}5、【題目分析】二叉樹的順序存儲是按完全二叉樹的順序存儲格式，雙親與子女結(jié)點下標間有確定關(guān)系。順序存儲結(jié)構(gòu)的二叉樹用結(jié)點下標大于n（完全二叉樹）或0（對一般二叉樹的“虛結(jié)點”）判空。本題是完全二叉樹。template<classT>voidPreOrder(Tbt[],intn)//對以順序結(jié)構(gòu)存儲的完全二叉樹bt進行前序遍歷{inti=1,top=0,s[2*n]; //top是棧s的棧頂指針，棧容量足夠大while(i<=n||top>0){while(i<=n){cout<<bt[i]<<””; //訪問根結(jié)點；if(2*i+1<=n)s[++top]=2*i+1; //右子女的下標位置進棧i=2*i; //沿左子女向下}if(top>0)i=s[top--]; //取出棧頂元素}}6、template<classT>BinaryTreeNode<T>*BinaryTree<T>::createtChainBinaryTree(TA[],inti,intn)//n是數(shù)組中元素個數(shù){ BinaryTreeNode<T>*pointer; if(i>n)pointer=NULL; else { pointer=newBinaryTreeNode<T>();//申請結(jié)點 pointer->info=A[i]; pointer->left=createtChainBinaryTree(A,2*i,n); pointer->right=createtChainBinaryTree(A,2*i+1,n); }returnpointer;}//root=createtChainBinaryTree(A,1,9);//數(shù)組0號沒使用，使用下標1~9元素//本代碼基于舊實驗里的BinaryTree<T>類7、ABDABDGECFIHJ本題生成的二叉樹見下圖。template<classT>Node<T>*binaryChainList<T>::inLevelCreat(Tin[],Tlevel[],intn,intl1,inth1){//n(n>0)是二叉樹的結(jié)點數(shù)，l1和h1是二叉樹中序序列低端和高端的下標 Node<T>*p;if(n>0){ inti;T*level2=newT[n];p=newNode<T>();p->setValue(level[0]); //level[0]是根結(jié)點for(i=l1;i<=h1;i++) //在中序序列中查找根結(jié)點(level[0])的位置if(in[i]==level[0])break;if(i==l1)p->setLeftchild(NULL); //無左子樹else{ intii=-1;for(intk=1;k<n;k++) //除根外整棵二叉樹層次序列的下標從1到n-1for(intj=l1;j<i;j++) //左子樹中序序列下標從l1到i-1if(level[k]==in[j]){ //形成左子樹的層次序列 level2[++ii]=level[k];break;}//下面由左子樹的層次序列和中序序列遞歸生成左子樹p->setLeftchild(inLevelCreat(in,level2,ii+1,l1,i-1)); }if(i==h1)p->setRightchild(NULL); //無右子樹else{ intii=-1;for(intk=1;k<n;k++) //除根外整棵二叉樹層次序列的下標從1到n-1for(intj=