幾道常用數(shù)據(jù)結(jié)構(gòu)考試試題及答案

一、編程題對于二維整數(shù)數(shù)組A［m][n］,對下列三種情況，分別編寫相應(yīng)的函數(shù)。求數(shù)組所有邊緣元素的數(shù)值和.intsum1(intA[M]［N］，intm,intn）{2。求從A[0]［0］開始的互不相鄰的所有元素的和注：一個元素的八個方向上的第一個元素均為相鄰元素.intsum2（intA[M］[N],intm，intn)｛3.假定m=n，并為偶數(shù)，請分別計算正、反兩條對角線上的元素值之和。intsum3（intA［M］[N]，intn）{答（1）本小題是計算數(shù)組A的最外圍的4條邊的所有元素之和.可以先累加各個靠邊的元素的值,再減去位于4個角上重復(fù)相加的元素的值。intsum1（intA［M］［N］,intm，intn)｛ints=0,i，j；for（i=0；i〈m；i++）｛s+=A[i]［0]；s+=A[i］[n—1］；｝for（j=0;j<n；j++）{s+=A[0][j]；s+=A［m—1]［j］；}s=s—A[0］［0]—A［0］［n—1]-A[m-1］[0]-A[m—1][n-1］;returns；｝（2）本小題的互不相鄰是指上、下、左、右、對角線均互不相鄰，即求第0，2,4，…。。,列的所有元素的值之和。intsum2（intA[M]［N]，intm,intn)｛ints=0,i,j；for（i=0,i〈m,i+=2）for(j=0,j〈n,j+=2)s+=A［i]［j]；returns;}(3）本小題中一條對角線是A[i］［j］,i=0，1，….。n—1；另一條對角線是A［i][n-i-1］，i=0,1，…。.n—1。可以用循環(huán)實現(xiàn).intsum3（intA［M][N］,intn){ints=0，i;for（i=0，i<n，i++)｛s+=A[i]［j]；s+=A[i][n-i-1］;}returns;}設(shè)順序表L是一個遞增有序表,試寫一算法，將x插入L中，并使L仍是一個有序表。因已知順序表L是遞增有序表，所以只要從順序表終端結(jié)點(diǎn)（設(shè)為i位置元素）開始向前尋找到第一個小于或等于x的元素位置i后插入該位置即可。在尋找過程中，由于大于x的元素都應(yīng)放在x之后,所以可邊尋找,邊后移元素,當(dāng)找到第一個小于或等于x的元素位置i時，該位置也空出來了.算法如下：voidInsertIncreaseList(Seqlist*L,Datatypex)｛inti;if(L-〉length〉=ListSize）Error(“overflow")；for(i=L—>length；i〉0＆＆L->data[i—1］〉x；i——）L—>data［i]=L->data[i];//比較并移動元素L—〉data[i］=x;L—>length++；｝只要從終端結(jié)點(diǎn)開始往前找到第一個比x大（或相等）的結(jié)點(diǎn)數(shù)據(jù)，在這個位置插入就可以了.算法描述如下：intInsertDecreaseList(SqList*L，elemtypex）{inti;if(（＊L)。len＞=maxlen）｛printf(”overflow")；return(0);}for（i=(*L).len；i＞0＆&（*L).elem［i—1]＜x；i-—）（*L）。elem[i］=（＊L).elem[i-1］；//比較并移動元素（*L).elem［i］=x；(*L)。len++;return（1);}/view/b16afa650b4c2e3f572763cd.html？from=search二、解答題（20分）設(shè)有一個求解漢諾塔（Hanoi)的遞歸算法voidHANOI（intn,intpeg1，intpeg2，intpeg3)｛if（n==1)printf（”move％dto％d\n”,peg1,peg3）；else｛HANOI（n-1,peg1，peg3,peg2）;printf(”move%dto%d\n”，peg1,peg3）;HANOI(n—1，peg2，peg1,peg3）;｝｝假定采用HANOI（3，1，2，3）去調(diào)用上述算法，則寫出整個輸出結(jié)果的前四行內(nèi)容。三、畫圖題(20分）某子系統(tǒng)在通