《數(shù)據(jù)結(jié)構(gòu)》(第二版)課后答案5-9章 鄒嵐

一．選擇題1.B2.A3.C4.B5.D6.D7.C8.D9.C10.B11.C12.D13.A14.C15.D16.D17.C18.D19.B20.C21.A22.B23.B24.C25.D二．填空題1.i(i+1)/2+j2.1741393.4.對(duì)稱上三角（下三角）矩陣5.d6.表頭表尾7.（2,3,5）8.行列9.3310.O(n)11.O(n2)12.行列13.（）((),(()))3314.(a)((b),((c)))三．判斷題1.√2.√3.√4.√5.×6.×7.√8.√9.√10.√四、簡(jiǎn)答題二維數(shù)組存儲(chǔ)時(shí)，要把它的元素映像存儲(chǔ)在一維存儲(chǔ)器中，存儲(chǔ)時(shí)若按先行后列的順序存儲(chǔ)，叫做二維數(shù)組的行序優(yōu)先存儲(chǔ)。若按先列后行的順序存儲(chǔ)，叫做二維數(shù)組的列序優(yōu)先存儲(chǔ)。元素分布特殊的矩陣，列如三角矩陣，對(duì)稱矩陣，帶狀矩陣，稀疏矩陣等，叫做特殊矩陣。特殊矩陣壓縮存儲(chǔ)的基本思想是壓縮存儲(chǔ)，即值相同的元素只分配一個(gè)存儲(chǔ)空間，零元素不分配存儲(chǔ)空間。設(shè)m*n矩陣中有t個(gè)非零元素且t<<m*n,這樣的矩陣叫做稀疏矩陣。系數(shù)矩陣存儲(chǔ)時(shí)可只存儲(chǔ)非零元素，由于非零元素的分布一般是沒(méi)有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須存儲(chǔ)非零元素所在的行號(hào)、列號(hào)，才能迅速確定一個(gè)非零元素是矩陣中的哪一個(gè)元素。ije001042204215436(((a,b,()),(),a,(b)),())6.程序設(shè)計(jì)題1.1.intgenlistDepth(BSLinkListlist){/*list存放廣義鏈表的首地址，該算法返回廣義鏈表的深度*/BSLinkListstack1[M],p;/*stack1用來(lái)記錄子表的起始位置*//*stack2用來(lái)記錄子表當(dāng)前的深度，depth用來(lái)表示當(dāng)前所求子表的深度，maxdep用來(lái)記錄當(dāng)前已求出的那些子表的最大深度,stack1和stack2共用一個(gè)棧頂指針*/intstack2[M],depth=0,maxdep=0,top=-1;p=list->pointer;/*將p指針指向廣義鏈表的第一個(gè)元素所在的鏈接點(diǎn)*/if(p!=NULL){do{while(p!=NULL){stack1[++top]=p;/*記錄當(dāng)前子表的起始位置*/stack2[top]=depth;/*記錄當(dāng)前所求子表的深度*/if(p->flag==1){/*當(dāng)前鏈接點(diǎn)元素是子表*/depth++;/*當(dāng)前層次數(shù)加1*/p=p->pointer;/*移動(dòng)到下一層*/}elsep=NULL;}if(maxdep<depth){maxdep=depth;/*記錄當(dāng)前已求得的最大層次數(shù)*/}p=stack1[top];/*退回到上一層，移動(dòng)到下一個(gè)元素，查看是否有子表*/depth=stack2[top--];p=p->link;}(p!=NULL&&top!=-1);}returnmaxdep+1;}2.#include<stdio.h>#include<string.h>main(){inta[100][100],m;intn,i,j,k,max,flat=0,l;scanf("%d,%d",&n,&l);for(i=0;i<n;i++)for(j=0;j<l;j++)scanf("%d",&a[i][j]);for(i=0;i<n;i++){m=a[i][0];for(j=0;j<l;j++)if(a[i][j]>m){m=a[i][j];max=j;}for(k=0;k<n;k++)if(a[k][max]<m){printf("No\n");flat++;break;}if(flat==0)printf("%c\n",m);}}3.（1）#include<stdio.h>voidproc1(matrixA){ints=0,i,j;for(i=0;i<m;i++)/*第一列*/s=s+A[i][1];for(i=0;i<m;i++)/*最后一列*/s=s+A[i][n];for(j=0;j<n;j++)/*第一行*/s=s+A[1][j];for(j=0;j<m;j++)/*最后一行*/s=s+A[m][j];s=s-A[0][0]-A[0][n-1]-A[m-1][0]-A[m-1][n-1];/*減去4個(gè)角的重復(fù)元素值*/printf("s=%d\n",s);}（2）voidproc2(matrixA){ints=0,i,j;i=0;while(i<m){j=0;while(j<n){s=s+A[i][j];j=j+2;/*跳過(guò)一列*/}i=i+2;/*跳過(guò)一行*/}printf("s=%d\n",s);}（3）voidproc3(matrixA){inti,s;if(m!=n)printf("m!=n");else{s=0;for(i=0;i<m;i++)s=s+A[i][i];/*求第一列對(duì)角線之和*/for(i=0;i<n;i++)s=s+A[n-i-1][i];/*累加第二條對(duì)角線之和*/printf("s=%d\n",s);}}voidmain(){intm,n,i,j;matrixA;printf("m,n:");scanf("%d%d",&m,&n);printf("元素值:\n");for(i=0;i<m;i++)/*建立數(shù)組*/for(j=0;j<n;j++)scanf("%d",&A[i][j]);proc1(A);/*調(diào)用proc1()*/proc2(A);/*調(diào)用proc2()*/proc3(A);/*調(diào)用proc3()*/}樹答案一選擇題1-5ABBDC6-10CACBD11-15BCADB16-20BAAAA21-22CA二填空題n2+137單分支完全二叉樹12764312+12-11多129P->lchild==null&&p->rchild==null哈夫曼樹41601656316、6三綜合應(yīng)用題1（1）根節(jié)點(diǎn)：A葉子節(jié)點(diǎn)：CEFHIJKMN非終端節(jié)點(diǎn)：ABDGL（2）深度：5各節(jié)點(diǎn)層數(shù)A：1；B、C、D：2；E、F、G、H、I、J：3；K、L、M：4；N：5雙親：D祖先：AD孩子：KLM子孫：KLMN兄弟：HIJ堂兄弟：EF2先序遍歷：ABCDEFGHIJ中序遍歷：BCDAFEHJIG后序遍歷：DCBFJIHGEA3對(duì)應(yīng)的二叉樹后序遍歷為：bdeca456帶權(quán)路徑長(zhǎng)度WPL=(2+3)*4+(6+7+8)*3+(10+14)*2=131樹的結(jié)點(diǎn)總數(shù)137(1)哈夫曼樹：給定n個(gè)權(quán)值作為n個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。(2)哈夫曼樹為：哈弗曼編碼：a:1110b:1111c:110d:00e:01f:10(4)長(zhǎng)度：244四、算法設(shè)計(jì)題設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundx\n");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}

設(shè)計(jì)判斷兩個(gè)二叉樹是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}

設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} }4.設(shè)計(jì)求二叉樹中值為x的結(jié)點(diǎn)所在的層號(hào)的算法。intlev=0;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidlevel(bitree*bt,intx){if(bt!=0){lev++;if(bt->key==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}第七章圖選擇題B2.B3.C4.A5.AB7.D8.B9.A10.A11.B12.B13.A14.C15.A16.C17.C18.D19.C20.B21.A22.D23.B24.A25.C26.C二、填空題1.度，出度2.ACDFBEABECFDn(n-1)，n4.n(n-1)/2n(n-1)m=2e6.n-17.鄰接矩陣，鄰接表，十字鏈表，臨接多重鏈表，邊集數(shù)組8.66n,2en-111.1,012.1第i列元素的和14.45,90n-1e,2e17A[i][j]=A[j][i]=1等于19.出度,入度可以隨機(jī)訪問(wèn)任意頂點(diǎn)O（n2）,O(n+e)v1,v3,v2,v4v1,v3,v2,v423.13245活動(dòng)和活動(dòng)間的優(yōu)先關(guān)系25有向無(wú)環(huán)三、判斷題1.√2.×3.×4.×5.×6.√7.×8×9.√10√11√四、簡(jiǎn)答題1.圖的深度遍歷相關(guān)無(wú)關(guān)123564123456最小生成樹：4.5.邊的集合{【1,5】，【2，5】，【3,5】，【3,4】}權(quán)值之和106.12543廣度優(yōu)先生成樹：（2）7.（1）深度優(yōu)先遍歷：abdce廣度優(yōu)先遍歷abedc(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,（4,6)4,(5,7)20（1）（2）五、算法設(shè)計(jì)題1.intCount(GraphG){intcount=0;for(v=0;v<G.vexnum;++v)visited[v]=false;//初始化每個(gè)節(jié)點(diǎn)的被訪問(wèn)標(biāo)記for(v=0;v<G.vexnum;++v){if(!visited[v]){DFS(G,v);count++;}}returncount;}voidDFS(GraphG,int){visited[v]=true;for(w=FirstAdjVex(G,v);w;w=NextAgjVex(G,v,w)){if(!visited[w])DFS(G,w)}}2.intvisited[MAXSIZE];//指示頂點(diǎn)是否在當(dāng)前路徑上intexist_path_DFS(ALGraphG,inti,intj)//深度優(yōu)先判斷有向圖G中頂點(diǎn)i到頂點(diǎn)j是否有路徑,是則返回1,否則返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!visited[k]&&exist_path(k,j))return1;//i下游的頂點(diǎn)到j(luò)有路徑}//for}//else}//exist_path_DFSvoidfind(intA[][],intm,intn)//求矩陣A中的馬鞍點(diǎn){inti,j,min,flag;for(i=0;i<m;i++){for(min=A[i][0],j=0;j<n;j++)if(A[i][j]<min)min=A[i][j];//求一行中的最小值for(j=0;j<n;j++)if(A[i][j]==min)//判斷最小值是否是馬鞍點(diǎn){for(flag=1,k=0;k<m;k++)if(min<A[k][j])flag=0;if(flag)printf("%d",A[i][j]);}}}voidMerge(LinkList&A,LinkList&B,LinkList&C)//假設(shè)是遞增序列{LinkListp,q,r;p=A->next;q=B->next;r=C=A;while(p&&q){if(p->data<q->data){r->next=p;r=r->next;p=p->next;}else{r->next=q;r=r->next;q=q->next;}}r->next=(p!=NULL?p:q);free(B);}3.第八章答案選擇題1~5CCCCD6~10BACBD11~15BAAAA16~20CBCBB21~25CB⑧①③④DB26~31CBDBCA二、選擇題1~9對(duì)對(duì)錯(cuò)對(duì)對(duì)對(duì)錯(cuò)三、填空題（1）2.9（2）2.1（3）1、2（4）7（5）1、2、4、8、5、3.7（6）O(n)、O(log2n)（7）3（8）增高一層（9）h（10）遞增數(shù)列、后綴表達(dá)式（11）┌m/2┐-1、m-1、O(n)、O(nlog2n)、O(n)（12）減少一層（13）如何構(gòu)造哈希函數(shù)、如何處理沖突（14）發(fā)生沖突的可能性越大、發(fā)生沖突的可能性越小（15）開(kāi)放定址法、拉鏈法四、簡(jiǎn)答題1.靜態(tài)查找表：如果一個(gè)查找表的操作只涉及查詢和檢索某個(gè)特定的數(shù)據(jù)元素的操作，無(wú)需動(dòng)態(tài)的修改查找表，此類查找表稱之為靜態(tài)查找表。動(dòng)態(tài)查找表：需要?jiǎng)討B(tài)的插入或刪除操作的查找表稱之為動(dòng)態(tài)查找表。適合靜態(tài)查找的存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)，散列存儲(chǔ)。適合動(dòng)態(tài)查找的存儲(chǔ)結(jié)構(gòu)有：順序存儲(chǔ)，散列存儲(chǔ)。2.平均查找長(zhǎng)度：在查找過(guò)程中，一次查找的長(zhǎng)度是指需要比較的關(guān)鍵字的次數(shù)，而平均查找長(zhǎng)度則是所有查找過(guò)程中進(jìn)行關(guān)鍵字的比較次數(shù)的平均值。其數(shù)學(xué)定義為ASL=∑PiCi(i=1,2,3,…,n),其中：Pi為查找表中第i個(gè)數(shù)據(jù)元素的概率，Ci為找到第i個(gè)數(shù)據(jù)元素時(shí)已經(jīng)比較過(guò)的次數(shù)。3.（1）53/\1766/\/\12255870/\\566087（2）中序遍歷二叉排序樹可得到一個(gè)從小到大的有序序列。4.5.（1）（2）ASL=(4+2*3+3*2+4)/9=20/96.7.8.H(25)=25mod7=4H(31)=31mod7=3H(8)=8mod7=1H(27)=27mod7=6H(13)=13mod7=6H(68)=68mod7=5線性探測(cè)法：ASL=(5*1+2)/6=7/6鏈地址法：ASL=(5*1+1*2)/6=7/69.H(105)=105mod13=1H(97)=97mod13=6H(28)=28mod13=2H(52)=52mod13=0H(37)=37mod13=11H(22)=22mod13=9H(16)=16mod13=3H(90)=90mod13=12H(45)=45mod13=6H(76)=76mod13=11H(59)=59mod13=7H(74)=74mod13=9（1）散列地址0123456789101112131415關(guān)鍵字5210528169745592274379076沖突次數(shù)111112212113（2）散列地址0123456789101112131415關(guān)鍵字5210528169745592276379074沖突次數(shù)11111221311510.H(11)=(5*11)%11=0H(81)=(5*81)%11=7H(23)=(5*23)%11=5H(59)=(5*59)%11=9H(17)=(5*17)%11=8H(19)=(5*19)%11=7H(68)=(5*68)%11=10散列地址012345678910關(guān)鍵字11231981175968沖突次數(shù)1131111ASL(成功)=（6*1+3)/7=9/7ASL（不成功）=(1+7+6+5+4+3+2)/11=28/11六、設(shè)計(jì)題1.二分查找遞歸算法：Typedefstruct{//查找表的數(shù)據(jù)結(jié)構(gòu)ElemType*elem;intlength;}SSTable;intBinSearch(SeqlistR,ElemTypek,intlow,inthigh){intmid;if(low<=high){mid=(low+high)/2;if(k>R[mid].key)Search(R,key,mid+1,high);elseif(k<R[mid].key)Search(R,key,low,mid-1);elsereturnmid;}elsereturn(-1);}二分查找非遞歸算法：intBinSearch(SeqlistR,ElemTypek,intn){intlow=0,high=n-1,mid;While(low<=high){mid=(low+high)/2;if(k>R[mid].key)low=mid+1;elseif(k<R[mid].key)High=mid-1;elsereturnmid;}Return-1;}2.KeyTypepredt=-32767;//predt為全局變量，保存當(dāng)前結(jié)點(diǎn)中序前驅(qū)的值，初值為-∞intJudgeBST(BiTreebt){intb1,b2;if(bt==NULL)return1;else{b1=JudgeBST(bt->lchild);if(b1==0||pred>=bt->data)return0;pred=bt->data;b2=JudgeBST(bt->rchild);returnb2;}}3.intlevel(BiTreebt,BSTNode*p){intn=0;BiTreet=bt;if(bt!=NULL){n++;while(t->data!=p->data){if(t->data<p->data)t=t->rchild;elset=t->lchild;n++;}}returnn;}4.voidinordprint(Bitreebt){intn;if(bt!=NULL){inordprint(bt->lchild);for(inti=1;i<=n;i++)printf("%d",bt->data);inordprint(bt->rchild);}}5.BSTNode*BST_Search(BiTreebt,ElemTypeX){if(bt==NULL)return(NULL);elseif(bt->data==X)return(bt);elseif(bt->data>X)return(BST_Search(bt->lchild,X));elsereturn(BST_Search(bt->rchild,X));}6.boolsearchmin(Sqlist&L,DateTypek){if(L.Length==0)returnfalse;k=L.data[0];intpos=0;for(inti=1;i<n;i++)if(L.data[i]<k){k=L.data[i];pos=i;}returnk;}一、選擇題1-5 BDDDA6-10 CCDDB 11-15 DBDAB 16-20 DDCCA21-25 DBAAB 26-28 ACC二、填空題1、(49，13，27，50，76，38，65，97) 2、8,8 3、O(n)，O(nlogn) 4、O(n)，O(nlogn)5、n-1 6、插入，選擇7、3 8、（12,24,27,35,18,26）9、（12,18,24,35,27,26） 10、（38,13,27,10,65,76,97）11、（5,16,71,23,72,94,73） 12、快速，歸并13、希爾排序，選擇排序，快速排序，堆排序 14、歸并排序三、判斷題錯(cuò)2、對(duì)3、錯(cuò)4、錯(cuò)5、錯(cuò)6、對(duì)7、錯(cuò)8、錯(cuò)四、算法設(shè)計(jì)題1、解：因?yàn)橹恍鑼⒇?fù)數(shù)關(guān)鍵字排在前面而無(wú)需進(jìn)行精確排列順序，因此本算法采用兩端掃描的方法，就象快速排序采用的方法一樣，左邊掃描到正數(shù)時(shí)停止，開(kāi)始掃描右邊，遇到負(fù)數(shù)時(shí)與左邊的當(dāng)前記錄交換，如此交替進(jìn)行，一趟下來(lái)就可以完成排序。voidReSort(SeqListR){//重排數(shù)組，使負(fù)值關(guān)鍵字在前inti=1,j=n;//數(shù)組存放在R[1..n]中while(i<j)//i<j表示尚未掃描完畢{while(i<j&&R[i].key<0)//遇到負(fù)數(shù)則繼續(xù)掃描i++;R[0]=R[i];//R[0]為輔助空間while(i<j&&R[j].key>=0)//遇到正數(shù)則繼續(xù)向左掃描j--;R[i++]=R[j];R[j--]=R[0];//交換當(dāng)前兩個(gè)元素并移動(dòng)指針}//endwhile}//ReSort2、#defineKeySize10//設(shè)關(guān)鍵字位數(shù)d=10#defineRadix27//基數(shù)rd為27typedefRecTypeDataType;//將隊(duì)列中結(jié)點(diǎn)數(shù)據(jù)類型改為RecType類型typedefstructnode{charkey[KeySize];//關(guān)鍵字域OtherInfoTypeinfo;//其它信息域，}RecType;//記錄結(jié)點(diǎn)類型typedefRecTypeseqlist[n+1];

voidRadixSort(seqlistR){