几道常用数据结构考试试题及答案

一、编程题对于二维整数数组A［m][n］,对下列三种情况，分别编写相应的函数。求数组所有边缘元素的数值和.intsum1(intA[M]［N］，intm,intn）{2。求从A[0]［0］开始的互不相邻的所有元素的和注：一个元素的八个方向上的第一个元素均为相邻元素.intsum2（intA[M］[N],intm，intn)｛3.假定m=n，并为偶数，请分别计算正、反两条对角线上的元素值之和。intsum3（intA［M］[N]，intn）{答（1）本小题是计算数组A的最外围的4条边的所有元素之和.可以先累加各个靠边的元素的值,再减去位于4个角上重复相加的元素的值。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。可以用循环实现.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;}设顺序表L是一个递增有序表,试写一算法，将x插入L中，并使L仍是一个有序表。因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。在寻找过程中，由于大于x的元素都应放在x之后,所以可边寻找,边后移元素,当找到第一个小于或等于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++；｝只要从终端结点开始往前找到第一个比x大（或相等）的结点数据，在这个位置插入就可以了.算法描述如下：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分）设有一个求解汉诺塔（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）去调用上述算法，则写出整个输出结果的前四行内容。三、画图题(20分）某子系统在通