算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）（馮廣慧第2版）習(xí)題解答匯總 第1-12章

習(xí)題答案選擇題ADDACC填空題（1）樹形結(jié)構(gòu)、（2）圖形結(jié)構(gòu)（1）確定性、（2）輸出（1）時間復(fù)雜度、（2）空間復(fù)雜度（1）1:1、（2）1:n、（3）n:n判斷題1-4錯錯對對習(xí)題答案選擇1-10：ADBACABDAD填空1、（a）元素的存儲位置（b）指針2、p->next!=NULL3、L->next==L或L->prior==L或L->prior==L&&L->next==L…或L->next==L->next…..（a）O(1)（b）O(n)判斷1-6：對錯錯錯錯錯四、應(yīng)用1、在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標(biāo)識作用，故常用頭指針冠以鏈表的名字。頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等）。有頭結(jié)點后，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。首元結(jié)點也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。2、選順序存儲結(jié)構(gòu)。順序表可以隨機存取，時間復(fù)雜度為O（1）。3、鏈?zhǔn)酱鎯Y(jié)構(gòu)一般說克服了順序存儲結(jié)構(gòu)的三個弱點。首先，插入、刪除不需移動元素，只修改指針，時間復(fù)雜度為O(1)；其次，不需要預(yù)先分配空間，可根據(jù)需要動態(tài)申請空間；其三，表容量只受可用內(nèi)存空間的限制。其缺點是因為指針增加了空間開銷，當(dāng)空間不允許時，就不能克服順序存儲結(jié)構(gòu)的缺點。4、參見2.6節(jié)5、單循環(huán)鏈表往往只設(shè)尾指針而不設(shè)頭指針，用一個指向尾結(jié)點的尾指針來標(biāo)識單循環(huán)鏈表，好處是既方便查找表尾結(jié)點又方便查找頭結(jié)點，因為通過尾結(jié)點的指針域很容易找到頭結(jié)點。若使用頭指針查找表尾結(jié)點需要從頭遍歷鏈表，時間復(fù)雜度是O(n)。五、算法設(shè)計題1、SeqListRearrange(SeqLista){ inti,j,t; i=0;j=a.Last-1;//i,j為工作指針(下標(biāo)) t=a.data[0];//暫存樞軸元素。 while(i<j) { while(i<j&&a.data[j]>=0)j--; //j指針前移找小于0的元素 if(i<j)a.data[i++]=a.data[j]; //將負(fù)數(shù)前移 while(i<j&&a.data[i]<0)i++;//i指針后移找大于等于0的元素 if(i<j)a.data[j--]=a.data[i]; //正數(shù)后移 } a.data[i]=t; //將原第一元素放到最終位置 returna;}2、(1)LinkedListDelSame（LinkedListla）{ pre=la->next； ∥pre是p所指向的前驅(qū)結(jié)點的指針 p=pre->next； ∥p是工作指針，設(shè)鏈表中至少有一個結(jié)點 while（p） if（p->data==pre->data）∥相同元素值,釋放結(jié)點{u=p；pre->next=p->next;p=p->next；free（u）；} else {pre=p；p=p->next；} ∥元素值不同 returnla;}(2)算法時間復(fù)雜度O(n)3、DLinkedListDInsert(DLinkedListla,ElemTypex){ p=la->next; ∥p指向第一元素 ∥MaxElemType是和x同類型的機器最大值，用做監(jiān)視哨 la->data=MaxElemType; while(p->data<x) ∥尋找插入位置 p=p->next

; s=(DLNode*)malloc(sizeof(DLNode));∥申請結(jié)點空間 s->data=x; s->prior=p->prior; ∥將插入結(jié)點鏈入鏈表 s->next=p; p->prior->next=s; p->prior=s;}4、（1）①分別求出str1和str2所指的兩個鏈表的長度m和n；②將兩個鏈表以表尾對齊：即長的鏈表將指針移到|m-n+1|,短鏈表的指針指向鏈表的第一個字母；=3\*GB3③兩個鏈表進(jìn)行模式匹配：對應(yīng)字母比較，從最后遇到兩個鏈表結(jié)點值相等，直至到表尾對應(yīng)結(jié)點值都相等為止。要注意處理雖然首次遇到對應(yīng)結(jié)點值相等，但有后續(xù)結(jié)點值不等的情況,即在匹配中，并非一遇到對應(yīng)字母相等，就結(jié)論后邊是共同后綴。（2）求用單鏈表表示的兩個單詞的共同后綴的算法typedefstructNode{ ElemTypedata;structNode*next;}LNode,*LinkedList；intListLength(LNode*la){//求鏈表la的長度inti=0;LNode*p=la->next; //p指向鏈表的第一個元素結(jié)點while(p){i++; //元素個數(shù)加1p=p->next; //鏈表指針后移}returni; //返回鏈表的長度}LNode*ComPostfix(LNode*str1,LNode*str2){//str1和str2分別是單詞以單鏈表存儲的頭指針，本算法返回兩個單詞共同后綴的起始位置p=null; //p指向兩個鏈表共同后綴的起始位置m=ListLength(str1);n=ListLength(str2); //求鏈表str1和str2的長度if(m>n){ s=str1->next; //s指向長鏈表的第一個元素 q=srt2->next; //q指向短鏈表的第一個元素 len=m-n+1; //兩個鏈表開始比較時，長鏈表應(yīng)移到的位置}else{ s=str2->next; //s指向長鏈表的第一個元素 q=srt1->next; //q指向短鏈表的第一個元素 len=n-m+1; //兩個鏈表比較時，長鏈表應(yīng)移到的位置}i=1;while(i<len){i++;s=s->next;} //長鏈表要移到兩個鏈表尾部對齊的位置while(s){while(s&&s->data!=q->data)//對應(yīng)字母不等，后移指針 { s=s->next;q=q->next;}p=s; //p指向兩個鏈表共同后綴的起始位置while(s&&s->data==q->data)//如對應(yīng)字母相等，后移指針{ s=s->next;q=q->next;}}returnp; //返回兩個鏈表共同后綴的起始位置}（3）算法中求了兩個鏈表的長度，接著將長鏈表的指針移到兩鏈表的比較處，進(jìn)行對應(yīng)元素的比較，記住可能共同后綴的開始位置，直到鏈表尾?？偟臅r間復(fù)雜度為O(m+n)。5、(1)算法思想：定義一個大小為N的數(shù)組，初始化為0.在遍歷鏈表的同時將數(shù)組中索引值為節(jié)點的值的絕對值的元素置1.如果此元素已經(jīng)為1，說明此節(jié)點之前已經(jīng)有與此節(jié)點的值的絕對值相等的節(jié)點，需將此節(jié)點刪除。(2)節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義如下：typedefstructNode{Intdata;StructNode*next;}Node;(3)inta[n];//全局?jǐn)?shù)組標(biāo)志節(jié)點的絕對值的值是否出現(xiàn)過voidDeleteABSEqualNode(Node*head){ memset(a,0,n);//初始化為0 if(head==NULL)returnNULL; Node*p=head; Node*r=head; while(p!=NULL) { if(a[abs(p->data)]==1) //如果此絕對值已經(jīng)在數(shù)組中出現(xiàn)過，則刪除 { r->next=p->next;deletep;p=r->next;} else//否則，將數(shù)組中對應(yīng)的元素置1 { a[abs(p->data)]=1;r=p;p=p->next;} } returnhead;}(4)只遍歷一次鏈表，所以時間復(fù)雜度為O(n)因為申請大小為n的數(shù)組，所以空間復(fù)雜度為O(n)（n為節(jié)點絕對值的最大值）。6、(1)算法思想由于數(shù)組中有n個整數(shù)，則未出現(xiàn)的最小的正整數(shù)一定在1到n+1的范圍，假如：數(shù)組a為[1,2,3,4]，則最小正整數(shù)為5，也就是n+1。如果數(shù)組中介于1到n之間的正整數(shù)個數(shù)不足n個，則未出現(xiàn)的最小的正整數(shù)的范圍是1到n。設(shè)置一個輔助數(shù)組b,大小為n+2,初始值全部為0，然后對a[i]進(jìn)行遍歷，如果0<a[i]<=n+1，則將b[a[i]]賦值為1，接下來遍歷b數(shù)組，遇到的第一個滿足b[i]==0的就退出，i就是數(shù)組a中未出現(xiàn)過的最小正整數(shù)(2)代碼實現(xiàn)intfindMissMin(intA[],intn){int*B=newint[n]; //創(chuàng)建動態(tài)數(shù)組memset(B,0,n*sizeof(int)); //賦初值inti;for(i=0;i<n;++i){ if(A[i]>0&&A[i]<n){//僅處理A中范圍在1~n的元素B[A[i]-1]++;}}for(i=0;i<n;++i){if(B[i]==0)break;}delete[]B;returni+1;}(3)算法的時間復(fù)雜度為O(n);空間復(fù)雜度為O(n)。7、(1)算法思想①首先尋找單鏈表的中心結(jié)點，使用兩個指針p、q，每次p走一步，q走兩步，當(dāng)q到鏈表尾時，p正好在鏈表中心的位置。②將鏈表后半段利用頭插法逆置。③從單鏈表前后兩段中依次各取一個結(jié)點，并重新排列。(2)代碼實現(xiàn)voidrealign(NODE*h){NODE*p,*q,*r,*s;p=q=h;while(q->next!=NULL){ //尋找中間結(jié)點p=p->next; //p向后移動一個結(jié)點q=q->next;if(q->next!=NULL)q=q->next;//q向后移動兩個結(jié)點}q=p->next; //p指向中間結(jié)點，q指向p后面的結(jié)點p->next=NULL;while(q!=NULL){ //從q開始逆置后半段r=q->next;q->next=p->next; //p是中間結(jié)點，每次新結(jié)點插入在p之后p->next=q;q=r;}s=h->next; //s指向前半部分的第一個結(jié)點q=p->next; //q指向后半部分的第一個結(jié)點p->next=NULL; //分成2個單鏈表while(q!=NULL){ //歸并單鏈表r=q->next;q->next=s->next; //將q指向的結(jié)點插入到s指向結(jié)點的后面s->next=q;s=q->next;q=r;}}(3)時間復(fù)雜度為O(n)習(xí)題答案一、選擇題1-5B、B、D、B、B6-10B、A、D、BD、C、二、填空題1、先進(jìn)后出，先進(jìn)先出2、23.12.3*2-4/34.5*7/++108.9/+3、假溢出4、rear=(rear+1)%ns=newLnode(x)；s->next=r->next；r->next=s；r=s5、O(1),O(n),O(1),O(1)三、判斷題對錯對對對四、應(yīng)用題三個：CDEBA，CDBEA，CDBAE435612不可以321，325641可以，154623不可以432，135426可以Rear=4和front=2隊列為滿的條件：(rear+1)%MaxSize==front隊列為空的條件:front==rear5、(1)A*B*C(2)(A+B)*C-D(3)A*B+C/(D-E)(4)(A+B)*D+E/(F+A*D)+C(1)ABC** (2)AB+C*D- (3)AB*CDE-/+ (4)AB+D*EFAD*+/C+五、算法設(shè)計題1、#definemaxsize100//兩棧共享順序存儲空間所能達(dá)到的最多元素數(shù)#defineElemTypeint∥假設(shè)元素類型為整型typedefstruct{ ElemTypestack[maxsize];∥?？臻g inttop[2];∥top為兩個棧頂指針}stk;stks;∥s是如上定義的結(jié)構(gòu)類型變量，//為全局變量入棧操作：intpush(inti,intx)∥入棧。i=0表示左棧s1，i=1表示右棧s2，x是入棧元素。入棧成功返回1，否則返回0{ if(i<0||i>1){printf(“棧號輸入不對\n”);exit(0);} if(s.top[1]-s.top[0]==1){printf(“棧已滿\n”);return(0);} switch(i) {case0:s.stack[++s.top[0]]=x;return(1);break; case1:s.stack[--s.top[1]]=x;return(1); }}∥push退棧操作:ElemTypepop(inti)∥退棧算法。i=0時為s1棧，i=1時為s2棧。退棧成功返回退棧元素，否則返回-1{ if(i<0||i>1){printf(“棧號輸入錯誤\n”)；exit(0);} switch(i) {case0:if(s.top[0]==-1){printf(“?？誠n”)；return（-1）；} elsereturn(s.stack[s.top[0]--]); case1:if(s.top[1]==maxsize){printf(“棧空\n”);return(-1);} elsereturn(s.stack[s.top[1]++]);}∥switch}∥算法結(jié)束判斷?？読ntEmpty();{return(S.top[0]==-1&&S.top[1]==m);}2、（1）初始化SeQueueQueueInit(SeQueueQ){//初始化隊列 Q.front=Q.rear=0;Q.tag=0; returnQ;}（2）入隊SeQueueQueueIn(SeQueueQ,inte){//入隊列 if((Q.tag==1)&&(Q.rear==Q.front)) printf("隊列已滿\n");

else{Q.rear=(Q.rear+1)%m; Q.data[Q.rear]=e;if(Q.tag==0)Q.tag=1;//隊列已不空 } returnQ;}(3)出隊ElemTypeQueueOut(SeQueueQ){//出隊列 if(Q.tag==0){printf("隊列為空\n");exit(0);}

else { Q.front=(Q.front+1)%m; e=Q.data[Q.front]; if(Q.front==Q.rear)Q.tag=0;//空隊列 } return(e);}3、（1）循環(huán)隊列的定義typedefstruct{ ElemTypeQ[m];∥循環(huán)隊列占m個存儲單元 intrear,length;∥rear指向隊尾元素,length為元素個數(shù)}SeQueue;(2)初始化SeQueueQueueInit(SeQueuecq)∥cq為循環(huán)隊列，本算法進(jìn)行隊列初始化{ cq.rear=0; cq.length=0; returncq;}(3)入隊SeQueueQueueIn(SeQueuecq，ElemTypex)∥cq是以如上定義的循環(huán)隊列，本算法將元素x入隊{ if(cq.length==m)return(0);∥隊滿 else {cq.rear=(cq.rear+1)%m;∥計算插入元素位置 cq.Q[cq.rear]=x;∥將元素x入隊列 cq.length++;∥修改隊列長度 } return(cq);}（4）出隊ElemTypeQueueOut(SeQueuecq)∥cq是以如上定義的循環(huán)隊列，本算法是出隊算法，且返回出隊元素{ if(cq.length==0)return(0);∥隊空 else {intfront=(cq.rear-cq.length+1+m)%m; ∥出隊元素位置 cq.length--;∥修改隊列長度

return(cq.Q[front]);∥返回對頭元素 }}4、（1）遞歸intAck(intm,n){if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ack(m-1,1));elsereturn(Ack(m-1,Ack(m,m-1));}∥算法結(jié)束（2）非遞歸intAckerman(intm,intn){intakm[M][N];intI,j;for(j=0;j<N;j++)akm[0][j];=j+1;for(i=1;i<m;i++){akm[i][0]=akm[i-1][1];for(j=1;j<N;j++)akm[i][j]=akm[i-1][akm[i][j-1]];}return(akm[m][n]);}∥算法結(jié)束5、intsympthy(charstr[],chars[]){inti=0,j,n;while(str[i]!=‘\0’)i++;//查字符個數(shù)n=i;for(i=0;i<n/2;i++)s[i]=str[i];//前一半字符入棧j=i-1;if(n%2==1)i++;//n為奇數(shù)時中間字符不用比較while(i<n&&str[i]==s[j])//比較字符串是否是回文{i++;j--;}if(i==n)printf(“字符串是回文\n”)；elseprintf(“字符串不是回文\n”)；}6、VoidPermute(intS[],intj,intn)∥對S[j]――S[n-1]中的n-j個元素進(jìn)行全排列，j的初值為0{ inti,temp; if(j==n-1)//只有一個元素 {for(i=0;i<n;i++)printf(“%5d”,S[i]);printf(“\n”);} else for(i=j;i<n;i++)//j位置元素固定，求j+1到n的全排列{temp=S[j];S[j]=S[i];S[i]=temp;Permute(S,j+1,n);temp=S[j];S[j]=S[i];S[i]=temp;}習(xí)題答案一、選擇題1-6B、A、B、D、C、B二、填空題1．字符2.O(m+n)3．-100112014．-10-10-1310三、判斷題對對錯錯四、應(yīng)用題1、空串：當(dāng)串的長度n=0時，串中沒有任何字符，稱為空串，如S=“”；空格串：由空格字符組成的串，稱為空格串，如S=“”子串：串中任意個連續(xù)的字符組成的子序列被稱為該串的子串?？沾侨我獯淖哟?；任意串S都是S自身的子串。主串：包含子串的串又被稱為該子串的主串。2、KMP的特點是主串無需回溯，主串指針一直往后移動，只有子串指針回溯，大大減少算法的比較次數(shù)和回溯次數(shù)。3、五、算法設(shè)計題1、[題目分析]設(shè)字符串存于字符數(shù)組X中，若轉(zhuǎn)換后的數(shù)是負(fù)數(shù)，字符串的第一個字符必為'-'轉(zhuǎn)換過程如下：將取出的數(shù)字字符減去字符零（'0'）的ASCII值，變成數(shù)；先前取出的數(shù)乘上10加上本次轉(zhuǎn)換的數(shù)形成部分結(jié)果；如此一個字符一個字符的轉(zhuǎn)換，直到字符串結(jié)束，得到結(jié)果。longatoi(char*X){longnum=0; //結(jié)果整數(shù)初始化inti=1; //i為數(shù)組下標(biāo)if(X==NULL){cout<<"PointerisNULL\n";return0;}if(X[0]!='-')num=X[0]-'0'; //如是正數(shù)，x[0]是數(shù)字字符while(X[i]!='\0') //當(dāng)字符串未到尾，進(jìn)行數(shù)的轉(zhuǎn)換num=10*num+(X[i++]-'0'); //先前取出的數(shù)乘上10加上本次轉(zhuǎn)換的數(shù)形成部分結(jié)果if(X[0]=='-')return(-num); //負(fù)數(shù)elsereturn(num); //返回正數(shù)}2、（1）//求重復(fù)子串的長度intrptSubLen(char*p,char*q){ intlen=0;while(*p&&*q){if(*p==*q){ ++len;p++,q++;}elsebreak;}returnlen;}（2）//求最長重復(fù)子串voidlongestRepeatSub(char*arr,intsize,int&maxLen,int&maxIndex){inti,j,len;maxLen=0; //記錄最長重復(fù)子串的長度maxIndex=-1; //記錄最長重復(fù)子串的下標(biāo)for(i=0;i<size;++i){for(j=i+1;j<size;++j){len=rptSubLen(&arr[i],&arr[j]);if(len>maxLen){maxLen=len;maxIndex=i;}}}if(maxLen==0)return;i=maxIndex;cout<<"Thelongestrepeatsubstring：";while(maxLen--)cout<<arr[i++];cout<<endl;}3、//利用4.2.1節(jié)已經(jīng)給定的順序存儲結(jié)構(gòu)的串的類型定義StringString&String::replace(intpos,intnum,constString&t){Stringtemp(*this); inti=0,j=0;if(pos<1||num<0){ //參數(shù)錯誤return*this;}curLen+=t.curLen-j; delete[]str; str=newchar[curLen+1]; assert(str!='\0'); while(i<pos-1) //拷貝原串前pos-1個元素str[i]=temp.str[i++];while(j<t.curLen) //拷貝t串str[i++]=t.str[j++];j=pos+num-1;while(temp.str[j]!='\0') //拷貝原串從第pos+num個到串尾的元素str[i++]=temp.str[j++];str[i]='\0';return*this;}4、voidInvertStore(charA[]){∥字符串逆序存儲的遞歸算法charch;staticinti=0; ∥使用靜態(tài)變量scanf("%c"，&ch);if(ch!='.') ∥'.'表示字符串輸入結(jié)束{InvertStore(A);A[i++]=ch; ∥字符串逆序存儲}A[i]='\0'; ∥字符串結(jié)尾標(biāo)記}∥InvertStore5、intCountInt（）｛charch;inti=0，a[]； ∥整數(shù)存儲到數(shù)組a，i記整數(shù)個數(shù)scanf(“％c”，&ch）； ∥從左到右讀入字符串while（ch!=‘#’） ∥‘#’是字符串結(jié)束標(biāo)記if(ch>=’0’&&ch<=’9’) ∥是數(shù)字字符｛num=０； ∥數(shù)初始化while（ch>=’0’&&ch<=’9’） ∥拼數(shù)｛num=num＊10+‘ch’-‘０’；scanf(“％c”，&ch）；｝a[i++]=num；if（ch!=‘#’） ∥若拼數(shù)中輸入了‘#’，則不再輸入scanf（“%c”，&ch）；｝elsescanf（“%c”，&ch）；∥輸入非數(shù)字且非＃時，繼續(xù)輸入字符printf（“共有%d個整數(shù)，它們是：”,i）；for（j=０；j<i；j++）｛printf（“%6d”，a[j]）；if（（j+1）％10==0）printf（“\n”）；}∥每10個數(shù)輸出在一行上｝∥CountInt6、#include<iostream>#include<cstring>#include<string>usingnamespacestd;intmain(){stringarr;inti,j,k=0;while(getline(cin,arr)){ if(arr=="STOP")break;k++;for(i=0,j=arr.length()-1;i<j;i++,j--){if(arr[i]!=arr[j])break; }if(i>=j) cout<<"#"<<k<<":YES"<<endl;else cout<<"#"<<k<<":NO"<<endl;}return0;}習(xí)題答案選擇題DABBBAAC填空題三元組表，鏈?zhǔn)酱鎯Y(jié)構(gòu)（1）288（2）282（3）72（4）276（5）A[2][3]判斷題對錯錯錯對應(yīng)用題1、[題目分析]三對角矩陣第一行和最后一行各有兩個非零元素，其余每行均有三個非零元素，所以共有3n-2個元素。（1）主對角線左下對角線上的元素下標(biāo)間有i=j+1關(guān)系，k與i和j的關(guān)系為k=3(i-1);主對角線上元素下標(biāo)間有關(guān)系i=j，k與i和j的關(guān)系為k=3(i-1)+1;主對角線上右上那條對角線上元素下標(biāo)間有關(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ī)律，因此可以對非零元素分配單元（對值相同元素只分配一個單元），將非零元素存儲在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡單公式表示，仍具有隨機存取功能。而稀疏矩陣是指非零元素和矩陣容量相比很?。╰<<m*n），且分布沒有規(guī)律。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機存取的功能。即使用三元組表的順序存儲結(jié)構(gòu)，存取下標(biāo)為i和j的元素時，要掃描三元組表，下標(biāo)不同的元素，存取時間也不同，最好情況下存取時間為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中的下標(biāo)為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++){ //行下標(biāo)for(j=i;j<n;j++){ //列下標(biāo)c[j*(j+1)/2+i]=b[k++];//b中的元素b[k],相應(yīng)地在c中下標(biāo)為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ù)不等時不能進(jìn)行相加運算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進(jìn)行計數(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開始，表示當(dāng)前的起始下標(biāo)，k表示取k個元素intA[],n;//設(shè)集合已存于數(shù)組A中,假定數(shù)組下標(biāo)從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í)題答案一、選擇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é)點的左右子樹進(jìn)行交換，然后以根節(jié)點的左子樹為根節(jié)點，而后以根節(jié)點的右結(jié)點為根節(jié)點，進(jìn)行左右子樹交換。遇到空節(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記當(dāng)前層寬度,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; //更新當(dāng)前最大寬度 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é)點下標(biāo)間有確定關(guān)系。順序存儲結(jié)構(gòu)的二叉樹用結(jié)點下標(biāo)大于n（完全二叉樹）或0（對一般二叉樹的“虛結(jié)點”）判空。本題是完全二叉樹。template<classT>voidPreOrder(Tbt[],intn)//對以順序結(jié)構(gòu)存儲的完全二叉樹bt進(jìn)行前序遍歷{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; //右子女的下標(biāo)位置進(jìn)棧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號沒使用，使用下標(biāo)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是二叉樹中序序列低端和高端的下標(biāo) 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++) //除根外整棵二叉樹層次序列的下標(biāo)從1到n-1for(intj=l1;j<i;j++) //左子樹中序序列下標(biāo)從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++) //除根外整棵二叉樹層次序列的下標(biāo)從1到n-1for(intj=i+1;j<=h1;j++) //右子樹中序序列下標(biāo)從i+1到h1if(level[k]==in[j]){//形成右子樹層次序列 level2[++ii]=level[k];break;}//下面由右子樹的層次序列和中序序列遞歸生成右子樹p->setRightchild(inLevelCreat(in,level2,ii+1,i+1,h1));}if(l1==0&&h1==n-1)root=p; //第一次調(diào)用時為root賦值}returnp;}8、template<classT>voidthreadBinaryTree<T>::preThreaded(){Node*pre=NULL;if(root!=NULL){preThreaded(root,pre); //調(diào)用私有中序線索化 pre->right=NULL; //pre指向中序序列最后一個結(jié)點pre->rTag=true;} }template<classT>voidthreadBinaryTree<T>::preThreaded(Node*current,Node*&pre){if(current==NULL)return;if(current->left==NULL){ //給當(dāng)前結(jié)點加前驅(qū)線索precurrent->left=pre;current->lTag=true;}if(pre!=NULL&&pre->right==NULL){ //給前驅(qū)加后繼線索pre->right=current;pre->rTag=true;}pre=current; //前驅(qū)指針后移if(T->lTag==0)preThreaded(current->left,pre); //左子樹前序線索化preThreaded(current->right,pre); //右子樹前序線索化}參考文獻(xiàn)/hangelsing/article/details/47807663卡特蘭數(shù)習(xí)題答案一、選擇題1-8：DCBBDDBC二、判斷題1-5：錯錯錯對錯三、填空題1.(1)80(2)001（不唯一）2.2n0-13.（1）5（2）964.（1）2h-1（2）2h-15、（1）順序（2）n/2+1（3）n四、應(yīng)用題1、哈夫曼樹的形態(tài)不唯一2、各字符的二進(jìn)制編碼為：a：00b：11110c：1110d：11111e：10f：110g：013、①是堆②不是堆調(diào)成堆100,90,80,25,85,75,60,20,10,70,65,504、27565346227565346261908170897875125035036539082754625128978717061(2)求次小值5036535036536127546251228978717090890865361503462512897275170875、(1)哈夫曼樹。(2)譯碼過程：譯碼過程與編碼一樣需要使用哈夫曼樹。譯碼過程為：自左向右逐一掃描碼文，并從哈夫曼樹的根開始，將掃描得到的二進(jìn)制串中的碼位與哈夫曼樹分支上標(biāo)的0、1相匹配，以確定一條從根到葉子的路徑，一旦達(dá)到葉子，則譯出了一個字符；再回到樹根，從二進(jìn)位串的下一位開始繼續(xù)譯碼，直到掃描碼文結(jié)束。(3)只需判定存儲有字符信息的節(jié)點是否全部為葉子結(jié)點即可。若存儲有某個字符信息的節(jié)點非葉子結(jié)點，即有子節(jié)點，那么它的0/1編碼一定是它孩子節(jié)點0/1編碼的前綴，違反了前綴特性。五、算法設(shè)計1、(1)voidsift(intn){∥假設(shè)data[1..n-1]是大堆,本算法把data[1..n]調(diào)成大堆intj=n;data[0]=data[j];for(inti=n/2;i>=1;i=i/2)if(data[0]>data[i]){data[j]=data[i];j=i;}elsebreak;data[j]=data[0];}(2)voidheapBuilder(){for(inti=2;i<=curLength;i++)sift(i);}2、參見代碼7.6【答案要點】(1)算法的基本設(shè)計思想：表達(dá)式樹的中序序列加上必要的括號即為等價的中綴表達(dá)式?？梢曰诙鏄涞闹行虮闅v策略得到所需的表達(dá)式。(3分)表達(dá)式樹中分支結(jié)點所對應(yīng)的子表達(dá)式的計算次序，由該分支結(jié)點所處的位置決定。為得到正確的中綴表達(dá)式，需要在生成遍歷序列的同時，在適當(dāng)位置增加必要的括號。顯然，表達(dá)式的最外層(對應(yīng)根結(jié)點)及操作數(shù)(對應(yīng)葉結(jié)點)不需要添加括號。(2分)(2)算法實現(xiàn)(10分)voidBtreeToE(BTree*root){BtreeToExp(root，1)； //根的高度為1}voidBtreeToExp(BTree*root,intdeep){ //中序遍歷求中綴表達(dá)式if(root==NULL)return;elseif(root->left==NULL&&root->right==NULL)//若為葉結(jié)點printf(“％s”，root->data)； //輸出操作數(shù)else{if(deep>1)printf(“(”)； //若有子表達(dá)式則加1層括號BtreeToExp(root->left，deep+1)； printf(“％s”，root->data)； //輸出操作符BtreeToExp(root->right，deep+1)；if(deep>1)printf(“)”)； //若有子表達(dá)式則加1層括號}}習(xí)題答案一、選擇1-5：BC,A,C,D,D6-10：CC,C,BD,AB,B二、填空n(n-1)/292(n-1)n深度優(yōu)先廣度優(yōu)先三、判斷1-6：對錯錯錯錯錯2：提示，如存在A到D的兩條路徑A-〉B-〉D和A-〉C-〉D，頂點D可能多次訪問四、應(yīng)用題1、（1）G1最多n(n-1)/2條邊，最少n-1條邊(2)G2最多n(n-1)條邊，最少n條邊2、遍歷起始頂點不同；存儲結(jié)構(gòu)不同；在鄰接表情況下鄰接點的順序不同；以及遍歷算法迭代順序不同等。3、abedfc,acfdeb,aebdfc,aedfcb4、深度優(yōu)先遍歷：V1->V2->V3->V6->V5->V4深度優(yōu)先遍歷：V1->V2->V5->V4->V3->V65、設(shè)鄰接表（略）中頂點的鄰接點按頂點編號升序排列（V1編號為1）（1）廣度優(yōu)先遍歷序列：V1V2V3V4V5V6V7V8（2）深度優(yōu)先遍歷序列：V1V2V4V8V5V3V6V7應(yīng)用題5（3）BFSV應(yīng)用題5（3）BFSV3V2V4V5V1V8V6V7應(yīng)用題5（3）DFSV3V2V4V5V1V8V6V7V76、（2）深度優(yōu)先遍歷：V1，V2，V3，V4，V5；寬度優(yōu)先遍歷：V1，V2，V3，V4，V5應(yīng)用題6（1）（3）DFS和BFS生成森林應(yīng)用題6（1）（3）DFS和BFS生成森林V3V2V1V5V4V3V2V1V5V4V3V2V1V5V47、（1）（2）應(yīng)用題7（1）（2）應(yīng)用題7（1）（2）（2）廣度優(yōu)先遍歷序列AFEDBC8、（1）僅從鋪設(shè)費用角度出發(fā)，為了求解最經(jīng)濟(jì)的方案，可以把問題抽象為求無向帶權(quán)圖的最小生成樹?？梢圆蒔rim算法或Kruscal算法手工模擬?？梢郧蟮帽绢}最小生成樹有兩種形式，如下圖所示。兩種方案的總費用都是16。（2）存儲題目中的圖可以采用鄰接矩陣(或鄰接表)。構(gòu)造最小生成樹可以采用Prim算法(或Kruscal算法)。（3）題目中TTL為5，即IP分組的生存時間（在本題中理解為最大傳遞距離）為5，方案1中TL和BJ過遠(yuǎn)（距離為11），TTL為5不足以讓IP分組從H1（TL）傳遞到H2（BJ）,因此H2不能收到該IP分組。而方案2中TL和BJ相鄰（距離為3），H2可以收到IP分組。XAXABJTLWHJNCSQDNJ2223232XABJTLWHJNCSQDNJ2322232方案一方案二五、算法題(只給出關(guān)鍵代碼或偽代碼)1、