第3部分 模拟试题及参考答案(6)

·26· 数据结构简明教程（C语言描述）

A C B E H I

F

2．参考答案：

80 60 100 40 70 120

3．参考答案：

(1) G1的邻接表和G1的逆邻接表

V1 V2 ^ V3 V4 4 ^ 1 ^ 2 3 ^

V1 V2 V3 V4 4 ^ 1 ^ 1 ^ 3 ^

(2) G1的强连通分量

4．参考答案：

(1) 以所有字符的权值作为叶结点构成的哈夫曼树如下：

第3部分 模拟试题及参考答案 ·27·

42 16 19 11

(2) 所有字符的哈夫曼编码如下： A(7)： 0011 B(19)： 011 C(5)： 0010 D(16)： 010 E(42)： 01 F(11)： 000 5．参考答案：

vi v1 v2 v3 v4 v5 v6 5 7 事件的发生时间 活动的发生时间 ve 0 6 3 12 18 21 vl 0 7 3 12 18 21 ai a1 a2 a3 a4 a5 a6 a7 a8 a9 e 0 0 3 6 3 3 12 12 18 l 5 0 4 7 3 14 12 19 18 l-e 5 0 1 1 0 11 0 7 0 6．参考答案：

(1) 该序列是一个小根堆。

(2) 该序列不是一个小根堆，调整如下：

20 25 23 35 28 38 29 61 56 76 40 100 ·28· 数据结构简明教程（C语言描述）

四．算法设计题(30分) 1．算法代码：

void fun(BiTree T, char x, int m){ if(T){ m++;

if(T->data==x) {printf(\ fun (T->lchild,x,m); fun (T->rchild,x,m); } }

main(){

BiTree bt; int m=0; fun(bt,m); }

2．算法代码：

#define MAXSIZE 100 typedef int ElemType; typedef struct{

ElemType elem[MAXSIZE]; int top[2]; }DuStack; DuStack s;

int push(int i,int x) /*入栈操作*/ {

if(i<0||i>1) { printf(\输入数据有误\ if(s.top[1]-s.top[0]==1) {printf(\栈满\ switch(i) {

case 0: s.elem[++s.top[0]]=x; break;

case 1: s.elem[--s.top[1]]=x; }

return 1; }

int pop(int i, int *x) /*出栈操作*/ {

if(i<0||i>1) { printf(\输入数据有误\ switch(i) {

case 0:

if(s.top[0]==-1) {printf(\栈空\ else *x=s.elem[s.top[0]--]; break; case 1:

if(s.top[0]==MAXSIZE) {printf(\栈空\ else *x=s.elem[s.top[1]++]; }

return 1;

第3部分 模拟试题及参考答案 ·29·

}

3．算法代码：

void dijkshort(MGraph G,int v){ int s[30]; int d[30]; int pre[30]; int i,j,k,p,min;

for(i=1;i<=G.vexnum;i++){ d[i]=G.arcs[v][i]; s[i]=0;

if(d[i]<32767) pre[i]=v; else pre[i]=0; }

s[v]=1;

for(i=1;i<=G.vexnum;i++){ min=32767; k=0;

for(j=1;j<=G.vexnum;j++)

if(!s[j]&&d[j]

s[k]=1; /*将找到的顶点加入到第一组中*/

for(j=1;j<=G.vexnum;j++) /*修改第二组中顶点的距离值*/ if(!s[j]&&d[j]>d[k]+G.arcs[k][j]) { d[j]=d[k]+G.arcs[k][j]; pre[j]=k; } }

for(j=1;j<=G.vexnum;j++) /*输出结果*/ if(pre[j]){

printf(\ while(p){

printf(\ p=pre[p]; }

printf(\ } else

if(j!=v) printf(\}