数据结构天津大学离线考核题库及答案

数据结构

请在以下五组题目中任选一组作答，满分100分。 第一组：

一、编程题（每小题30分，共60分）

(一)

对于二维整数数组A[m][n]，对下列三种情况，分别编写相应的函数。 1. 求数组所有边缘元素的数值和。

int sum1(int A[M][N],int m ,int n) {

2.求从A[0][0]开始的互不相邻的所有元素的和

注：一个元素的八个方向上的第一个元素均为相邻元素。 int sum2 (int A[M][N] , int m , int n) {

3. 假定m=n，并为偶数，请分别计算正、反两条对角线上的元素值之和。

int sum3(int A[M][N] , int n) {

答：1、本小题是计算数组A的最外围的4条边的所有元素之和。可以先累加各个靠边的元素的值，再减去位于4个角上重复相加的元素的值。

int sum1(int A[M][N],int m ,int n){ int s=0,i,j;

for(i=0;i

2、本小题的互不相邻是指上、下、左、右、对角线均互不相邻，即求第0，2，4，…..，列的所有元素的值之和。 int sum2(int A[M][N],int m ,int n){ int s=0,i,j;

for(i=0,i

3、本小题中一条对角线是A[i][i]，i=0,1,…..n-1;另一条对角线是A[i][n-i-1]，i=0,1,…..n-1。可以用循环实现。

int sum3(int A[M][N] ,int n){ int s=0,i; for(i=0,i

{s+=A[i][i];s+=A[i][n-i-1];} return s; }

（二）设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。 在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。 算法如下：

void InsertIncreaseList( Seqlist *L , Datatype x ) { int i;

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++;

}

二、解答题（20分） (一)

设有一个求解汉诺塔（Hanoi）的递归算法

voidHANOI (int n , int peg1 , int peg2 , int peg3) {

if (n= =1)

printf（”move %d to %d\\n”,peg1,peg3）; else {

HANOI (n-1, peg1, peg3, peg2);

printf（”move %d to %d\\n”,peg1,peg3）; HANOI (n-1, peg2, peg1, peg3) ; } }

假定采用HANOI（3，1，2，3）去调用上述算法，则写出整个输出结果的前四行内容。

解：汉诺塔的递归处理过程如下表示：

move 1 to 3 move 1 to 2 move 3 to 2 move 1 to 3

三、画图题（20分） (一)

某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码