2024年1月5日发(作者：)

第二章 线性表(参考答案)

在以下习题解答中，假定使用如下类型定义：

2.1 头指针：指向链表的指针。因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。如：链表的头指针是la，往往简称为“链表la”。

头结点：为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。这样在插入和删除中头结点不变。

开始结点：即上面所讲第一个元素的结点。

2·5

void insert(linklist *L,ElemType x)

// 带头结点的单链表L递增有序，本算法将x插入到链表中，并保持链表L的递增有序。

{ linklist *p=L->next, *pre=L，*s;

// p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱

s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断溢出

s->data=x;

while (p && p->data<=x) {pre=p; p=p->next;} // 查找插入位置

pre->next=s; s->next=p; // 插入元素

} // 算法结束

2·9

void deleteprior(linklist *L)

// 长度大于1的单循环链表，既无头结点，也无头指针，本算法删除*s 的前驱结点

{ linklist *p=s->next,*pre=s; // p为工作指针，指向当前元素，

// pre为前驱指针，指向当前元素*p的前驱

while (p->next!=s) {pre=p; p=p->next;} // 查找*s的前驱

pre->next=s;

free(p); // 删除元素

} // 算法结束

第三章 栈和队列(参考答案)

3.1 1234四辆车进栈，写出出战顺序？

1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1

1 2 4 3 2 1 4 3 3 2 4 1

1 3 2 4 2 3 1 4 3 4 2 1

1 3 4 2 2 3 4 1

1 4 3 2 2 4 3 1

设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2)

3.3 void sympthy(linklist *head, stack *s)

//判断长为n的字符串是否中心对称

{ int i=1; linklist *p=head->next;

while (i<=n/2) // 前一半字符进栈

{ push(s,p->data); p=p->next; }

if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点

while (p && p->data==pop(s)) p=p->next;

if (p==null) printf(“链表中心对称”)；

else printf(“链表不是中心对称”)；

} // 算法结束

3.4

int match()

//从键盘读入算术表达式，本算法判断圆括号是否正确配对

（init s;//初始化栈s

scanf(“%c”,&ch);

while (ch!=’#’) //’#’是表达式输入结束符号

switch (ch)

{ case ’(’: push(s,ch); break;

case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);}

pop(s);

}

if (!empty(s)) printf(“括号不配对”);

else printf(“括号配对”);

} // 算法结束

第四章 串 (参考答案)

4.4 将S=“（xyz）*”转为T=“（x+z）*y”

S=concat(S, substr(S,3,1)) // ”(xyz)*y”

S=replace(S,3,1,”+”) // ”(x+z)*y”

第五章 多维数组和广义表（参考答案）

5.1 按行优先顺序列出A[2][3][2][3]所有元素在内存中的存储次序

A[2][3][2][3]

A0000 , A0001 , A0002

A0010 , A0011 , A0012

A0100 , A0101 , A0102

A0110 , A0111 , A0112

A0200 , A0201 , A0202

A0210 , A0211 , A0212

将第一维的0变为1后，可列出另外18个元素。以行序为主（即行优先）时，先改变右边的下标，从右到左进行。

5.2 求三维数组按行优先顺序存储的地址计算公式？

设各维上下号为c1„d1，c2„d2，c3„d3，每个元素占l个单元。

LOC(aijk)=LOC(ac1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l

推广到n维数组！！（下界和上界）为（ci，di），其中1<=i<=n.则：其数据元素的存储位置为：

LOC（aj1j2….jn）=LOC（ac1c2…cn）+[（d2-c2+1） „（dn-cn+1）(j1-c1)+(d3-c3+1) „（dn-cn+1）

n

(j2-c2)+„+(dn-cn+1)(jn-1-cn-1)+(jn-cn)]*l=LOC(ac1c2c3)+ ∑αi(ji-ci)

n

i=1

其中αi∏（dk-ck+1）（1<=i<=n）

k=i+1

若从c开始，c数组下标从0开始，各维长度为bi（1<=i<=n）则：

LOC（aj1j2…jn）=LOC(a00…0)+(b2* b3*„* bn*j1+ b3* „* bn*+ j2„+ bn* jn-1+ jn)*l

n

=LOC(a00…0)+ ∑αiji 其中：αi=l，α

5.3 (1) k=2*i+j ( 0<=k<3n-2 )

(2) i=(k+1)/3 ( 0<=k<3n-2 )

j=k-2*i

5.4

void saddlepoint(int a[m][n]);

// a是m行n列的二维数组,本算法求所有马鞍点

// b是一维数组,存放一行中可能的马鞍点的列值,k记相等值个数

// c是一维数组,存放某列可能马鞍点的行值,kk记相等值个数

解法3: 设定两个数组： -1] 记各列的最大值所在行号

-1] 记各行的最小值所在列号

第j 列的最大值为A[max[j]][j],第i行的最小值是A[i][min[i]]

void saddlepoint(int a[m][n]);

// a是m行n列的二维数组,本算法求所有马鞍点

{ int max[]=0,min[]=0;for(i=0;i

for(i=0; i

for (j=0; j

{ if (A[i][j]>A[max[j]][j]) max[j]=i; // 重新确定第j列最大值的行号

if (A[i][j]

}

for (i=0;i

{j=min[i]; // a[i][j]是否是马鞍点

if( max[j]==i) printf(“马鞍点 A[%d][%d]=%d”,i,j,a[i][j]);

} // END OF for jj

}

时间复杂度为O(m*n+m).

5.5 画出矩阵X的三元组表和十字链表

（1）三元组表（行号 0—5，列号 0—5）

S=（（0，0，15），（0，3，22），（0，5，-15），（1，1，11），（1，2，3），（2，3，-6），（4，0，91），（5，2，28））

（2）

i-1=bi*αi ，1

5.7 广义表的运算结果

(1) head((p,h,w))=p

(2) tail((b,k,p,h))=(k,p,h)

(3) head(((a,b),(c,d)))=(a,b)

(4) tail(((a,b),(c,d)))=((c,d))

(5) head(tail(((a,b),(c,d)))=(c,d)

(6) tail(head(((a,b),(c,d))))=(b)

5.8 画出下列广义表的图形

(1) D（A(),......） (2) J

5.9(1)

6.22

7,19,2,6,32,3,21,10其对应字母分别为a,b,c,e,f,g,h。

第6章 树和二叉树（参考答案）

哈夫曼编码：a：0010

b：10

c：00000

d：0001

e：01

f：00001

g：11

h：0011

第八章 排序（参考答案）

8.5对n个元素组成的线性表进行快速排序，所需的比较次数依赖于这n个元素的初始排列‘

（1）在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排序，将序列分成

相等程度的序列（各3个元素），再各进行2次比较，完成全部排序。

（2）最好的初始排列：4，1，3，2，6，5，7

8.11看是堆不？不是就化成堆

按极小化堆取调整（若已是极大化堆则维持不变）

（1）

（2）

（3）

（4）

8.11

void heapadjust(K[]，n)

//待排序元素在向量K中，从K1到Kn已是堆，现将第n+1个元素加入，本算法这n+1个元素调整成堆。

{rp=K[n+1]; x=K[n+1].key; // 用rp暂存第n+1个元素，x为其关键字

int c=n+1, f=c/2;

// 设c表示第n+1个元素的下标，f是其双亲的下标，本算法将子女与双亲比较，若符合堆的定义，则排序结束；否则将双亲和子女交换。之后，双亲的下标为新的子女，再与新的双亲比较，直至根结点（无双亲）

while (f>0)

if (K[f].key<=x) break; // 已符合堆的定义，排序结束

else {K[c]=k[f]; c=f; f=c/2; } // 仅将双亲移至子女

K[c]=rp;// 将暂存记录rp（原第n+1个记录）放入合适位置

}//算法结束

// 利用上述排序思想，从空堆开始，一个一个添加元素的建堆算法如下：

void heapbuilder(rectype R[])

// 向量R的第1到第n个元素为待排序元素，本算法将这n个元素建成堆。

{for (i=0;i

heapadjust(R，i);

}//算法结束

第九章 查找（参考答案）

9.12 （1）设散列表长度为13，散列函数H(K)=K%13

0 1 2 3 4 5 6 7 8 9 10 11 12

14 01 68 27

4

55

3

19

1

20

1

84

3

79

9

23

1

11

1

10

3 1 2 1

H(19)=19%13=6

H(14)=14%13=1

H(23)=23%13=10

H(01)=01%13=1 冲突，2次成功

H(68)=68%13=3

H(20)=20%13=7

H(84)=84%13=6 冲突，3次成功

H(27)=27%13=1 冲突，4次成功

H(55)=55%13=3 冲突，3次成功

H(11)=11%13=11

H(10)=10%13=10 冲突，3次成功

H(79)=79%13=1 冲突，9次成功

成功时的平均查找长度=（1*6+1*2+3*3+1*4+1*9）/12=30/12

查找不成功时的平均查找长度=（1+13+12+11+10+9+8+7+6+5+4+3+2+1）/13=92/13

（2）

0

^

1

2

^

3

4

^

5

^

6

7

8

^

9

^

10

11

12

^

14 01 27 79 ^

68 55 ^

19

20

84 ^

23

11 ^

10 ^

查找成功时平均查找长度=（1*6+4*2+1*3+1*4）/12=21/12

查找不成功时的平均查找长度=（1*7+2*2+3*3+1*5）/13=25/13

9.13 各种查找方法均有优点和缺点，不能笼统地说某种方法的好坏。

顺序查找的时间为o（n），在n较小时使用较好，它对数据元素的排列没有要求；二分查找时间为o（log2n），效率高但它要求数据元素有序排列；散查找时间为o（1），它只能按关键字随机查找（使用散列函数），不能顺序查找，也不能折半查找。