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

1、一、编程题(一)对于二维整数数组 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

2、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

3、, i=0,1, .n -1; 另一条对角线是 Ain-i-1i=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 i;if(*L). le

4、n =maxle n)printf(over flow) ；return(0);for(i=(*L). len; i 0& (*L). elemi-1 vx; 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 , i

5、nt 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) ;假定采用 HANO(I 3，1，2，3)去调用上述算法，则写出整个输出结果的前四行内容。答案：汉前塔的递归处理过程如下表示tmove 1 tu 3move 1 to 2move 3 io 2mov 1 tv 3三、画图题（20分）（一）某子系统在通信联络中只可能出现8种字符，其

6、出现的概率分别为 0.05 ,0.29 ,0.07 ,0.08 ,0.14，0.23，0.03，0.11试设计赫夫曼编码例 w=5, 29, 7, 8,14,23, 3T 11隐 胆與仓（3）1(5):0110 2(29):103(7):1110 4(8):11115(14):110 6(23):007(3) :01118(11):010w=55 29, 7, 8,14, 23, 3,11I 1 J *答：为方fa A.段各种字符的权值w-5r29,7A1 4,23,3,11m L所以嬰构造的赫夫=2*8-1 = 15个结点.生成的赫夫曼树为下阁 所示赫夫曇编码为：概率为0.23 Yr? ?编码九00 概率为的宇符編码为：010 概宰为0.05的宁符编码为;0110 粒