算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）（第2版） 第5章課后習(xí)題答案

PAGEPAGE1習(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ù)不等時不能進行相加運算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個元素的所有組合.,將這兩種情況合到一