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

一、编程题(一)对于二维整数数组Amn，对下列三种情况，分别编写相应的函数。1. 求数组所有边缘元素的数值和。int sum1(int AMN,int m ,int n)2.求从A00开始的互不相邻的所有元素的和注：一个元素的八个方向上的第一个元素均为相邻元素。int sum2 (int AMN , int m , int n)3. 假定m=n，并为偶数，请分别计算正、反两条对角线上的元素值之和。int sum3(int AMN , int n)答（1）本小题是计算数组A的最外围的4条边的所有元素之和。可以先累加各个靠边的元素的值，再减去位于4个角上重复相加的元素的值。int sum1(int AMN,int m ,int n) int s=0,i,j; for(i=0;im;i+)s+=Ai0;s+=Ain-1; for(j=0;jn;j+)s+=A0j;s+=Am-1j; s=s-A00-A0n-1-Am-10-Am-1n-1; return s;（2）本小题的互不相邻是指上、下、左、右、对角线均互不相邻，即求第0，2，4，.，列的所有元素的值之和。int sum2(int AMN,int m ,int n) int s=0,i,j; for(i=0,im,i+=2) for(j=0,jn,j+=2) s+=Aij; return s; （3）本小题中一条对角线是Aij，i=0,1,.n-1;另一条对角线是Ain-i-1，i=0,1,.n-1。可以用循环实现。int sum3(int AMN ,int n) int s=0,i; for(i=0,ilength=ListSize)Error(“overflow);for ( i=L - length ; i0 & L-data i-1 x ; i-)L-data i =L-data i ; / 比较并移动元素L-data i =x;L - length+;只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：int InsertDecreaseList(SqList*L，elemtype x) int i;if(*L). len=maxlen)printf(over flow)；return(0);for(i=(*L). len; i0(*L). elemi-1x; i-)(*L). elemi=(*L). elemi-1; /比较并移动元素(*L). elemi=x;(*L). len+;return(1);/view/b16afa650b4c2e3f572763cd.html?from=search二、解答题（20分）(一)设有一个求解汉诺塔（Hanoi）的递归算法voidHANOI (int n , int peg1 , int peg2 , int peg3)if (n= =1) printf（”move %d to %dn”,peg1,peg3）;elseHANOI (n-1, peg1, peg3, peg2);printf（”move %d to %dn”,peg1,peg3）;HANOI (n-1, peg2, peg1, peg3) ; 假定采用HANOI（3，1，2，3）去调用上述算法，则写出整个输出结果的前四行内容。三、画图题（20分）(一)某子系统在通信联络中只可能出现8种字符，其出现的概率